数据结构(Java版)第九期：LinkedList与链表

数据结构(Java版)第九期：LinkedList与链表(四)

这是“手握风云”博主的《Java数据结构秘籍》（又称数据结构(Java版)系列）的第9期文章，发表于2025年1月15日。
系列前几期（第6~8期）已经详细讲解了链表基础（单向链表、带头/不带头、头插/尾插等），第9期重点转向双向链表的模拟实现 + Java官方LinkedList的使用与源码剖析。

原文链接（CSDN）：https://blog.csdn.net/2401_85198927/article/details/145118067

一、LinkedList的模拟实现（双向带头非循环链表）

在前几期实现的都是单向链表，本期升级为双向链表（每个节点包含 val、prev、next 三个域），并采用带头哨兵节点（head不存数据，初始时 head.prev = head; head.next = head;），极大简化边界判断。

核心节点类

private static class Node {
    int val;
    Node prev;
    Node next;
    public Node(int val) {
        this.val = val;
    }
}

MyLinkedList完整模拟代码（核心方法）

public class MyLinkedList {
    private final Node head;  // 哨兵头节点
    private int size;

    public MyLinkedList() {
        head = new Node(-1);
        head.prev = head;
        head.next = head;   // 初始形成环（方便头尾操作）
        size = 0;
    }

    // 尾插法
    public void addLast(int data) {
        Node newNode = new Node(data);
        Node last = head.prev;
        last.next = newNode;
        newNode.prev = last;
        newNode.next = head;
        head.prev = newNode;
        size++;
    }

    // 头插法
    public void addFirst(int data) {
        Node newNode = new Node(data);
        Node first = head.next;
        head.next = newNode;
        newNode.prev = head;
        newNode.next = first;
        first.prev = newNode;
        size++;
    }

    // 按索引插入（中间插入）
    public void add(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) { addFirst(data); return; }
        if (index == size) { addLast(data); return; }

        Node cur = head.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        Node newNode = new Node(data);
        newNode.prev = cur.prev;
        newNode.next = cur;
        cur.prev.next = newNode;
        cur.prev = newNode;
        size++;
    }

    // 获取指定索引元素
    public int get(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        Node cur = head.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur.val;
    }

    // 删除指定索引元素（O(1)删除）
    public void remove(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        Node cur = head.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        size--;
    }

    public int size() { return size; }

    // 打印（便于调试）
    public void display() {
        Node cur = head.next;
        while (cur != head) {
            System.out.print(cur.val + " <-> ");
            cur = cur.next;
        }
        System.out.println("null");
    }
}

关键点：

• 所有插入/删除只需修改4个指针（O(1)），无需移动元素。
• 哨兵节点让头尾操作和中间操作代码高度统一。

二、Java官方 LinkedList 的使用

import java.util.LinkedList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();

        // 尾插
        list.add(1);
        list.add(2);
        list.add(3);

        // 指定位置插入
        list.add(0, 0);           // 头插
        list.add(list.size(), 99);// 尾插

        // 删除
        list.remove();            // removeFirst()
        list.removeFirst();
        list.removeLast();
        list.remove(1);           // 按索引删除

        // 常用API
        System.out.println(list.get(0));
        list.set(0, 100);
        System.out.println(list.contains(100));
        System.out.println(list.indexOf(100));
        System.out.println(list.lastIndexOf(100));

        // 子列表（视图，不是拷贝）
        List<Integer> sub = list.subList(0, 2);

        list.clear();
    }
}

遍历方式推荐（LinkedList不实现RandomAccess，普通for循环很慢！）

// 推荐：foreach 或 迭代器
for (Integer e : list) { ... }

// 正向迭代器
var it = list.listIterator();
while (it.hasNext()) System.out.print(it.next() + " ");

// 反向迭代器
var rit = list.listIterator(list.size());
while (rit.hasPrevious()) System.out.print(rit.previous() + " ");

三、LinkedList 底层结构总结（本期核心）

Java的 LinkedList 正是 双向带头非循环链表：

• 每个 Node<E> 包含：E item; Node<E> prev; Node<E> next;
• 内部维护 Node<E> first; Node<E> last; int size;
• 实现了 List、Deque、Queue 等接口，可当栈、队列、双端队列使用。
• 随机访问 get(index) 是 O(n)，但头尾增删是 O(1)。

四、与ArrayList的对比（本系列反复强调）

维度	ArrayList（动态数组）	LinkedList（双向链表）
底层结构	Object[] 数组	双向Node链表
随机访问	O(1)	O(n)
头/中间插入删除	O(n)（需搬移元素）	O(1)（改指针）
内存占用	连续空间，可能浪费	每个节点多2个引用指针开销
适用场景	频繁查询、顺序访问	频繁头尾/中间增删

选择建议（本系列反复提醒）：

• 读多写少 → ArrayList
• 写多读少（尤其是中间操作）→ LinkedList
• 两者都不是线程安全的，需要同步请用 Collections.synchronizedList(...)

---

这期内容是整个链表章节的高潮，把前几期的单向链表知识直接升级为生产级双向链表模拟，并对接JDK源码。掌握这期后，你就真正理解了“为什么LinkedList适合做队列/栈”以及“为什么面试总问LinkedList和ArrayList区别”。

想继续学习？

• 第10期、第11期：栈和队列（基于LinkedList实现）
• 后续还有二叉树、红黑树、堆等重头戏。

需要我把第6~8期的单向链表完整代码也贴出来，或者帮你手写一个泛型版MyLinkedList（带Iterator实现），随时说一声！🚀

（以上内容基于该系列第9期原文 + 配套讲解整理，代码均可直接运行测试。）