链表与 LinkedList

Iterable 接口（间接实现，通过 Collection 继承）

• 所有集合类的顶层接口之一，定义了迭代遍历的能力。
• 核心约定： 实现 iterator() 方法，返回一个 Iterator 迭代器，支持对集合元素的遍历（如 hasNext()、next()、remove()）。
• 对 LinkedList 的影响： LinkedList 可通过迭代器、增强 for 循环（底层依赖迭代器）遍历元素，且由于其链表结构，迭代器遍历的时间复杂度为 O(n)，但比随机索引遍历更高效。

二、链表

• 在数据结构中，链表是用非连续的存储单元存储元素的线性表，而 Java 中的 LinkedList 就是顺序表的具体实现，下面从数据结构方面介绍：

数据结构中的链表

• 节点（Node） 链表的基本存储单元，通常包含两部分数据：
  • 数据域：存储实际的业务数据（如整数、字符串、自定义对象）；
  • 指针域：存储下一个（或上一个）节点的内存地址 / 引用，用于建立节点间的关联。
• 头节点 / 头指针
  • 头指针：指向链表第一个节点的引用，是访问整个链表的入口；
  • 头节点（可选）：在第一个数据节点前额外添加的空节点，作用是统一链表首尾的操作逻辑（避免头节点为空的边界判断）。
• 尾节点 链表的最后一个节点，其指针域通常指向 null（单向链表）或头节点（循环链表）。

三、常用代码手动实现

一般的链表分为有头无头结点、单项双向、有无尾结点，不过大差不差。我们手动实现的为无头结点单项的链表。

熟悉了这个，其他类型的也就水到渠成！

基本成员变量

static class ListNode {
    public int val;
    public ListNode next;

    // 构造方法实例化节点
    public ListNode(int val) {
        this.val = val;
    }
}

// 定义 listNode 的头结点
public ListNode head;

基本方法

public ListNode createList() {
    ListNode node0 = new ListNode(11);
    ListNode node1 = new ListNode(11);
    ListNode node2 = new ListNode(11);
    ListNode node3 = new ListNode(11);
    ListNode node4 = new ListNode(11);
    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) {
    // 检查 index
    if (index < 0 || index > size()) {
        System.out.println("index 不合法");
    }
    // 头插入
    if (index == 1) {
        addLast(data);
    }
    // 尾插入
    if (index == size()) {
        addLast(data);
    }
    // 中间插入
    ListNode cur = findIndex(index);
    ListNode node = new ListNode(data);
    node.next = cur.next;
    cur.next = node;
}

public ListNode findIndex(int index) {
    ListNode cur = head;
    int count = 0;
    while (count != index - 1) {
        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;
    }
    // 处理中间部分
    // 找到 del 之前的 ret
    ListNode ret = search(key);
    if (ret == null) {
        System.out.println("没有要删除元素");
        return;
    }
    ListNode del = ret.next;
    ret.next = del.next;
}

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("空链表异常");
    }
    ListNode prev = head;
    ListNode cur = head.next;
    // 处理中间部分
    while (cur != null) {
        if (cur.val == key) {
            prev.next = cur.next;
        } else {
            prev = cur;
            cur = cur.next;
        }
        cur = cur.next;
    }
    // 最后处理头节点
    if (head.val == key) {
        head = head.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 crn = cur.next;
        // 在删除节点之前保存之后的节点
        // cur.val = null; // 引用类型处理方法
        cur.next = crn;
        cur = null;
        cur = crn;
    }
    head = null;
}

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

四、LinkedList 使用

我们看一下 java 官方包中的方法。

构造方法

就是两个简单的构造方法。

1. 无参构造器 LinkedList()

public LinkedList() {}

无参构造器的实现非常简洁，仅初始化一个空的双向链表： 链表的 头指针（first）和尾指针（last） 默认都为 null； 链表的元素个数（size）初始化为 0； 没有预先分配任何节点或内存，链表处于完全空的状态。

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

public LinkedList(Collection<? extends E> c) {
    this(); // 先调用无参构造器初始化空链表
    addAll(c); // 将集合 c 中的元素批量添加到链表中
}

• 调用无参构造器：先创建一个空的双向链表；
• 调用 addAll 方法：将传入的 Collection 集合中的元素按迭代顺序批量添加到链表尾部；
• Collection：表示这个参数必须是一个实现了 Collection 接口的对象；
• ：表示这个集合的元素类型必须是 E 或 E 的子类。

List<Integer> list1 = new LinkedList<>();
List<Integer> list2 = new ArrayList<>();
// 使用 ArrayList 构建 LinkedList
LinkedList<Integer> list3 = new LinkedList<>(list2);
// List 实现了 Collection Integer 是 Integer 或者子类

官方常用方法

需要注意的就是每个方法的返回类型 + 方法名 + 形参。 一定要动手操作一下。

五、LinkedList 的遍历

直接打印

System.out.println(list);

for 循环

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

迭代器

介绍

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

方法

• 接口位置：java.util.Iterator
• 核心方法：
  • boolean hasNext()：判断是否还有下一个元素（无元素时返回 false）。
  • E next()：返回下一个元素（无元素时抛出 NoSuchElementException）。

// 迭代器
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}
System.out.println(" ");
ListIterator<Integer> iterator1 = list.listIterator(list.size());
while (iterator1.hasPrevious()) {
    System.out.print(iterator1.previous() + " ");
}