链表细节与 Java LinkedList 实战

头插与尾插

头插法直接在 head 前插入，时间复杂度 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 提供的 LinkedList 不仅作为列表，还是个双端队列。构造方法有无参和从其他集合构造两种。

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

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

常用的队列和栈操作：

• addFirst / removeFirst：队首操作
• addLast / removeLast：队尾操作
• push / pop：模拟栈（等价于 addFirst/removeFirst）

遍历方式的差异

遍历 LinkedList 时，方式选不对会严重影响性能。

System.out.println(list); 直接用 toString 输出，适合调试。

通过索引的 for 循环 for (int i = 0; i < list.size(); i++) 在 LinkedList 上是灾难——每次 get(i) 都需要从链表头部开始找，复杂度 O(n²)。数据量稍大就会慢得离谱。

迭代器是更好的选择，它内部维护了当前节点的引用，每次 next 只是向前走一步。

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() + " ");
}

理解了这些底层的实现，才能在合适的场景下挑对集合。例如频繁随机访问就该用 ArrayList，如果需要频繁在头部插入或删除，LinkedList 会更合适。