【Java 数据结构】双向链表

男娘i 2024-04-01 12:41 56阅读 0赞

![b4e6ca8983a34017be11d504193bfa0e.png][] 篮球哥温馨提示：编程的同时不要忘记锻炼哦！

## 圆圆的脑袋，大大耳朵，天天敲代码，找找找bug ##

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

**目录**

1、什么是双向链表

2、实现一个双向链表

2.1 实现前的约定

2.2 addFirst 方法

2.3 addLast 方法

2.4 addIndex 方法

2.5 contains 方法

2.6 removeAllKey 方法

2.7 clear 方法

2.8 size 方法

3、LinkedList 的学习

3.1 认识下 LinkedList

3.2 LinkedList 的构造方法

3.3 LinkedList 的遍历

4、ArrayList 和 LinkedList 的区别

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

## **1、什么是双向链表** ##

上期我们实现了一下单链表，在Java(1.8)中，链表为 LinkedList，而底层是一个双向链表，跟 ArrayList 一样，LinkedList 也实现了 List 接口，这里我们画一个图，让大家简单见识下双向链表：

![4ff9ead45d3d46cfb6dc0edf323bb5b3.png][]如图我们可以看出，双向链表最少有三个域，分别是数据域和两个指针域，分别指向节点的前驱和后继，第一个节点没有前驱，最后一个节点没有后继。

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

## **2、实现一个双向链表** ##

### 2.1 实现前的约定 ###

链表的每个元素是一个节点，我们仍然采用内部类的方式，既然是双向的，那么我们还需要在外部定义一个head和last，分别为头节点和尾节点的引用。

public class MyLinkedList {
    
        private class ListNode {
            private int val; //数据域
            private ListNode prev; //前指针域
            private ListNode next; //后指针域
    
            private ListNode(int val) {
                this.val = val;
            }
        }
        private ListNode head; //头节点引用
        private ListNode last; //尾节点引用
        private int size; //链表有效数据个数
    }

同时我们还要实现以下几个方法：

public void addFirst(int data); //头插法
    
    public void addLast(int data); //尾插法
    
    public boolean addIndex(int index,int data) //任意位置插入,第一个数据节点为0号下标
    
    public boolean contains(int key); //查找是否包含关键字key是否在单链表当中
    
    public void removeAllKey(int key); //删除所有值为key的节点
    
    public void clear(); //清空链表
    
    public int size(); //得到链表的长度

### 2.2 addFirst 方法 ###

//头插法
    public void addFirst(int data) {
        ListNode newNode = new ListNode(data);
        // 链表为空的情况
        if (this.head == null) {
            this.head = newNode;
            this.last = newNode;
            this.size++;
            return;
        }
        newNode.next = this.head; //新节点的后一个为头节点
        this.head.prev = newNode; //头节点的前一个为新节点
        this.head = newNode; //新节点成为新的头节点
        this.size++;
    }

与单链表不同，由于双向链表有头尾节点引用，所以这里我们要在第一次插入元素的时候进行特殊处理，当第一次插入元素我们需要将头尾节点的引用都指向这个节点，后续插入只需要改变头节点的引用即可，最后插入完成别忘记链表有效节点个数自增1哦！

### 2.3 addLast 方法 ###

//尾插法
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        // 链表为空的情况
        if (this.head == null) {
            this.head = newNode;
            this.last = newNode;
            this.size++;
            return;
        }
        newNode.prev = this.last; //新节点的前一个为尾节点
        this.last.next = newNode; //尾节点的后一个为新节点
        this.last = newNode; //新节点成为新的尾节点
        this.size++;
    }

与头插法相差不多，无非就是需要修改尾节点的引用，以及注意新节点的指针域指向问题，这里小伙伴们可以结合我的代码注释，尝试去理解，配合画图，相信你就能掌握好头插法和尾插法了！

### 2.4 addIndex 方法 ###

