链表四种结构与操作核心

§ 403 链表四种结构与操作核心#

一、问题#

单链表、双链表、循环链表的操作复杂度为什么各不一样？什么结构下能 $O(1)$ 访问尾部？循环双链表判空的条件为什么和普通双链表不同？

二、为什么是这样#

判断任意链表操作的复杂度，先问三个问题：

1. 什么结构：有头节点 / 有尾指针 / 双向指针 / 循环？
2. 操作在哪个位置：表头 / 表尾 / 中间？
3. 能 $O(1)$ 到达所需节点吗？找不到就要遍历 = $O(n)$。

三个关键设计的来龙去脉：

头节点：让第一个数据节点有前驱，消除表头操作的特判。判空：head->next == NULL。

尾指针（循环链表中常用）：链表只能从头顺序访问，找尾节点要遍历 $O(n)$。加了尾指针 rear 后，rear 直接是尾节点，rear->next 是头节点（循环结构），两端都是 $O(1)$。这是循环单链表用尾指针而不是头指针的原因。

双向指针（prev）：单链表只能向后，找前驱要从头遍历 $O(n)$。有了 prev 指针，已知节点地址就能 $O(1)$ 找前驱，从而 $O(1)$ 删除该节点或在该节点前插入。

循环双链表判空：循环结构中没有 NULL，头节点的 next 在空表时指向自身，判空是 head->next == head，而不是 head->next == NULL。

双链表插入步骤顺序很关键：先把新节点 X 的两端接好（X->next = B; X->prev = A），再改前后节点（B->prev = X; A->next = X）。顺序反了会丢失 B 的前驱。

三、关联#

• 1.3 单链表：单链表基础操作
• 1.4 链表变体：双链表、循环链表、静态链表的代码
• 401-单链表头节点的作用：头节点详细解释

四、我的理解#

三问法：①什么结构 ②操作在哪 ③能 $O(1)$ 到达操作节点吗？快速判断复杂度时直接问这三个，不用背表格。

循环双链表有个好处：head->prev 直接就是尾节点，不需要额外的尾指针也能 $O(1)$ 访问两端。