添加链接描述### “不要把世界让给你讨厌的人”

1. 前言

在上篇博客我们主要介绍了单链表的实现以及练习题，本篇博客我们主要讲双向链表也是Java数据结构中自带的链表！跟着小编的脚步一起学习吧！

---

2. 正文

1. 单向链表的循环链表

在上篇博客，我们留了一个小尾巴就是单向链表中的循环列链表的部分知识，下面直接看练习题 环形链表，先读题与上篇博客的不同点在于这次要返回链表刚开始入环的节点！小编再举一个例子：”假如你和你女朋友约定好中午去广场散步，到了中午准备出门时，你和你女打算比赛谁先到广场，你开始提速你的速度是你女朋友速度的二倍，你走到了广场发现女朋友还没到广场，这时你准备围着广场走圈边走边等着你女朋友过来，当你第二次走到同样的位置时，你碰到了你的女友！

fast每次走两步，slow每次走一步，最后fast套slow一圈，我们根据这个图可以理解上面的例子，那么我们要这个图有什么用呢？
我们推导出X=Y这个等式尤为重要！如果fast刚好从相遇点走，slow从起点走，那么它们就会在入口点相遇，这个点就是我们要找的点，这里我们只考虑了广场很大的情况，fast只套了1圈，如果广场很小，那么fast会套N圈，这时候我们还会推导出一个式子！X+NC+C-Y=2 *（X+C-Y），化简我们可以得到X=(N-1)C+Y,根据我们推导的公式我们就可以完成代码了

我们slow和fast经过循环完找到了相遇点跳出循环，如果是因为没有环才相遇则return null，有环的话再让slow到头节点，slow和fast以相同速度走最终相遇。这样我们的题就完成啦！

---

2. LinkedList数据结构

2.1 什么是LinkedList

还是看这张图LinkedList就是Java原本的链表数据结构，我们之前实现的链表都是单链表，而LinkedList是一个双向链表，更方便操作
这就是一个双向链表的结构，我们可以看到它就是比单向链表多了一个pre域用来存放前一个的地址！！有了单链表的基础学习这个还是非常容易的。

---

2.2 LinkedList自己实现

在学习新的数据结构之前我们都要模拟实现一遍这个数据结构！！我们先来看看LinkedList的方法
还是非常非常多的，这里我们就挑主要的实现，因为有了实现单链表的基础，我们这里就不浪费太多时间

1. 创建一个用来被实现的接口存放LinkedList方法
   
   定义一个类实现这个接口

重写了接口的方法，并定义了一个新的内部类。

因为是双向链表我可以定义一个头和一个尾

---

2. 完成 public void display()方法，这个方法的完成很简单与单链表的实现类似，定义一个cur遍历链表便可以输出

    public void display() {
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }

这样就完成了！

---

3. 完成 public int size()方法

    public int size() {
        int len=0;
        ListNode cur=head;
        while (cur!==null){
            len++;
            cur=cur.next;
        }
        return len;
    }

这个也非常简单小编不赘述了。

---

4. 完成 public boolean contains(int key)方法

  public boolean contains(int key) {
         ListNode cur=head;
         while (cur!=null){
             if (cur.val==key){
                 return true;
             }
             cur=cur.next;
         }
         return false;
    }

easy

---

5. 完成 public void addFirst(int data) 方法，这是头插法，我们单链表也实现过这个方法，这里我们只需要注意一点
   直接代码实现

   public void addFirst(int data) {
        ListNode node=new ListNode(data);
        if(head==null){
            head=last=node;
        }else {
            node.next = head;
            head.pre = node;
            head = node;
        }
    }

只需要注意head为空的情况

---

6. 完成 public void addLast(int data)方法，在我们单链表的学习中尾差法要遍历链表至最后一个才可以进行插入，而双向链表有last那么我们就可以直接实现了！

    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = last = node;
        } else {
            last.next = node;
            node.pre = last;
            last = node;
        }
    }

也是非常easy

---

7. 完成 public void addIndex(int index, int data)方法，这里是指定位置插入，与单链表不同的是我们要注意pre域的取值
   

单链表实现中我们要将cur遍历至1位置因为没有pre域，而这里就会很方便

    public void addIndex(int index, int data) {
        ListNode cur=findIndex(index);
        ListNode node = new ListNode(data);
        int len=size();
        if (index==0){
            addFirst(data);
            return;
        }
        if(index==len){
            addLast(data);
            return;
        }
      
        node.next=cur;
        node.pre=cur.pre;
        cur.pre.next=node;
        cur.pre=node;
    }
