GESP五级 链表

一、链表基础：VS 数组

1. 链表定义

线性表的链式存储，每个节点包含数据域和指针域，节点在内存中地址不连续，通过指针串联。
链表的代码实践中利用节点互相链接，节点即结构体复合类型，里面定义有数据和前后相邻节点的地址（指针）。

2. 链表 vs 数组（核心对比）

3. 链表适用场景

✅ 频繁在开头/中间插入、删除元素
✅ 数据量不确定，动态变化
❌ 需要频繁随机访问元素（数组适配）
❌ 要求存储空间连续（数组适配）

二、单链表

1. 节点结构定义

struct Node {
    int val;        // 数据域
    Node* next;     // 指针域，指向下一个节点
    // 构造函数 同时初始化指针为空
    Node(int x) : val(x), next(nullptr) {}
};

2. 核心操作

（1）尾插节点

// 在单链表尾部插入值为val的节点
void insertTail(Node*& head, int val) {
    Node* newNode = new Node(val);
    // 空链表特殊处理
    if (head == nullptr) {
        head = newNode;
        return;
    }
    // 1. 迭代找到尾节点
    Node* p = head;
    while (p->next != nullptr) { // 尾节点的next指针为空指针
        p = p->next;
    }
    // 2. 修改指针
    p->next = newNode;
}

（2）删除指定值的所有节点（哑结点技巧）

问题：头节点如果是要删除的节点，需要单独处理
解决：创建哑结点（dummy），让它的next指向头节点，统一处理所有节点

Node* removeElements(Node* head, int val) {
    Node dummy(0);          // 哑结点，不存储数据
    dummy.next = head;      // 哑结点指向原头节点
    Node* cur = &dummy;     // 从哑结点开始遍历

    while (cur->next != nullptr) {
        if (cur->next->val == val) {
            // 1. 保存要删除的节点
            Node* del = cur->next;
            // 2. 修改前驱节点的指针，跳过要删除的节点
            cur->next = del->next;
            // 3. 释放内存
            delete del;
        } else {
            // 不是要删除的节点，继续往后走
            cur = cur->next;
        }
    }
    // 返回新的头节点（哑结点的next）
    return dummy.next;
}

（3）删除已知指针的节点（O(1)技巧）

问题：单链表不知道头节点，无法找到前驱节点
解决：把下一个节点的值覆盖到当前节点，然后删除下一个节点

// 删除节点p（非尾节点），不知道头节点
void deleteNode(Node* p) {
    // 1. 用下一个节点的值覆盖当前节点
    p->val = p->next->val;
    // 2. 删除下一个节点
    Node* del = p->next;
    p->next = del->next;
    delete del;
}

三、双链表

1. 节点结构定义

每个节点有两个指针：prev（指向前驱）、next（指向后继）

struct DNode {
    int val;
    DNode* prev;
    DNode* next;
    DNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

// 双链表结构体（带头尾指针）
struct DoubleLink {
    DNode* head;
    DNode* tail;
    int size;
    DoubleLink() : head(nullptr), tail(nullptr), size(0) {}
};

2. 核心操作

（1）尾插节点

void append(DoubleLink& list, int val) {
    DNode* newNode = new DNode(val);
    // 空链表特殊处理
    if (list.size == 0) {
        list.head = newNode;
        list.tail = newNode;
    } else {
        // 1. 新节点的prev指向原尾节点
        newNode->prev = list.tail;
        // 2. 原尾节点的next指向新节点
        list.tail->next = newNode;
        // 3. 更新尾指针
        list.tail = newNode;
    }
    list.size++;
}

（2）删除已知指针的节点 O(1)

void deleteNode(DNode* p) {
    // 1. 前驱节点的next指向后继节点
    if (p->prev != nullptr) {
        p->prev->next = p->next;
    }
    // 2. 后继节点的prev指向前驱节点
    if (p->next != nullptr) {
        p->next->prev = p->prev;
    }
    // 3. 释放内存
    delete p;
}

（3）在节点p之前插入新节点s

void insertBefore(DNode* p, DNode* s) {
    // 1. s的prev指向p的前驱
    s->prev = p->prev;
    // 2. s的next指向p
    s->next = p;
    // 3. p的前驱的next指向s
    if (p->prev != nullptr) {
        p->prev->next = s;
    }
    // 4. p的prev指向s
    p->prev = s;
}

四、循环链表

1. 循环单链表

特点：尾节点的next指向头节点，没有空指针

（1）创建只有一个节点的循环单链表

Node* createCircularList(int val) {
    Node* head = new Node(val);
    head->next = head;  // 自己指向自己
    return head;
}

（2）循环单链表遍历（必考填空）

void printCircularList(Node* head) {
    if (head == nullptr) return;
    Node* p = head;
    // 用do-while，先输出头节点，再遍历
    do {
        cout << p->val << " ";
        p = p->next;
    } while (p != head);  // 回到头节点结束
}

2. 带头尾哨兵的双向循环链表

特点：头哨兵和尾哨兵不存储数据，首尾相连

// 初始化空的双向循环链表
void initLinkedList(LinkedList* list) {
    list->head = new ListNode<int>();
    list->tail = new ListNode<int>();
    // 头哨兵的next指向尾哨兵
    list->head->next = list->tail;
    // 尾哨兵的prev指向头哨兵
    list->tail->prev = list->head;
}

五、考点

• 链表相比数组的最大优势：频繁在中间/开头插入删除
• 单链表不具备的特点：随机访问
• 带头结点的循环单链表判空：head->next == head
• 哑结点的作用：统一处理头节点和中间节点的删除操作

• 双向链表 插入/删除 指针操作考点：假设要在p后面插入q

  • 核心铁律：先保住要访问的节点地址，绝不能先动 p->next（一改就断链，找不到后继节点）
  • 所有操作遵循：先连后面，再连前面；先改后继，再改前驱

  • 坑点：

    • 插入时绝对不能先写 p->next = q;
      一旦先改p->next，原后继节点地址丢失，直接断链，再也找不到。
    • 删除时绝对不先动 p->next/p->prev
      先改自身指针会丢失前后节点地址，无法完成连接。
    • 空节点判断（边界）：删除头/尾节点时，先判p->prev/p->next是否为NULL，避免空指针报错。