Java LinkedList 底层原理与手动实现指南

1. 节点定义

static class ListNode {
    int val;
    ListNode next;

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

2. 成员变量与方法

我们需要维护一个头指针 head，并实现增删改查功能。

public class MyLinkedList {
    private 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;
    }

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

    // 尾插法：O(n)
    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;
    }

    // 指定位置插入：O(n)
    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 = findIndex(index - 1);
        ListNode node = new ListNode(data);
        node.next = prev.next;
        prev.next = node;
    }

    // 辅助方法：查找指定位置的前驱节点
    private ListNode findIndex(int index) {
        ListNode cur = head;
        int count = 0;
        while (count != index) {
            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) {
            System.out.println("空链表异常");
            return;
        }
        if (head.val == key) {
            head = head.next;
            return;
        }
        ListNode prev = findIndex(key); // 这里简化逻辑，实际应查找前驱
        // 修正查找前驱逻辑
        ListNode cur = head;
        while (cur.next != null && cur.next.val != key) {
            cur = cur.next;
        }
        if (cur.next != null) {
            cur.next = cur.next.next;
        } else {
            System.out.println("未找到要删除的元素");
        }
    }

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

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

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

四、官方 API 使用

Java 提供的 LinkedList 类封装了上述逻辑，并提供了更丰富的功能。

构造方法

1. 无参构造：创建一个空的双向链表，first 和 last 指针均为 null。
2. 带集合参数构造：将传入的 Collection 批量添加到链表中。

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

常用操作

• 添加：add(E e)、addFirst(E e)、addLast(E e)。
• 删除：remove(Object o)、removeFirst()、removeLast()。
• 获取：get(int index)、getFirst()、getLast()。
• 判断：contains(Object o)、isEmpty()。

注意区分不同方法的返回类型和形参，特别是涉及首尾操作的 Deque 方法。

五、遍历方式

1. 直接打印

利用 toString() 方法，输出所有元素。

System.out.println(list);

2. 索引循环

适用于需要下标访问的场景，但注意 get(i) 在 LinkedList 中是 O(n)。

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

3. 增强 For 循环

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

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

4. 迭代器

最通用的遍历方式，支持正向和反向遍历。

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

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

总结

通过对比手动实现与官方 API，我们可以清晰看到 LinkedList 在内存布局和操作效率上的特点。它在频繁插入删除的场景下表现优异，但在随机访问上不如数组。理解其底层双向链表结构及接口设计，有助于在实际开发中做出更合理的数据结构选择。