【数据结构】三部曲：搞懂链表分类、掌握核心操作、复刻官方 LinkedList

白白的云835

402人浏览 · 2026-03-01 23:11:18

白白的云835 · 2026-03-01 23:11:18 发布

3. 手写 MyLinkedList（双向链表）

3.1 定义节点内部类

3.2 定义链表属性

3.3 实现 addFirst（头部添加）

3.4 实现 addLast（尾部添加）

3.5 实现 removeFirst

3.6 实现 removeLast

3.7 实现 get(int index)

3.8 实现 indexOf

3.9 实现 size 和 isEmpty

3.10 可选：重写 toString 方便打印

4. 完整代码示例

5. 测试我们的 MyLinkedList

6. 对比官方 LinkedList 源码

说明

1. 链表是什么？为什么需要它？

在编程中，我们经常需要存储一组数据。数组是一种常见的方式，但它有两大局限：

大小固定（扩容需要复制数组，成本高）。
在中间插入或删除元素效率低（需要移动后续所有元素）。

为了解决这些问题，链表应运而生。链表就像一列火车，每节车厢（节点）里装着货物（数据），车厢之间用挂钩（指针）连接。你可以轻松地在任意位置挂上一节新车厢，或者卸下一节旧车厢，只需调整相邻车厢的挂钩即可，其他车厢不必移动。

链表的基本单位是节点（Node），每个节点包含两部分：

数据域：存储实际的数据。
指针域：存储指向下一个节点的引用（地址）。

多个节点通过指针串联起来，就形成了链表。

2. 单向、双向、循环链表的区别

2.1 单向链表

每个节点只包含一个指向下一个节点的指针（next）。你可以从头节点开始，沿着指针一直走到尾节点（next 为 null 的节点）。但无法从后往前遍历，因为每个节点只有向前的指针。

head -> [data|next] -> [data|next] -> [data|next] -> null

2.2 双向链表

每个节点有两个指针：一个指向前一个节点（prev），一个指向后一个节点（next）。这样既可以从头到尾遍历，也可以从尾到头遍历。Java 的 LinkedList 就是双向链表。

null <- [prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> null

2.3 循环链表

循环链表可以是单向或双向的，但它的特点是尾节点的指针指向头节点，形成一个环。这样可以从任何节点出发遍历整个链表。常用于需要循环访问的场景，如约瑟夫环问题。

本文我们将手写一个双向链表，因为它最常用，且与 Java 的 LinkedList 对标。

3. 手写 MyLinkedList（双向链表）

我们将创建一个泛型类 MyLinkedList<E>，实现以下功能：

addFirst(E e)：在链表头部添加元素。

addLast(E e)：在链表尾部添加元素。

removeFirst()：删除并返回第一个元素。

removeLast()：删除并返回最后一个元素。

get(int index)：获取指定索引的元素。

indexOf(Object o)：查找元素第一次出现的索引。

size()：返回元素个数。

其他辅助方法（如 isEmpty()）。

3.1 定义节点内部类

节点是链表的核心，我们定义一个静态内部类 Node<E>，包含数据、前驱指针、后继指针。

private static class Node<E> {
    E item;          // 数据
    Node<E> prev;    // 前一个节点
    Node<E> next;    // 后一个节点

    Node(Node<E> prev, E item, Node<E> next) {
        this.prev = prev;
        this.item = item;
        this.next = next;
    }
}

3.2 定义链表属性

我们需要记住链表的头节点（first）、尾节点（last），以及元素个数（size）。

public class MyLinkedList<E> {
    private Node<E> first;   // 头节点
    private Node<E> last;    // 尾节点
    private int size;        // 元素个数

    public MyLinkedList() {
        first = null;
        last = null;
        size = 0;
    }

    // 其他方法...
}

3.3 实现 addFirst（头部添加）

头部添加的逻辑：

新节点的 prev 应为 null，next 指向当前的 first。
如果原链表为空，则新节点既是头也是尾（first = last = newNode）。
否则，将原头节点的 prev 指向新节点，然后更新 first 为新节点。
size++。

原链表: first -> A -> B -> ... -> last
添加新节点 X 到头部：
1. X.next = A
2. A.prev = X
3. first = X

public void addFirst(E e) {
    Node<E> newNode = new Node<>(null, e, first);
    Node<E> oldFirst = first;
    first = newNode;

    if (oldFirst == null) {
        // 原链表为空
        last = newNode;
    } else {
        oldFirst.prev = newNode;
    }
    size++;
}

3.4 实现 addLast（尾部添加）

尾部添加类似：

新节点的 prev 指向当前的 last，next 为 null。
如果原链表为空，则新节点既是头也是尾。
否则，将原尾节点的 next 指向新节点，然后更新 last 为新节点。
size++。

public void addLast(E e) {
    Node<E> newNode = new Node<>(last, e, null);
    Node<E> oldLast = last;
    last = newNode;

    if (oldLast == null) {
        first = newNode;
    } else {
        oldLast.next = newNode;
    }
    size++;
}

3.5 实现 removeFirst

删除头部元素：

如果链表为空，抛出异常（或返回 null）。
保存原头节点的数据和后继节点。
将原头节点的 item 和 next 置为 null（帮助 GC）。
更新 first 为原头节点的下一个节点。
如果新 first 不为 null，则将其 prev 设为 null；否则链表变空，last 也设为 null。
size--，返回被删除的元素。

public E removeFirst() {
    if (first == null) {
        throw new NoSuchElementException("链表为空");
    }
    Node<E> oldFirst = first;
    E item = oldFirst.item;
    Node<E> next = oldFirst.next;

    // 清除原头节点的引用
    oldFirst.item = null;
    oldFirst.next = null; // 帮助 GC

    first = next;
    if (next == null) {
        // 原链表只有一个节点，删除后链表为空
        last = null;
    } else {
        next.prev = null;
    }
    size--;
    return item;
}

3.6 实现 removeLast

删除尾部元素类似：

public E removeLast() {
    if (last == null) {
        throw new NoSuchElementException("链表为空");
    }
    Node<E> oldLast = last;
    E item = oldLast.item;
    Node<E> prev = oldLast.prev;

    oldLast.item = null;
    oldLast.prev = null; // 帮助 GC

    last = prev;
    if (prev == null) {
        first = null;
    } else {
        prev.next = null;
    }
    size--;
    return item;
}

3.7 实现 get(int index)

根据索引获取元素：

先检查索引是否合法（0 <= index < size）。
为了效率，可以从头或尾遍历，取决于 index 在前半段还是后半段。我们实现简单的从头遍历（也可优化，但先保证易懂）。

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("索引越界: " + index);
    }
    Node<E> x = first;
    for (int i = 0; i < index; i++) {
        x = x.next;
    }
    return x.item;
}



