数据结构——链表(概念，类型，java实现、增删、优缺点)

我是一个计算机专业研0的学生卡蒙Camel🐫🐫🐫（刚保研）
记录每天学习过程（主要学习Java、python、人工智能），总结知识点（内容来自：自我总结+网上借鉴）
希望大家能一起发现问题和补充，也欢迎讨论👏👏👏

链表

链表介绍

链表（Linked List）是一种线性数据结构，它由一系列节点（Node）组成，每个节点包含两部分：一部分用于存储元素（数据域），另一部分是包含指向列表中下一个节点的引用（指针域）。

基本概念：

• 节点（Node）：链表的基本单位，由数据域和一个或多个指针域组成。
• 头结点（Head Node）：指向链表第一个节点的引用。对于空链表，头结点为null。
• 尾结点（Tail Node）：链表中最后一个节点，它的指针域通常为null（对于非循环链表）。

链表类型

1. 单向链表

• 每个节点只包含一个指向前驱节点或后继节点的指针。
• 优点是结构简单，节省空间；缺点是从任意节点只能朝一个方向遍历。

2. 双向链表

• 每个节点包含两个指针，分别指向前驱节点和后继节点。
• 支持双向遍历，方便在链表中前后移动，但需要额外的空间来存储第二个指针。

3. 循环链表

• 尾结点的指针不是指向null，而是指回链表的第一个节点，形成一个环。
• 可以是单向循环链表或双向循环链表，适用于某些特定的应用场景，如实现循环队列。

链表实现(增删改查)

以双向链表为例

链表节点

private static class Node<E> {
    E item; // 存储的元素
    Node<E> next; // 指向下一个节点
    Node<E> prev; // 指向前一个节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

• 使用泛型来表示存储在节点中的数据可以是任何对象
• next和prev指向对象都是Node

插入节点

• 头插：

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

1. 先记录头节点
2. 创建新节点，并且新节点的prev指向null，next指向头节点
3. 判断头节点是否为空

​ a. 若为空，则原来没有节点，设置尾节点也为该新节点

​ b. 否则头节点的prev指向新节点

4. size和modCount都加一

• 尾插：

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

和头插法几乎同理。

删除节点

unlink操作：

E unlink(Node<E> x) {
    // assert x != null;  // 断言：确保传入的节点不为null（注释掉了）
    final E element = x.item;  // 保存要移除节点的数据元素
    final Node<E> next = x.next;  // 获取要移除节点的下一个节点引用
    final Node<E> prev = x.prev;  // 获取要移除节点的上一个节点引用

    if (prev == null) {  // 如果要移除的是头结点
        first = next;  // 更新头结点指向下一个节点（即新的头结点）
    } else {  // 如果不是头结点
        prev.next = next;  // 将前一个节点的next指针指向当前节点的下一个节点
        x.prev = null;  // 断开当前节点与前一个节点的链接
    }

    if (next == null) {  // 如果要移除的是尾结点
        last = prev;  // 更新尾结点指向前一个节点（即新的尾结点）
    } else {  // 如果不是尾结点
        next.prev = prev;  // 将下一个节点的prev指针指向前一个节点
        x.next = null;  // 断开当前节点与下一个节点的链接
    }

    x.item = null;  // 清空当前节点的数据域
    size--;  // 减少链表大小计数器
    modCount++;  // 增加修改计数器，用于迭代器检测并发修改
    return element;  // 返回被移除节点的数据元素
}

remove操作：

public boolean remove(Object o) {
    // 如果要移除的元素为null，则特别处理
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) { // 遍历链表
            if (x.item == null) { // 查找值为null的节点
                unlink(x); // 移除找到的第一个null节点
                return true; // 成功移除后返回true
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) { // 遍历链表
            if (o.equals(x.item)) { // 使用equals方法查找匹配的节点
                unlink(x); // 移除找到的第一个匹配节点
                return true; // 成功移除后返回true
            }
        }
    }
    return false; // 如果没有找到匹配项则返回false
}

链表的特点与优势👍

• 动态大小：不像数组那样需要预先分配固定大小的内存空间，链表可以根据需要动态地增长或收缩。
• 插入和删除效率高：一旦找到要操作的位置，插入或删除只需要改变相关节点之间的链接，而不需要像数组那样移动大量元素。
• 不连续存储：由于节点之间通过指针连接，因此它们不必存放在连续的内存位置上，这使得内存使用更加灵活。

链表的缺点👎

• 随机访问效率低：为了访问某个节点，通常需要从头结点开始逐个遍历，直到到达目标节点，这使得随机访问的时间复杂度为O(n)。
• 额外的内存开销：每个节点除了存储实际的数据外，还需要额外的内存来存储指针。