//任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data) {
        // 判断index下标的合法性
        if (index < 0 || index > this.size) {
            return false;
        }
        // index为0表示头插
        if (index == 0) {
            addFirst(data);
            return true;
        }
        // index为size长度表示尾插
        if (index == this.size) {
            addLast(data);
            return true;
        }
    
        //其他情况为中间插入
        ListNode newNode = new ListNode(data);
        ListNode cur = this.head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        newNode.prev = cur.prev; //新节点的前一个为cur的前一个
        newNode.next = cur; //新节点的后一个为cur
        cur.prev.next = newNode; //cur的前节点的后一个为新节点
        cur.prev = newNode; //cur的前节点为新节点
        this.size++;
        return true;
    }

对于在指定位置插入节点来说，如果给定的 index 位置大于我们的有效节点个数呢？也就是说假设我链表只有 5 个节点，你要在 8 位置插入元素显然是不合法的，其次，如果要在负数的位置插入那更不合法，所以我们要对 index 做判断，往后走我们还可以考虑两个点，如果index == 0 或者 index == size()，那么也就是对应着我们的头插和尾插，那么我们直接调用前面写的头插尾插方法即可，代码接着往后走，剩下的就是中间插入节点的情况了，逻辑很简单，首先要找到 index 对应的节点，接着改变相关节点指针域的指向即可，这里可以结合着代码以及注释，下来画图进行分析。

### 2.5 contains 方法 ###

//查找是否包含关键字key是否在双链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

这个方法跟我们之前写单链表的时候相差无几，相信有了前面单链表的基础，这个简直是信手拈来了吧，无非就是遍历这个链表，只要 cur 没有遍历到 null，也就是没有到最后一个节点的 next 位置，我们就遍历找有没有 key，找到了返回 true 找不到返回 false 咯！

### 2.6 removeAllKey 方法 ###

//删除所有值为key的节点
    public void removeAllKey(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                //如果被删除cur是头节点
                if (cur == this.head) {
                    //只有一个节点的情况
                    if (this.head.next == null) {
                        this.head = null;
                        this.last = null;
                    } else {
                        cur.next.prev = null; //cur的后节点的前节点指针域改为null
                        this.head = cur.next; //头节点变成cur的下一个节点
                    }
                } else {
                    //如果被删除cur是尾节点
                    if (cur == this.last) {
                        this.last = cur.prev; //尾节点变成cur的前节点
                    } else {
                        cur.next.prev = cur.prev; //cur的后节点的前节点指针域改为cur的前节点
                    }
                    cur.prev.next = cur.next; //cur的前节点的后节点指针域改为cur的后节点
                }
                this.size--;
            }
            cur = cur.next;
        }
    }

要删除所有值为 key 的节点，这道题思想不难，还是遍历链表嘛，如果值一样，修改相关节点引用即可，但是问题来了，删除头节点和尾节点，和删除中间节点的修改指向逻辑可不一样，所以我们要分别处理，分开处理这三种情况之后，如果只有一个节点的情况呢？也得处理，于是就有了我们上面的代码，当然可以有很多种写法，你只要把各种情况捋清楚了就好，至于修改指针域指向的逻辑画画图就能理解了！

### 2.7 clear 方法 ###

public void clear() {
        // 遍历链表
        ListNode cur = this.head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        this.head = null;
        this.last = null;
        this.size = 0;
    }

双向链表的清空方法可不能直接头节点置空，因为直接头节点置空的话，别忘了Java中是某一块空间没有被引用的时候，才会被自动回收掉，但是这是双向链表，中间节点都是互相引用的，所以我们需要每个都手动置空，我们要定义一个curNext引用，指向cur的下一个，防止置空cur的指针域的时候，cur找不到下一个节点了！最后别忘了 size 要等于 0，不然会出问题的！\\(￣︶￣\*\\))

### 2.8 size 方法 ###

这个方法还是很很简单的，直接 return this.size; 不就可以了吗？

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

## **3、LinkedList 的学习**  ##

### 3.1 认识下 LinkedList ![27461ff8c9384efba0094b2f12ad8bb3.png][] ###

