Java 数据结构：链表原理与 LinkedList 核心应用

2. 核心操作方法

创建链表示例

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;
}

指定位置插入

// 任意位置插入，第一个数据节点为 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;
}

private 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;
}

private 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() {
    head = null;
}

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

四、LinkedList 官方 API 使用

构造方法

1. 无参构造器 LinkedList()

   • 初始化一个空的双向链表。
   • 头指针（first）和尾指针（last）默认为 null。
   • 元素个数（size）初始化为 0。

2. 带集合参数的构造器 LinkedList(Collection<? extends E> c)

   • 先调用无参构造器初始化空链表。
   • 调用 addAll 方法，将传入的 Collection 集合中的元素按迭代顺序批量添加到链表尾部。

List<Integer> list1 = new LinkedList<>();
List<Integer> list2 = new ArrayList<>();
// 使用 ArrayList 构建 LinkedList
LinkedList<Integer> list3 = new LinkedList<>(list2);

常用方法

• 返回类型 + 方法名 + 形参：这是理解 API 的关键。
• 双端队列操作：由于实现了 Deque 接口，支持首尾双向操作。
  • 队首添加：addFirst(E e)
  • 队尾添加：addLast(E e)
  • 获取队首：getFirst()
  • 获取队尾：getLast()
  • 出栈：pop()（等效于 removeFirst）

五、LinkedList 的遍历方式

1. 直接打印

利用 toString() 方法，直接输出链表内容。

System.out.println(list);

2. for 循环

适用于知道大小的场景，但注意随机访问效率较低。

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

// 增强 for 循环（底层依赖迭代器）
for (Integer x : list) {
    System.out.print(x + " ");
}

3. 迭代器

在 Java 集合框架中，迭代器（Iterator） 是用于遍历集合元素的统一接口，它提供了一种不依赖集合底层结构的遍历方式。

• 核心方法：
  • boolean hasNext()：判断是否还有下一个元素。
  • E next()：返回下一个元素。

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

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

总结

本文梳理了链表的数据结构原理，并通过手动实现加深了对节点操作的理解。同时对比了 LinkedList 在 Java 集合框架中的定位及其核心 API 用法。掌握这些内容，有助于在实际开发中根据场景选择合适的数据结构。