Java数据结构——————双向链表（详细图解，增删改查详细实现）

系统管理员 2023-10-02 12:22 7阅读 0赞

###  ###

![b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png][]

**目录**

1.什么是双向链表？

2.双向链表的基本功能和结构

3.双向链表基本功能详细图解代码实现

1.清空，判空，获得长度功能实现

2.获取第一个元素和最后一个元素

3.添加元素t

4.向指定位置i插入元素t

5.获取指定位置i处的元素

6.找到元素t第一次出现的位置

7.删除位置i的元素，并返回该元素

--------------------

## 1.什么是双向链表？ ##

要明白什么是双向链表，我们首先得明白什么是链表和什么是单链表？如果对于这个还有疑惑的推荐我的这篇博客，里面有非常详细的图解和代码实现。[https://blog.csdn.net/m0\_57487901/article/details/120871022?spm=1001.2014.3001.5501][https_blog.csdn.net_m0_57487901_article_details_120871022_spm_1001.2014.3001.5501]

首先我们通过一张直观的图对比单链表和双向链表

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16][]

通过名字我们就可知它之所以叫双向链表，就是它可以向两头遍历，任意一个结点我可以得到它的前结点和后一个结点。不像单链表具有单向遍历的局限性，而且双向链表同时记录了尾结点last，这样我们每次想得到最后一个结点就不需要从头遍历到末尾了，如果链表很长的话，这样每次循环查询是非常浪费时间的。

## 2.双向链表的基本功能和结构 ##

public class TwoWayLinkList<T> implements Iterable {
        //首结点
         Node head;
        //链表的长度
         int N;
         Node last;
        //结点类
        public class Node {
            //数据域
            public T item;
            //头指针
            public Node pre;
            //尾指针
            public Node next;
    
            public Node(T item, Node pre, Node next) {
                this.item = item;
                this.pre = pre;
                this.next = next;
            }
        }
        //初始化链表
        public TwoWayLinkList() {
            //初始化头结点和尾结点
            this.head = new Node(null, null, null);
            this.last = new Node(null, null, null);
            //初始化元素个数
            N = 0;
        }

解析：学习数据结构，我们在学习它的基本功能前，一定要明白它的逻辑结构。代码中，首先有一个内部类Node表示为结点，因为一个结点具有指针域和数据域，所以需要用一个类来表示，Node里面首先有表示存放数据的item，因为不清楚存放的数据是什么类型，所以用泛型T表示。同时有两个Node类型的变量pre和next分别记录指向前一个结点和后一个结点。在链表中有两个个Node类型的变量head和last分别表示头指针和尾指针，同时有一个int类型的N记录成员个数。初始化时，只需要建立头结点和尾结点，内部属性都为null，再让N为0即可。

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td> <pre>public void clear() 
</pre> </td> 
   <td> <pre>清空链表</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public int getLength() 
</pre> </td> 
   <td> <pre>获取链表长度</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public boolean isEmpty()</pre> </td> 
   <td> <pre>判断链表是否为空</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public T getFirst()</pre> </td> 
   <td> <pre>获取第一个元素</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public T getLast()</pre> </td> 
   <td> <pre>获取最后一个元素</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public void add(T t)</pre> </td> 
   <td> <pre>插入元素t</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public void insert(int i,T t)</pre> </td> 
   <td> <pre>向指定位置i位置插入元素t</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public T get(int i)</pre> </td> 
   <td> <pre>获取指定位置i处的元素</pre> </td> 
  </tr> 
  <tr> 
   <td> <pre>public int indexOf(T t)</pre> <pre>public T remove(int i)</pre> <p></p> </td> 
   <td> <pre>找到元素t第一次出现的位置</pre> <pre>删除位置i处的元素,并返回该元素</pre> </td> 
  </tr> 
 </tbody> 
</table>

看上去很多API功能需要实现，但其实大部分都很简单，只要理解就可以自己写出来。

## 3.双向链表基本功能详细图解代码实现 ##

### 1.清空，判空，获得长度功能实现 ###

//清空链表
        public void clear() {
            this.head.next = null;
            this.last = null;
            this.N = 0;
        }
    
        //获取链表长度
        public int getLength() {
            return N;
        }
    
            //判断链表是否为空
        public boolean isEmpty() {
            return N == 0;
        }

解析：这里我需要提醒大家，**虽然头结点我们一般不存储元素，但是尾结点我们是可以存储的元素的，不要硬性思维。**清空时，我们需要让头结点的next为null，这样无法从头进入链表，尾结点因为也是存储数据的，所以得直接让last为null，同时让N为0。获得链表长度直接返回N。判空也是直接返回N是否等于0的值即可。

### 2.获取第一个元素和最后一个元素 ###

//获取第一个元素
        public T getFirst() {
            //需要判断链表是否为空
            if (isEmpty()) {
                return null;
            }
            return head.next.item;
        }
    
