草庐IT

一步步带你用Java实现双向链表（超详细）

尽欢Sir 2023-07-15 原文

文章目录

上一节说到了单链表,这一节我们来手写一个双向链表，在这之前，需要先补充一下关于双链表的概念。

什么是双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

属性及方法

节点Node

存储的数据 T data、直接前驱节点 Node pri、直接后继节点 Node next

private static class Node<T> {
    private T data;
    private Node<T> pri;
    private Node<T> next;
}

size

链表中节点的数量

数据插入

头插法 addFirst(T value)

插入数据首先要对链表进行判空

如果链表为空

头结点 = 插入的节点 = 尾结点

不为空则:

1、将插入节点的next指向头结点
2、调整头结点的前驱为新节点
3、将新节点设置为头结点
4、size++

实现细节：
Node<T> node = new Node<>(value);
if (size == 0) {
    first = node;
    last = first;
}else {
    node.next = first;
    first.pri = node;
    first = node;
}
size++;
尾插法 addLast(T value)

依旧要对链表进行判空

为空时：

等价于头插，直接调用addFirst

不为空：

1、调整尾结点的后继next指向新节点
2、调整新节点的前驱pri指向尾结点
3、更新尾结点为新的节点
4、size++

实现细节

if (size == 0){
     return addFirst(value);
 }else {
     Node<T> node = new Node<>(value);
     last.next = node;
     node.pri = last;
     last = node;
 }
size++;
插入到指定下标位置add(int index)

由于是根据下标插入的，所以首先要判断下标

注意，此时的下标最大值应该是size-1，但是在插入的时候是可以取到size的，因为此时的下标代表的是插入的位置（注意和删除时进行区分）
下标不合法:

这里我选择了抛出异常，也可以进行其他处理

下标合法【0 - size】：

1、判断下标取值

为0 即进行头插法 addFirst(T value)
为size 即进行尾插法 addLast(T value)
为其他值：

遍历到指定节点的前一个节点-> left
设置新节点的next值为left的next值
将left的next值设置为新节点
调整新节点的pri值为left
调整新节点的next节点的pri值为新节点

​ 2、size++

实现细节

add(int index,T value){
    if (index < 0 || index > size-1){
        throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
    } else if(index == 0){
        return addFirst(value);
    }else if (index == size){
        return addLast(value);
    }else {
        Node<T> node = new Node<>(value);
        Node<T> head = first;
        for (int i = 0; i < index-1; i++) {
            head = head.getNext();
        }
        node.next = head.next;
        head.next = node;
        node.pri = head;
        node.next.pri = node;
    }
    size++;
}

数据删除(返回被删除节点存储的值)

删除头结点 removeFirst

实现思想

1、判断链表是否为空
2、存储头结点存储的数据
3、将头结点更新为头结点的next节点
4、设置新的头结点的前驱节点为空
5、返回原始头结点存储的数据
6、size–

实现细节

public T removeFirst(){
    if (size == 0){
        throw new RuntimeException("链表为空！");
    }
    T data = first.getData();
    Node<T> node = first.next;
    node.setPri(null);
    first = node;
    return data;
}
删除尾结点 removeLast

实现思想

1、判断链表是否为空
2、存储尾结点存储的数据
3、更新尾结点为尾结点的前驱节点
4、设置新的尾结点的后继节点为空
5、返回原始尾结点存储的数据
6、size–

实现细节

public T removeLast(){
    if (size == 0){
        throw new RuntimeException("链表为空！");
    }
    T data = last.getData();
    Node<T> node = last.pri;
    node.setNext(null);
    last = node;
    return data;
}
删除指定下标节点remove（int index）

1、判断链表是否为空
2、判断下标是否合法

不合法：

抛出异常

合法【0 - size-1】：

为0 即删除头结点 removeFirst()

为size-1 即删除尾结点 removeLast()

为其他值

1、遍历到指定下标对应节点的前驱节点 left，则当前节点为left的后继节点 temp
2、存储temp存储的数据 data
3、设置left的后继节点值为temp的后继节点
4、设置left的后继节点的前驱节点值为left节点
5、返回原指定下标对应的数据（也可以在返回之前将当前节点的后继值设为空，便于GC回收）
6、size–

