Java 实现双向链表：LinkedList 模拟与源码解析

在之前的系列中，我们主要探讨了单向链表。本期我们将深入双向链表（Doubly Linked List），并尝试用 Java 模拟实现一个 MyLinkedList，同时对比 JDK 原生 LinkedList 的用法。

一、LinkedList 的模拟实现

双向链表的每个节点包含三个域：val 存储数据，prev 指向上一个节点，next 指向下一个节点。相比单向链表，它支持双向遍历，但在插入删除时指针操作稍显复杂。

我们需要定义一个内部类 ListNode 和外部类 MyLinkedList，并实现基础接口 IList。

public class MyLinkedList implements IList {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next; // 修正：原名为 head，此处应为 next
        
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head; // 链表头
    public ListNode last; // 链表尾

    @Override
    public void addFirst(int data) { }

    @Override
    public void addLast(int data) { }

    @Override
    public void addIndex(int index, int data) { }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) { }

    @Override
    public void removeAllKey(int key) { }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void display() { }

    @Override
    public void clear() { }
}

接口定义如下：

public interface IList {
    void addFirst(int data);
    void addLast(int data);
    void addIndex(int index, int data);
    boolean contains(int key);
    void remove(int key);
    void removeAllKey(int key);
    int size();
    void display();
    void clear();
}

1.1. 头插法

头插法相对直观，新节点的 next 指向当前头节点，旧头节点的 prev 指向新节点，最后更新 head 引用。

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

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

测试代码：

public class Main {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addFirst(50);
        myLinkedList.addFirst(40);
        myLinkedList.addFirst(30);
        myLinkedList.display(); // 输出：30 40 50
    }
}

顺便补充长度统计和元素查找功能：

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

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

1.2. 尾插法

尾插法逻辑与头插法类似，只是操作对象变成了 last 指针。

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

1.3. 插入中间节点

在指定位置插入需要处理四个引用关系。注意修改顺序，避免覆盖导致断链。通常先绑定新节点的后继，再调整前驱。

@Override
public void addIndex(int index, int data) {
    int len = size();
    if (index < 0 || index > len) {
        throw new RuntimeException("双向链表位置不合法:" + index);
    }
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == len) {
        addLast(data);
        return;
    }

    ListNode node = new ListNode(data);
    ListNode cur = findIndex(index);
    
    // 关键四步：先连后，再连前
    node.next = cur;
    cur.prev.next = node;
    node.prev = cur.prev;
    cur.prev = node;
}

private ListNode findIndex(int index) {
    ListNode cur = head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}

1.4. 删除某个节点

删除中间节点只需两行代码调整前后指针。但需特殊处理头节点和尾节点的情况，尤其是当链表仅剩一个节点时，要确保 last 也置空。

@Override
public void remove(int key) {
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == key) {
            // 删除头节点
            if (cur == head) {
                head = head.next;
                if (head == null) {
                    last = null;
                    return;
                }
                head.prev = null;
            }
            // 删除尾结点
            else if (cur == last) {
                last = last.prev;
                last.next = null;
            }
            // 删除中间节点
            else {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }
            return;
        }
        cur = cur.next;
    }
}

1.5. 删除所有为 key 的元素

此方法只需在遍历时持续检查，若匹配则执行删除逻辑，且无论是否删除成功都继续向后移动指针。

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

二、LinkedList 的使用

2.1. 什么是 LinkedList

JDK 中的 LinkedList 实现了 List 和 Deque 接口，底层同样是双向链表结构。

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

2.2. LinkedList 的使用

直接实例化即可调用丰富的 API，如 addFirst, addLast, removeFirst 等。

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.addFirst(10);
        linkedList.addLast(20);
        System.out.println(linkedList); // [10, 20]
    }
}

查看源码可知，add(E e) 方法内部调用了 linkLast 或 linkBefore，逻辑与我们手写的一致。

常用操作示例：

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(1); list1.add(2); list1.add(3);
        list1.add(3, 100); // 下标 3 处插入
        
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.add(11); list2.add(22);
        list1.addAll(2, list2); // 从下标 2 开始添加
        
        list1.remove(2);       // 删除下标 2 元素
        list1.removeFirst();   // 删除头元素
        list1.removeLast();    // 删除尾元素
        
        System.out.println(list1.get(2));
        list1.set(0, 20);      // 修改元素
        System.out.println(list1);
    }
}

三、ArrayList 和 LinkedList 的区别

不同点	ArrayList	LinkedList
存储空间	物理上连续	逻辑连续，物理上不连续
随机访问	支持 O(1)	不支持，需遍历 O(n)
头插/尾插	需搬移元素，效率低 O(n)	仅需改变指向，O(1)
扩容机制	空间不足时扩容	无容量概念，按需分配

在实际开发中，若频繁查询索引，首选 ArrayList；若频繁在头部或中间插入删除，LinkedList 更合适。