        //获取最后一个元素
        public T getLast() {
            if (isEmpty()) {
                return null;
            }
            return last.item;
        }

解析：无论是获取哪个，我们都需要获取判空操作，养成好习惯，代码一定要考虑进所有情况，否则容易出异常。因为是获取元素，所以我们返回的一定是某个结点的item，第一个元素，说明就是头结点的next的item，最后一个元素就是返回last的item就好。

### 3.添加元素t ###

//插入元素t
            public void add(T t) {
                //如果链表为空
                if (isEmpty()) {
                    //创建新结点
                    Node newNode = new Node(t, head, null);
                    //让新节点为尾结点
                    last = newNode;
                    //让头结点指向尾结点
                    head.next = last;
                } else {
                    //如果链表不为空
                    Node oldLast = last;
                    //创建新节点
                    Node newNode = new Node(t, oldLast, null);
                    //让当前的尾结点指向新结点
                    oldLast.next = newNode;
                    //让新节点成为尾结点
                    last = newNode;
                }
                N++;
            }

解析：同样我们需要对链表进行判空操作，如果链表为空，我们需要new一个新节点存入数据t，因为就它一个结点，所以我们把它赋值给last，让它成为尾结点，然后让head指向它即可。如果链表不为空，我们首先需要用一个结点oldLast记录旧的尾结点，同时new一个新节点放入数据t，让它成为新的尾结点last，同时让旧的尾结点oldLast指向它。最后无论怎样都记得让N++。

### 4.向指定位置i插入元素t ###

//向指定位置i位置插入元素t
        public void insert(int i,T t){
            //找到i位置的前一个节点
            Node a=head;
            for (int j = 0; j < i; j++) {
                a=a.next;
            }
            //找到i位置的节点
            Node curr = a.next;
            //创建新节点
            Node newNode = new Node(t, a, curr);
            //让i位置的前一个节点的下一个节点变为新节点
            a.next=newNode;
            //让i位置的前一个节点变为新节点
            curr.pre=newNode;
            //元素个数加1
            N++;
        }

具体的步骤通过下图就能明白，一定要搞清楚每一步的顺序，否则很容易出错，自己可以草稿画图模拟。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

### 5.获取指定位置i处的元素 ###

//获取指定位置i处的元素
        public T get(int i){
            Node a=head;
            for (int j = 0; j <=i; j++) {
                a=a.next;
            }
            return a.item;
        }

解析：和单链表相同，从头结点开始遍历打i处，返回item即可。

### 6.找到元素t第一次出现的位置 ###

//找到元素t第一次出现的位置
        public int indexOf(T t){
            Node a=head;
            for (int i = 0; i < N; i++) {
                a=a.next;
                if(a.item==t) return i;
            }
            return -1;
        }

解析：单单链表一致，从头结点开始遍历，同时判断是否是查找的元素，如果找到返回位置i，否则循环结束后返回-1。

### 7.删除位置i的元素，并返回该元素 ###

//删除位置i处的元素,并返回该元素
        public T remove(int i){
            Node a=head;
            //找到i节点
            for (int j = 0; j <= i; j++) {
                a=a.next;
            }
            a.next.pre=a.pre;
            a.pre.next=a.next;
            N--;
            return a.item;
        }

如下图解即可明白，主要是要分清步骤，不要搞混，返回的是值不是结点。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

**总结：双向链表与单链表虽然有所区别，但方法的实现大同小异，我们也应该熟练掌握，多画图更易帮助我们理解，都是基础的知识。**

**有错的地方还望在评论区提出，水平有限**

![f704dcb374c688a57eae9f5dd97c3655.png][]

[b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png]: https://img-blog.csdnimg.cn/img_convert/b3cd3475ec6ca0a6ff7b57fa6ed26d7f.png
[https_blog.csdn.net_m0_57487901_article_details_120871022_spm_1001.2014.3001.5501]: https://blog.csdn.net/m0_57487901/article/details/120871022?spm=1001.2014.3001.5501
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/89d5c2a3ec354c4b8f47f4b84b928b84.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5omn5qKX,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/d74a33b86aed485b8632326c6d3fa4ec.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5omn5qKX,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5omn5qKX_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/9e3515d8ecdc4868ac07a28e33b1ef01.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5omn5qKX,size_20,color_FFFFFF,t_70,g_se,x_16
[f704dcb374c688a57eae9f5dd97c3655.png]: https://img-blog.csdnimg.cn/img_convert/f704dcb374c688a57eae9f5dd97c3655.png