实现细节

public T remove(int index){
    if (size == 0){
        throw new RuntimeException("链表为空！");
    }
    //注意添加的时候，下标取不到size，但是添加的位置可以是size，但是删除的时候不行
    if (index < 0 || index > size-1){
        throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
    } else if(index == 0){
        return removeFirst();
    }else {
        Node<T> node = first;
        for (int i = 0; i < index - 1; i++) {
            node = node.next;
        }
        Node<T> temp = node.next;
        if (temp != last){
            T data = temp.getData();
            node.next = temp.next;
            temp.next.pri = node;
            temp.setNext(null);
            return data;
        }else {
            return removeLast();
        }
    }
}

获取指定下标位置节点的数据 getData（int index）

实现思想

1、判断下标是否合法【0 - size-1】
2、处理特殊下标 0 size-1，直接返回头、尾结点存储的数据
3、处理其他下标

遍历到当前下标对应节点，返回对应节点存储的数据

实现细节

public T getData(int index){
    if (index<0 || index>size-1){
        throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
    }else if (size == 0){
        throw new RuntimeException("链表为空");
    }else if (size == 1){
        return first.data;
    }else {
        Node<T> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.data;
    }
}

获取链表长度

getSize()

遍历输出print()

public void print(){
    if (size == 0) {
        System.out.println("该链表为空!");
    }
    Node<T> node = first;
    while (node != null) {
        System.out.print(node.getData() + "\t");
        node = node.next;
    }
    System.out.println();
}

详细遍历输出

依次输出每个节点的直接前驱存储的数据、当前节点存储的数据、后继节点存储的数据（不存在则输出 null）

public void detailPrint(){
    if (size == 0) {
        System.out.println("该链表为空!");
    }
    Node<T> node = first;
    while (node != null) {
        System.out.print("前驱节点值：");
        System.out.printf("%-5s",node.pri == null ? "null\t" : node.pri.getData()+"\t");
        System.out.print("当前节点值：");
        System.out.printf("%-6s",node.getData() + "\t");
        System.out.print("后继节点值：");
        System.out.printf("%-5s",node.next == null ? "null\t" : node.next.getData()+"\t");
        System.out.println();
        node = node.getNext();
    }
    System.out.println();
}

清空链表

public void clear(){
    first.next = null;
    last = first;
}

实现细节

为了方便大家进行测试，下面放了整体实现，欢迎大家测评

package com.jinhuan.chapter04.no4_4.doublyLinkedList;

/**
 * @Author jinhuan
 * @Date 2022/4/19 14:43
 * Description:
 * 实现双向链表
 */
public class DoublelyLinkedList<T> {
    private static int size;
    private Node<T> first;
    private Node<T> last;

    private static class Node<T> {
        private T data;
        private Node<T> pri;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node<T> getPri() {
            return pri;
        }

        public void setPri(Node<T> pri) {
            this.pri = pri;
        }

        public Node<T> getNext() {
            return next;
        }

        public void setNext(Node<T> next) {
            this.next = next;
        }

    }

    public static int getSize() {
        return size;
    }

    /**
     * 添加节点到头部
     * */
    public boolean addFirst(T value){
        Node<T> node = new Node<>(value);
        if (size == 0) {
            first = node;
            last = first;
        }else {
            node.next = first;
            first.pri = node;
            first = node;
        }
        size++;
        return true;
    }
    /**
     * 添加节点到尾部
     * */
    public boolean addLast(T value){
         if (size == 0){
             return addFirst(value);
         }else {
             Node<T> node = new Node<>(value);
             last.next = node;
             node.pri = last;
             last = node;
         }
        size++;
        return true;
    }
    /**
     * 元素添加到指定位置
     * */
    public boolean add(int index,T value){
        if (index < 0 || index > size){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
        } else if(index == 0){
            return addFirst(value);
        }else if (index == size){
            return addLast(value);
        }else {
            Node<T> node = new Node<>(value);
            Node<T> head = first;
            for (int i = 0; i < index-1; i++) {
                head = head.getNext();
            }
            node.next = head.next;
            head.next = node;
            node.pri = head;
            node.next.pri = node;
        }
        size++;
        return true;
    }