>  *  LinkedList 并没有像 ArrayList 一样实现 RandomAccess 接口，所以 LinkedList 并不支持随机访问
>  *  LinkedList 实现了Cloneable接口，表明 LinkedList 是可以clone的
>  *  LinkedList 实现了Serializable接口，表明 LinkedList 是支持序列化的
>  *  LinkedList 在任意位置插入和删除时效率比较高，时间复杂度为O(1)

**接着来看一看 LinkedList 里面的成员变量：**

### ![91dc9a76f34a4e84a616e90a42b98ccb.png][]3.2 LinkedList 的构造方法 ###

Java 中的 LinkedList 提供了两个构造方法：

<table style="width:579px;"> 
 <thead> 
  <tr> 
   <th style="width:292px;">方法</th> 
   <th style="width:285px;">解释说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="width:292px;"><span style="color:#e6b223;">LinkedList</span>()</td> 
   <td style="width:285px;">无参构造</td> 
  </tr> 
  <tr> 
   <td style="width:292px;"><span style="color:#e6b223;">LinkedList</span>(Collection&lt;? <span style="color:#e6b223;">extends</span> <span style="color:#1c7331;">E</span>&gt; c)</td> 
   <td style="width:285px;">使用其他集合容器中元素进行构造</td> 
  </tr> 
 </tbody> 
</table>

使用构造方法例子：

public static void main(String[] args) {
        // 构造一个空的双向链表
        LinkedList<Integer> list1 = new LinkedList<>(); // 直接构造
        List<Integer> list2 = new LinkedList<>(); // 向上转型
    
        // 使用ArrayList构造LinkedList
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        LinkedList<Integer> list3 = new LinkedList<>(arrayList);
        List<Integer> list4 = new LinkedList<>(arrayList);
    }

至于LinkedList当中还有特别多的方法，小伙伴们下去可以自行查阅手册，这里就不多讲述了！

### 3.3 LinkedList 的遍历 ###

public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i <= 5; i++) {
            list.add(i); //add默认是尾插
        }
        // 方法1：使用foreach遍历
        for (int x : list) {
            System.out.print(x + " ");
        }
        System.out.println();
    
        // 方法2：使用迭代器遍历->正向遍历
        ListIterator<Integer> it = list.listIterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
    
        // 方法3：使用迭代器遍历->反向遍历
        ListIterator<Integer> rit = list.listIterator(list.size());
        while (rit.hasPrevious()) {
            System.out.print(rit.previous() + " ");
        }
        System.out.println();
    }

迭代器后期也会逐步接触到，这里能看得懂就ok了！

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

## **4、ArrayList 和 LinkedList 的区别** ##

首先我们来说它们的相同点，都是Java中的集合，都是顺序结构，都实现了 List 接口等其他的接口。

重点是他们的区别，也就是不同点！

*  从存储的角度来说，ArrayList 一定是空间连续的，因为底层是数组，数组是一块连续的存储空间，而 LinkedList 的空间不一定连续，每个节点是依靠节点的指针域进行连接起来的。
 *  从访问元素的角度来说，ArrayList 支持下标随机访问，而 LinkedList 并不支持，而且时间复杂度还是 O(n)。
 *  插入和删除的角度来说，ArrayList 尾插，尾删还好，其他都需要挪动元素了，效率低，时间复杂度是 O(n)，而对于 LinkedList 来说，只需要修改指向即可，时间复杂度是 O(1)。
 *  从空间的角度来说，ArrayList 容量不够需要扩容，而 LinkedList 并没有扩容的概念，每次插入都会 new 一个新的节点。
 *  从应用场景的角度来说(目前的知识层面上)，ArrayList 更适合频繁用到随机访问，而LinkedList 更适合频繁的插入和删除。

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

**下期预告：【Java 数据结构】栈**

[b4e6ca8983a34017be11d504193bfa0e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ddfbf027db584708a7219e567fbc3f82.png
[4ff9ead45d3d46cfb6dc0edf323bb5b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/eb2a94a6e82641388167ae012396bed9.png
[27461ff8c9384efba0094b2f12ad8bb3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/402ba9c8ebaf4f7da6f0cfe2cac0fcb1.png
[91dc9a76f34a4e84a616e90a42b98ccb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1e1275cb4ed44095ac63891d2517cd92.png