//优化版本（类似 Java LinkedList 的 node 方法）：如果 index < size/2 则从头遍历，否则从尾遍历。
private Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        return x;
    }
}
//然后 get 方法可以简化为 return node(index).item;。

3.8 实现 indexOf

查找元素第一次出现的索引：

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                return index;
            }
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                return index;
            }
            index++;
        }
    }
    return -1;
}

3.9 实现 size 和 isEmpty

public int size() {
    return size;
}

public boolean isEmpty() {
    return size == 0;
}

3.10 可选：重写 toString 方便打印

@Override
public String toString() {
    StringBuilder sb = new StringBuilder("[");
    Node<E> x = first;
    while (x != null) {
        if (x != first) {
            sb.append(", ");
        }
        sb.append(x.item);
        x = x.next;
    }
    sb.append("]");
    return sb.toString();
}

4. 完整代码示例

将以上所有代码整合成一个类，添加必要的导入（如 java.util.NoSuchElementException）。为了完整，我们加上一些注释。

import java.util.NoSuchElementException;

public class MyLinkedList<E> {
    // 节点内部类
    private static class Node<E> {
        E item;
        Node<E> prev;
        Node<E> next;

        Node(Node<E> prev, E item, Node<E> next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }

    private Node<E> first;
    private Node<E> last;
    private int size;

    public MyLinkedList() {
        first = null;
        last = null;
        size = 0;
    }

    // 头部添加
    public void addFirst(E e) {
        Node<E> newNode = new Node<>(null, e, first);
        Node<E> oldFirst = first;
        first = newNode;
        if (oldFirst == null) {
            last = newNode;
        } else {
            oldFirst.prev = newNode;
        }
        size++;
    }

    // 尾部添加
    public void addLast(E e) {
        Node<E> newNode = new Node<>(last, e, null);
        Node<E> oldLast = last;
        last = newNode;
        if (oldLast == null) {
            first = newNode;
        } else {
            oldLast.next = newNode;
        }
        size++;
    }

    // 删除头部
    public E removeFirst() {
        if (first == null) {
            throw new NoSuchElementException("链表为空");
        }
        Node<E> oldFirst = first;
        E item = oldFirst.item;
        Node<E> next = oldFirst.next;

        // 清除引用，帮助GC
        oldFirst.item = null;
        oldFirst.next = null;

        first = next;
        if (next == null) {
            last = null;
        } else {
            next.prev = null;
        }
        size--;
        return item;
    }

