深入理解链表结构与 Java LinkedList 实现

2. 核心操作方法

头插法与尾插法

头插法将新节点置于链表头部，时间复杂度 O(1)。尾插法则需遍历至末尾，时间复杂度 O(n)。

// 头插法
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;
}

任意位置插入

插入时需找到目标位置的前驱节点。注意边界条件处理。

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 prev = findPrev(index);
    ListNode node = new ListNode(data);
    node.next = prev.next;
    prev.next = node;
}

private ListNode findPrev(int index) {
    ListNode cur = head;
    int count = 0;
    while (count != index - 1) {
        cur = cur.next;
        count++;
    }
    return cur;
}

查找与删除

删除操作分为删除特定值节点和按索引删除。需注意空链表及头节点被删除的特殊情况。

// 查找是否包含关键字
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) return;
    if (head.val == key) {
        head = head.next;
        return;
    }
    ListNode prev = search(key);
    if (prev == null) return;
    ListNode del = prev.next;
    prev.next = del.next;
}

private ListNode search(int val) {
    ListNode cur = head;
    while (cur.next != null) {
        if (cur.next.val == val) return cur;
        cur = cur.next;
    }
    return null;
}

// 清空链表
public void clear() {
    head = null;
}

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

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

四、Java LinkedList 官方用法

在实际开发中，我们直接使用 JDK 提供的 java.util.LinkedList。

构造方法

1. 无参构造器：创建一个空的双向链表，首尾指针均为 null。
2. 带集合参数构造器：批量添加现有集合中的元素。

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

常用操作

除了 List 接口的标准方法外，由于实现了 Deque 接口，它还支持双端队列操作：

• 队尾入队/出队：addLast, removeLast
• 队首入队/出队：addFirst, removeFirst
• 栈行为：push (等同于 addFirst), pop (等同于 removeFirst)

图：双向链表内部结构示意

五、遍历方式对比

遍历是集合操作中最常见的场景，不同方式各有优劣。

1. 直接打印

利用 toString() 方法，适合快速查看内容。

System.out.println(list);

2. for 循环

适用于需要索引的场景，但在 LinkedList 中通过 get(i) 遍历效率较低（O(n²)），建议仅用于小数据量。

for (int i = 0; i < list.size(); i++) {
    System.out.print(list.get(i) + " ");
}

3. 迭代器（Iterator）

这是最推荐的遍历方式，解耦了集合与遍历逻辑，且支持安全删除。

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

对于双向链表，还可以使用 ListIterator 进行双向遍历：

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

总结

本文从数据结构角度剖析了链表原理，并通过手动实现代码展示了增删改查的核心逻辑。同时梳理了 Java LinkedList 作为 List 和 Deque 双重角色的特性。理解这些底层机制，有助于在开发中根据场景选择合适的集合类型，避免性能陷阱。