单元2

链表操作详解：插入、删除、读取及指针修改次数

以下针对四种链表类型（单链表、双链表、循环单链表、循环双链表），详细说明插入、删除、读取操作步骤及指针修改次数（仅统计已有节点的指针修改，不包括新节点初始化或删除节点释放）。

1. 单链表（Singly Linked List）

• 节点结构：数据 + next指针（指向后继）

• 插入操作（在节点A和B之间插入C）：

  • 步骤：
    1. 创建新节点C，设置 C.next = B（新节点初始化，不计入修改）。
    2. 修改A的 next 指针指向C：A.next = C。
  • 指针修改次数：1次（仅修改前驱节点A的指针）。
  • 边界情况：
    • 头部插入：修改头指针指向C（头指针修改不计入节点指针修改）。
    • 尾部插入：同一般情况（修改原尾节点的 next）。

• 删除操作（删除节点B，A为其前驱）：

  • 步骤：
    1. 修改A的 next 指针指向B的后继：A.next = B.next。
    2. 释放B（不计入指针修改）。
  • 指针修改次数：1次（仅修改前驱节点A的指针）。
  • 边界情况：
    • 删除头节点：修改头指针指向原头节点的后继（头指针修改不计入节点指针修改）。
    • 删除尾节点：修改倒数第二节点的 next 为 null（1次修改）。

• 读取操作：

  • 仅支持顺序访问：从头节点遍历，时间复杂度 O(n)。
  • 不支持随机访问（无索引）。

2. 双链表（Doubly Linked List）

• 节点结构：数据 + next指针（指向后继） + prev指针（指向前驱）

• 插入操作（在节点A和B之间插入C）：

  • 步骤：
    1. 创建新节点C，设置 C.prev = A, C.next = B（新节点初始化）。
    2. 修改A的 next 指针指向C：A.next = C。
    3. 修改B的 prev 指针指向C：B.prev = C。
  • 指针修改次数：2次（修改前驱A的 next 和后继B的 prev）。
  • 边界情况：
    • 头部插入：需修改原头节点的 prev 指向C（1次修改）。
    • 尾部插入：需修改原尾节点的 next 指向C（1次修改）。

• 删除操作（删除节点B）：

  • 步骤：
    1. 修改B前驱A的 next 指向B的后继C：A.next = C。
    2. 修改B后继C的 prev 指向A：C.prev = A。
    3. 释放B（不计入指针修改）。
  • 指针修改次数：2次（修改前驱A的 next 和后继C的 prev）。
  • 边界情况：
    • 删除头节点：需修改新头节点的 prev = null（1次修改）。
    • 删除尾节点：需修改新尾节点的 next = null（1次修改）。

• 读取操作：

  • 支持双向顺序访问（从头或尾遍历），时间复杂度 O(n)。
  • 不支持随机访问。

3. 循环单链表（Circular Singly Linked List）

• 节点结构：同单链表，尾节点 next 指向头节点。

• 插入操作（在节点A和B之间插入C）：

  • 步骤：
    1. 创建新节点C，设置 C.next = B（新节点初始化）。
    2. 修改A的 next 指针指向C：A.next = C。
  • 指针修改次数：1次（仅修改前驱节点A的指针）。
  • 边界情况：
    • 头节点前插入：需修改尾节点的 next 指向C（1次修改）。

• 删除操作（删除节点B，A为其前驱）：

  • 步骤：
    1. 修改A的 next 指向B的后继：A.next = B.next。
    2. 若删除头节点，需更新尾节点的 next 指向新头节点（1次修改）。
  • 指针修改次数：1次（修改前驱节点A的指针）。
  • 边界情况：
    • 删除唯一节点：直接置空链表（无指针修改）。

• 读取操作：

  • 支持循环顺序访问，可从任意节点遍历全链表。

4. 循环双链表（Circular Doubly Linked List）

• 节点结构：同双链表，头节点 prev 指向尾节点，尾节点 next 指向头节点。