    /**
     * 删除头结点
     * */
    public T removeFirst(){
        if (size == 0){
            throw new RuntimeException("链表为空！");
        }
        T data = first.getData();
        Node<T> node = first.next;
        node.setPri(null);
        first = node;
        return data;
    }

    /**
     * 删除尾节点
     * */
    public T removeLast(){
        if (size == 0){
            throw new RuntimeException("链表为空！");
        }
        T data = last.getData();
        Node<T> node = last.pri;
        node.setNext(null);
        last = node;
        return data;
    }

    /**
     * 删除指定下标结点
     * */
    public T remove(int index){
        if (size == 0){
            throw new RuntimeException("链表为空！");
        }
        //注意添加的时候，下标取不到size，但是添加的位置可以是size，但是删除的时候不行
        if (index < 0 || index > size-1){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
        } else if(index == 0){
            return removeFirst();
        }else {
            Node<T> node = first;
            for (int i = 0; i < index - 1; i++) {
                node = node.next;
            }
            Node<T> temp = node.next;
            if (temp != last){
                T data = temp.getData();
                node.next = temp.next;
                temp.next.pri = node;
                temp.setNext(null);
                return data;
            }else {
                return removeLast();
            }
        }
    }

    /**
     * 获取对应下标数据
     * */
    public T getData(int index){
        if (index<0 || index>size-1){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
        }else if (size == 0){
            throw new RuntimeException("链表为空");
        }else if (size == 1){
            return first.data;
        }else {
            Node<T> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node.data;
        }
    }

    /**
     * 清空链表
     * */
    public void clear(){
        first.next = null;
        last = first;
    }

    /**
     * 遍历输出当前所有数据
     * */
    public void print(){
        if (size == 0) {
            System.out.println("该链表为空!");
        }
        Node<T> node = first;
        while (node != null) {
            System.out.print(node.getData() + "\t");
            node = node.next;
        }
        System.out.println();
    }

    /**
     * 详细遍历输出:
     *      前驱节点值
     *      当前节点值
     *      后继节点值
     * */
    public void detailPrint(){
        if (size == 0) {
            System.out.println("该链表为空!");
        }
        Node<T> node = first;
        while (node != null) {
            System.out.print("前驱节点值：");
            System.out.printf("%-5s",node.pri == null ? "null\t" : node.pri.getData()+"\t");
            System.out.print("当前节点值：");
            System.out.printf("%-6s",node.getData() + "\t");
            System.out.print("后继节点值：");
            System.out.printf("%-5s",node.next == null ? "null\t" : node.next.getData()+"\t");
            System.out.println();
            node = node.getNext();
        }
        System.out.println();
    }
}

以上均为本人个人观点，借此分享，希望能和大家一起进步。如有不慎之处，劳请各位批评指正！鄙人将不胜感激并在第一时间进行修改！

Java一步spanclasstoken数据结构

有关一步步带你用Java实现双向链表（超详细）的更多相关文章

  1. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  2. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  3. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  4. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  5. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  6. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  7. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

  8. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

  9. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  10. MIMO-OFDM无线通信技术及MATLAB实现（1）无线信道：传播和衰落 - 2

     MIMO技术的优缺点优点通过下面三个增益来总体概括：阵列增益。阵列增益是指由于接收机通过对接收信号的相干合并而活得的平均SNR的提高。在发射机不知道信道信息的情况下，MIMO系统可以获得的阵列增益与接收天线数成正比复用增益。在采用空间复用方案的MIMO系统中，可以获得复用增益，即信道容量成倍增加。信道容量的增加与min(Nt,Nr)成正比分集增益。在采用空间分集方案的MIMO系统中，可以获得分集增益，即可靠性性能的改善。分集增益用独立衰落支路数来描述，即分集指数。在使用了空时编码的MIMO系统中，由于接收天线或发射天线之间的间距较远，可认为它们各自的大尺度衰落是相互独立的，因此分布式MIMO

随机推荐