private ListNode findIndex(int index){
    ListNode cur=head;
    while (index!=0) {
        cur = cur.next;
        index--;
    }
    return cur;
}

这里用方法封装了一下，使代码更清晰

---

8. 完成 public void remove(int key)方法，这里的删除我们也是将cur走到删除点来操作，单链表是走到删除点的前面操作，注意pre域即可框架搭建好了接着我们判断情况，如果删的是尾巴那么cur.next.pre就不存在了！！如果删掉的头结点也要有变化，所以要优化

    public void remove(int key) {
        ListNode cur = head;
        if (head == null) {
            return;
        }
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    head.pre = null;
                } else {
                    cur.pre.next = cur.next;
                    if (cur == last) {
                        cur.pre.next = cur.next;
                        last = last.pre;
                    } else {
                        cur.next.pre = cur.pre;
                    }
                    return;
                }
            } else {
                cur = cur.next;
            }
        }
    }

---

9. 完成public void removeAllKey(int key)方法,对于双向链表这个方法的实现就非常简单了

 public void removeAllKey(int key) {
        ListNode cur = head;
        if (head == null) {
            return;
        }
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    head.pre = null;
                } else {
                    cur.pre.next = cur.next;
                    if (cur == last) {
                        cur.pre.next = cur.next;
                        last = last.pre;
                    } else {
                        cur.next.pre = cur.pre;
                    }
                }
            } else {
                cur = cur.next;
            }
        }
    }

我们只需要把删除的方法中的return去掉即可！！因为他会不断的查找是否有删除的节点！

---

10. 完成 public void clear()方法，这里也是直接遍历链表都指向为空，最后将head和last都至为空即可

    public void clear() {
        ListNode cur=head;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=null;
            cur.pre=null;
            cur=curN;
        }
        head=last=null;
    }

这样就完成啦！

---

以上就是自己实现的LinkedList的操作，有了单向链表的基础也是很简单的，这里是代码详解🌹

---

2.2 LinkedList方法

1. 具体方法
   我们可以看到非常之多，我们现在只学习了LinkedList单纯作为链表使用，后面学习完栈和队列它就有更多的功能了！

---

2. 声明
   我们可以直接通过引用声明或者通过接口，LinkedList实现List接口所以可以声明。

---

3. 构造方法
   与顺序表的构造方法极为相似，这里不过多介绍了

方法	解释
LinkedList()	无参构造
public LinkedList(Collection<? extends E> c)	使用其他集合容器中元素构造List

---

4. 遍历
   这里LinkedList与顺序表ArrayList的遍历一样也不过介绍，不会的小伙伴看这里

（1）直接遍历

（2）foreach遍历

（3）使用迭代器遍历

---

3. ArrayList与LinkedList区别

对比总结表

特性/维度	ArrayList	LinkedList
底层数据结构	动态数组	双向链表
随机访问性能	极快 (O(1)) 通过索引直接计算内存地址。	慢 (O(n)) 需要从链表头或尾开始遍历。
头部插入/删除性能	慢 (O(n)) 需要移动后续所有元素。	极快 (O(1)) 只需修改头节点的指针。
尾部插入/删除性能	快 (O(1)) 如果容量足够，直接追加。 扩容时是 O(n)。	极快 (O(1)) 通过尾指针直接操作。
中间插入/删除性能	慢 (O(n)) 需要移动后续部分元素。	平均为 O(n) 需要先遍历到指定位置 (O(n))，但操作本身快 (O(1))。
内存占用	较小 只存储数据和数组容量，内存开销小。	较大 每个元素（节点）都需存储前后节点的指针。
内存空间利用	连续空间 有利于 CPU 缓存，性能更高。	碎片化空间 节点在内存中不连续。

---

3. 结语

**以上就是本文主要的内容，本文主要介绍LinkedList和LinkedList的实现比较简单，下一篇是关于栈和队列部分知识，请大家敬请期待！！有不明白的地方可以留言小编会回复，希望读者们多提建议，小编会改正，共同进步！谢谢大家。🌹🌹🌹

---

今天是2025年10月24日，小编祝程序猿们和未来的程序猿们节日快乐🌹🐱🐱🐱