• 插入操作（在节点A和B之间插入C）：

  • 步骤：
    1. 创建新节点C，设置 C.prev = A, C.next = B（新节点初始化）。
    2. 修改A的 next 指向C：A.next = C。
    3. 修改B的 prev 指向C：B.prev = C。
  • 指针修改次数：2次（修改前驱A的 next 和后继B的 prev）。
  • 边界情况：无特殊处理（循环特性消除头尾边界）。

• 删除操作（删除节点B）：

  • 步骤：
    1. 修改B前驱A的 next 指向B的后继C：A.next = C。
    2. 修改B后继C的 prev 指向A：C.prev = A。
  • 指针修改次数：2次（修改前驱A的 next 和后继C的 prev）。
  • 边界情况：
    • 删除唯一节点：直接置空链表（无指针修改）。

• 读取操作：

  • 支持双向循环访问，可从任意节点双向遍历全链表。

操作总结表

核心结论

1. 单链表/循环单链表：
   • 插入和删除只需 1次指针修改（前驱的 next）。
2. 双链表：
   • 插入和删除需 1~2次指针修改（中间操作需修改前驱的 next 和后继的 prev）。
3. 循环双链表：
   • 插入和删除严格需 2次指针修改（循环特性消除边界情况）。
4. 读取操作：
   • 所有链表均需遍历（O(n)），不支持随机访问。

关于链表头部节点的详细解释

1. 头部节点是否存储数据？

• 头部节点可以存储数据：
  • 在标准链表实现中，头部节点（第一个节点）通常存储有效数据。
  • 例如：链表 A → B → C，节点A是头部节点，存储数据A。
• 特殊情况（哨兵节点）：
  • 某些实现会添加一个不存储数据的哨兵节点（Dummy Node）作为头节点，此时：
    • 哨兵节点的数据域为空（或无效值）
    • 其 next 指针指向真正的第一个数据节点
  • 例如：[哨兵] → A → B → C

2. 插入新节点到头部时的操作

• 标准情况（无哨兵节点）：

  graph LR
    subgraph 插入前
      HEAD[头指针] --> A
      A --> B
    end
  
    subgraph 插入后
      HEAD_NEW[头指针] --> C
      C --> A
      A --> B
    end
  

  1. 创建新节点C
  2. 设置 C.next = A（原头部节点）
  3. 修改头指针指向C：HEAD = C
  • 结果：C成为新的头部节点，链表变为 C → A → B

• 有哨兵节点的情况：

  graph LR
    subgraph 插入前
      HEAD[头指针] --> SENTINEL[哨兵]
      SENTINEL --> A
      A --> B
    end
  
    subgraph 插入后
      HEAD --> SENTINEL
      SENTINEL --> C
      C --> A
      A --> B
    end
  

  1. 创建新节点C
  2. 设置 C.next = A（原第一个数据节点）
  3. 修改哨兵节点的指针：SENTINEL.next = C
  • 结果：C成为第一个数据节点，哨兵节点仍为逻辑头部

3. 关键问题澄清

“插入新节点C到头部时，C是否可能成为第一个节点？”

• 可以成为第一个节点：
  • 在无哨兵节点的链表中，C通过头指针的修改直接成为新的头部节点。
  • 在有哨兵节点的链表中，C成为第一个数据节点（逻辑上的第一个有效节点）。

“头部节点的指针是否指向第二个节点？”

• 是：
  • 头部节点（无论是数据节点还是哨兵）的 next 指针始终指向链表的第二个节点。
  • 例如：
    • 插入前：头部A的 next 指向B
    • 插入后：头部C的 next 指向A

4. 链表类型对比

总结

1. 头部节点通常存储有效数据（除非使用哨兵节点）。
2. 插入到头部时，新节点一定会成为链表的起始节点：
   • 无哨兵：成为实际头部节点
   • 有哨兵：成为第一个数据节点
3. 头部节点的 next 指针始终指向第二个节点，这是链表的基础结构特性。
4. 头指针（HEAD）的修改不属于节点操作，它是外部指针的更新，不纳入"节点指针修改次数"的统计。