    // 删除尾部
    public E removeLast() {
        if (last == null) {
            throw new NoSuchElementException("链表为空");
        }
        Node<E> oldLast = last;
        E item = oldLast.item;
        Node<E> prev = oldLast.prev;

        oldLast.item = null;
        oldLast.prev = null;

        last = prev;
        if (prev == null) {
            first = null;
        } else {
            prev.next = null;
        }
        size--;
        return item;
    }

    // 根据索引获取元素
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界: " + index);
        }
        return node(index).item;
    }

    // 查找元素的索引
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) return index;
                index++;
            }
        }
        return -1;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    // 根据索引返回节点（优化：判断前半段还是后半段）
    private Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node<E> x = first;
        while (x != null) {
            if (x != first) {
                sb.append(", ");
            }
            sb.append(x.item);
            x = x.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

5. 测试我们的 MyLinkedList

写一个简单的测试类，验证基本功能。

public class MyLinkedListTest {
    public static void main(String[] args) {
        MyLinkedList<String> list = new MyLinkedList<>();

        // 测试 addFirst 和 addLast
        list.addFirst("A");
        list.addFirst("B");
        list.addLast("C");
        System.out.println("链表: " + list); // 期望 [B, A, C]

        // 测试 get
        System.out.println("索引 0: " + list.get(0)); // B
        System.out.println("索引 1: " + list.get(1)); // A
        System.out.println("索引 2: " + list.get(2)); // C

        // 测试 indexOf
        System.out.println("A 的索引: " + list.indexOf("A")); // 1
        System.out.println("不存在元素索引: " + list.indexOf("D")); // -1

        // 测试 removeFirst 和 removeLast
        System.out.println("删除头部: " + list.removeFirst()); // B
        System.out.println("删除尾部: " + list.removeLast());  // C
        System.out.println("剩余链表: " + list); // [A]

        // 测试空链表删除
        list.removeFirst(); // 删除 A
        System.out.println("isEmpty? " + list.isEmpty()); // true
        try {
            list.removeFirst(); // 抛出异常
        } catch (Exception e) {
            System.out.println("捕获异常: " + e.getClass().getSimpleName());
        }
    }
}

6. 对比官方 LinkedList 源码

Java 的 java.util.LinkedList 也是一个双向链表，它实现了 List 和 Deque 接口，因此提供了更多方法（如 add(int index, E element)、remove(Object o) 等）。下面从几个方面对比我们的实现和官方实现。

下面以表格形式对比手写 MyLinkedList 与官方 java.util.LinkedList 的核心实现。每个对比项前标注了对应的小节编号，方便对照原文。

对比项（标号）	MyLinkedList	Java LinkedList
6.1 节点定义	静态内部类 `Node<E>`，包含 `item`、`prev`、`next`	完全相同
6.2 链表属性	`first`、`last`、`size`	增加了 `modCount`（用于快速失败迭代器）
6.3.1 addFirst 实现	创建新节点，链接前后，更新 `first`，处理空链表，`size++`	逻辑完全相同，但额外增加 `modCount++`
6.3.2 removeFirst 实现	保存原头节点，更新 `first`，清理引用，`size--`	逻辑相同，增加 `modCount++`，并抽取出 `unlinkFirst` 方法
6.3.3 get(index) 实现	检查索引，调用 `node(index)` 遍历（二分优化：根据 index 位置决定从头或尾遍历）	完全一致，`node(index)` 方法也采用相同的二分优化
6.3.4 indexOf 实现	遍历链表，分 null 和非 null 两种情况比较	完全相同
6.4 额外功能	仅实现了最基础的增删查	实现了 `List` 和 `Deque` 接口，提供丰富方法： - 指定位置增删改 - 批量操作 - 队列/双端队列方法（offer/poll/peek） - 迭代器（支持 fail-fast） - 序列化、克隆
6.5 性能特点	头部/尾部操作 O(1)，按索引访问 O(n)（但有二分优化）	完全相同

说明

modCount：Java LinkedList 通过 modCount 记录结构修改次数，迭代器检测到 modCount 变化时会抛出 ConcurrentModificationException，保证迭代过程的安全性。

方法封装：官方将删除逻辑封装在 unlinkFirst、unlinkLast、unlink 等方法中，代码复用性更高。

接口实现：官方 LinkedList 实现了 List 和 Deque，因此可以当作队列、双端队列使用，而我们的实现只具备栈/队列的基本功能。