Java 链表基础与 LinkedList 核心原理

Java 集合框架概览

Java 集合框架是存储和操作对象的核心体系，主要分为 Collection（单列集合） 和 Map（双列集合）。

核心接口与分类

• Collection：单列集合的根接口，定义增删改查及遍历等基本操作。其子接口包括 List（有序可重复）、Set（无序不可重复）和 Queue（队列）。
• Map：存储键值对（Key-Value），Key 唯一，Value 可重复。子接口包含 SortedMap（键有序）。

今天我们重点探讨 Collection 下的 LinkedList。

LinkedList 特性

1. 实现的接口
   • 实现了 List 接口，具备列表的增删改查能力。
   • 实现了 Deque 接口，兼具双端队列特性，可作为栈或队列使用。
2. 核心结构
   • 基于双向链表，每个节点存储前驱和后继节点的引用，无容量限制。
3. 性能特点
   • 随机访问：通过索引 get(i) 效率较低（时间复杂度 O(n)），需从头遍历。
   • 增删操作：在链表两端或已知节点附近增删元素效率高（时间复杂度 O(1)）。
   • 线程安全：非线程安全，多线程环境下需手动同步。

作为 List 接口的实现，它继承了有序集合的基础行为；作为 Deque 的实现，它支持首尾双向操作。相比 ArrayList（数组实现），LinkedList 在频繁的首尾插入删除场景下更具优势，但随机访问性能较弱。

数据结构中的链表

链表是用非连续存储单元存储元素的线性表。理解其底层结构有助于掌握 LinkedList 的行为。

• 节点（Node）：基本存储单元，包含数据域（业务数据）和指针域（指向下一个/上一个节点的引用）。
• 头指针：指向链表第一个节点的引用，是访问入口。
• 尾节点：最后一个节点，指针域通常指向 null（单向）或头节点（循环）。

手动实现单链表

为了深入理解，我们可以尝试手动实现一个无头结点的单项链表。虽然 Java 提供了 LinkedList，但手写过程能清晰展示内存引用的变化逻辑。

以下代码分为成员变量、构造辅助方法、核心业务方法三部分。

节点定义与成员变量

static class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

public ListNode head;

核心操作方法

这里展示了创建链表、头插法、尾插法、指定位置插入以及查找删除等基础逻辑。

// 创建测试链表
public ListNode createList() {
    ListNode node0 = new ListNode(1);
    ListNode node1 = new ListNode(2);
    ListNode node2 = new ListNode(3);
    ListNode node3 = new ListNode(4);
    ListNode node4 = new ListNode(5);
    
    node0.next = node1;
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    head = node0;
    return head;
}

// 头插法
public void addFirst(int data) {
    ListNode node = new ListNode(data);
    node.next = head;
    head = node;
}

// 尾插法
public void addLast(int data) {
    ListNode node = new ListNode(data);
    if (head == null) {
        head = node;
        return;
    }
    ListNode cur = head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = node;
}

// 任意位置插入（index 从 0 开始）
public void addIndex(int index, int data) {
    if (index < 0 || index > size()) {
        System.out.println("index 不合法");
        return;
    }
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size()) {
        addLast(data);
        return;
    }
    ListNode cur = findIndex(index - 1);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;
}

// 辅助方法：找到第 index 个节点的前驱
public ListNode findIndex(int index) {
    ListNode cur = head;
    int count = 0;
    while (count != index) {
        cur = cur.next;
        count++;
    }
    return cur;
}

// 查找是否包含关键字 key
public boolean contains(int key) {
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

// 删除第一次出现关键字为 key 的节点
public void remove(int key) {
    if (head == null) {
        System.out.println("空链表异常");
        return;
    }
    // 删除头节点
    if (head.val == key) {
        head = head.next;
        return;
    }
    // 处理中间部分
    ListNode prev = search(key);
    if (prev == null) {
        System.out.println("没有要删除元素");
        return;
    }
    ListNode del = prev.next;
    prev.next = del.next;
}

// 辅助方法：查找值为 val 的节点的前驱
public ListNode search(int val) {
    ListNode cur = head;
    while (cur.next != null) {
        if (cur.next.val == val) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
}

// 删除所有值为 key 的节点
public void removeAllKey(int key) {
    if (head == null) {
        System.out.println("空链表异常");
        return;
    }
    // 处理头节点
    while (head != null && head.val == key) {
        head = head.next;
    }
    if (head == null) return;
    
    ListNode prev = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == key) {
            prev.next = cur.next;
        } else {
            prev = cur;
        }
        cur = cur.next;
    }
}

// 获取长度
public int size() {
    int count = 0;
    ListNode cur = head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

// 清空链表
public void clear() {
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = null; // 帮助 GC
        cur = next;
    }
    head = null;
}

// 打印链表
public void display() {
    ListNode cur = head;
    while (cur != null) {
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}

LinkedList 官方 API 解析

Java 标准库中的 java.util.LinkedList 已经封装了上述逻辑，并针对双向链表进行了优化。

构造方法

1. 无参构造器

   public LinkedList() {}
   

   初始化一个空的双向链表，头尾指针均为 null，size 为 0。

2. 带集合参数构造器

   public LinkedList(Collection<? extends E> c)
   

   先调用无参构造器，再批量添加传入集合的元素。这要求传入的集合必须实现 Collection 接口。

   List<Integer> list2 = new ArrayList<>();
   LinkedList<Integer> list3 = new LinkedList<>(list2);
   

常用方法

• 增删改查：继承自 List 接口，如 add, remove, get, set。
• 双端操作：继承自 Deque 接口，如 addFirst, addLast, pollFirst, pop。
• 注意：由于底层是双向链表，首尾操作的时间复杂度为 O(1)，而中间位置的索引访问仍需 O(n)。

遍历方式

直接打印

利用 toString() 方法，会输出 [元素 1, 元素 2, ...] 格式。

System.out.println(list);

增强 for 循环

底层依赖迭代器，语法简洁。

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

迭代器 Iterator

Iterator 提供了统一的遍历接口，解耦了集合结构与遍历逻辑。

Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}

若需反向遍历，可使用 ListIterator。

ListIterator<Integer> iterator1 = list.listIterator(list.size());
while (iterator1.hasPrevious()) {
    System.out.print(iterator1.previous() + " ");
}

总结

LinkedList 基于双向链表实现，在频繁的首尾插入删除场景中表现优异，但随机访问性能不如 ArrayList。理解其底层节点结构和接口继承关系，有助于在实际开发中根据场景选择合适的集合类型。