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

4. 指定位置插入

双向链表可以找到前一个节点，所以可以让 cur 直接走到想要插入的位置，先判断位置是否合法，然后开始插入，先绑定后面让新节点的 next 指向 cur 节点的地址，然后让前一个节点的 next 指向新的节点的地址，在将新节点的前驱改为 cur 的前驱，cur 的前驱改为新节点。

public void addIndex(int index, int data) {
    // 检查 index 的合法性
    checkIndex(index);
    // 特殊位置处理
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size()) {
        addLast(data);
        return;
    }
    // 指定插入
    ListNode cur = searchIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur;
    cur.prev.next = node;
    node.prev = cur.prev;
    cur.prev = node;
}

// 寻找位置
private ListNode searchIndex(int index) {
    ListNode cur = head;
    while (index != 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}

// 自定义异常
private void checkIndex(int index) {
    if (index < 0 || index > size()) {
        throw new IllegalArgumentException("index 位置不合法：" + index);
    }
}

5. 删除值为 key 的节点

先遍历，找到所要删除的那个节点，当 cur 走到要删除的节点时，常规操作：cur.next.prev = cur.prev; cur.prev.next = cur.next;但还有其他情况：比如要删除的是头节点或者尾节点，只要一个节点的情况，具体操作看下面的代码详解。

public void remove(int key) {
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == key) {
            // 开始删除
            if (cur == head) {
                // 删除的时头节点
                head = head.next;
                // 如果只有一个节点，head 为空，它的前驱就会空指针异常，所以判断一下
                if (head != null) {
                    head.prev = null;
                }
            } else {
                // 不是头节点
                if (cur == last) {
                    // 删除的是尾节点
                    cur.prev.next = cur.next;
                    last = last.prev;
                } else {
                    // 正常情况：中间节点
                    cur.next.prev = cur.prev;
                    cur.prev.next = cur.next;
                }
            }
            return;
        }
        cur = cur.next;
    }
}

6. 删除所有值为 key 的节点

只要将上面的代码中 return 去掉，就能删除所有值为 key 的节点，删完一个后不返回，继续遍历，直到全部删除。

public void removeAllKey(int key) {
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == key) {
            // 开始删除
            if (cur == head) {
                // 删除的时头节点
                head = head.next;
                // 如果只有一个节点，head 为空，它的前驱就会空指针异常，所以判断一下
                if (head != null) {
                    head.prev = null;
                }
            } else {
                // 不是头节点
                if (cur == last) {
                    // 删除的是尾节点
                    cur.prev.next = cur.next;
                    last = last.prev;
                } else {
                    // 正常情况：中间节点
                    cur.next.prev = cur.prev;
                    cur.prev.next = cur.next;
                }
            }
        }
        cur = cur.next;
    }
}

7. 清空链表

【方法一：】直接将头和尾置空

public void clear() {
    head = last = null;
}

【方法二：】将一个一个的节点置空

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

三、LinkedList

1. LinkedList 的概念

LinkedList 使用双向链表结构，实现了 List 接口。在任意位置插入和删除元素时效率较高，时间复杂度为 O(1)。

2. 构造方法

方法说明表格

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    List<Integer> list1 = new LinkedList<>();
    List<Integer> list2 = new ArrayList<>();
    list.add(1); // 默认尾插
    list.add(11);
    list.add(12);
    list.add(13);
    System.out.println(list);
}

3. LinkedList 常用方法

4. LinkedList 遍历

4.1 直接打印

System.out.println(list);

4.2 for-each 遍历

for (Integer x : list) {
    System.out.println(x + " ");
}

4.3 迭代器遍历

// 迭代器遍历
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    System.out.println(it.next() + " ");
}
// 迭代器遍历：专门遍历 List
ListIterator<Integer> listIterator = list.listIterator();
// 可以给参数，从 index 开始打印
while (listIterator.hasNext()) {
    System.out.println(listIterator.next() + " ");
}
// 反向迭代器
ListIterator<Integer> listIterator1 = list.listIterator();
// 可以给参数，从 index 开始打印
while (listIterator.hasPrevious()) {
    System.out.println(listIterator.next() + " ");
}

5. ArrayList 和 LinkList 的区别

四、总结

本文围绕双向链表和 LinkedList 展开了系统讲解。

双向链表凭借'每个节点保存前驱和后继引用'的结构，在插入、删除操作上有着 O(1) 的时间复杂度优势。LinkedList 作为双向链表的 Java 实现，不仅提供了如 addFirst、removeLast 等丰富方法，支持迭代器、增强 for 等多种遍历方式，还能充当队列、栈使用。和 ArrayList 相比，LinkedList 适合频繁进行插入删除的场景，ArrayList 则更适合元素存储和随机访问的场景。掌握这些知识，能让你在面对不同业务场景时，合理选择数据结构，写出高效且易维护的代码。