一、单链表

AcWing 826. 单链表

代码

N = 100010
idx = 0
e = [0] * N
ne = [0] * N
head = -1def init():global idx,headidx = 0head = -1def add_head(x):global idx,heade[idx] = xne[idx] = headhead = idxidx += 1def delete(k):ne[k] = ne[ne[k]]def add_k(k,x):global idxe[idx] = xne[idx] = ne[k]ne[k] = idxidx += 1def _print():i = headwhile i != -1:print(e[i],end=" ")i = ne[i]if __name__ == "__main__":m = int(input())init()for _ in range(m):op = list(input().split())if op[0] == 'H':add_head(int(op[1]))elif op[0] == 'D':k = int(op[1])if k == 0:head = ne[head]delete(k-1)else:add_k(int(op[1])-1, int(op[2]))_print()

解析

1、head 的作用

• head 是链表的入口指针。

• 初始时 head = -1，表示链表为空。

• 当链表有元素时，head 保存第一个节点的下标。

• 遍历链表时，从 head 出发，通过 ne[idx] 不断找到下一个节点，直到遇到 -1 结束。

---

2、关于 k-1 的问题

• 题意：将 x 插入到第 k 个插入的数后面。

• 实现时，数组下标是从 0 开始的，所以第 k 个插入的数下标是 k-1。

• 因此调用时是 add(k-1, x) 或 remove(k-1)。

• 如果初始化时 idx=1（而不是0），下标和 k 可以对齐，就不需要 k-1。

---

3、e[idx]、ne[idx] 与 idx 的关系

• 结点定义：链表的元素由 (e[idx], ne[idx]) 两部分组成。

• e[idx]：编号为 idx 的节点存储的值。

• ne[idx]：编号为 idx 的节点的下一个节点下标。

• idx 本身只是一个编号（不一定连续），节点顺序要通过 ne 串联起来。

---

4、删除头节点 head = ne[head]

• 删除的其实是链表的首元结点（第一个存值的结点）。

• 操作原理：把 head 移动到原来 head 的下一个节点，即 ne[head]。

• 这样就跳过了原首元结点，等价于删除它。

---

5、为什么最后一个节点的 ne[idx] = -1

• 初始时 head = -1，表示空链表。

• 插入第一个元素时：e[0] = val，ne[0] = -1，head = 0。

• 后续插入时，新节点的 ne[new] = head，再更新 head = new。

• 因为链表是靠 ne 串起来的，所以最后一个节点始终指向 -1，表示链表结束。

二、双向链表

AcWing 827. 双链表

代码

N = 100010
l = [0] * N
r = [0] * N
e = [0] * N
idx = 0def init():global idxr[0] = 1l[1] = 0idx = 2def delete(k):r[l[k]] = r[k]l[r[k]] = l[k]# 往k的右端插入  
def insert(k,x):global idxe[idx] = xr[idx] = r[k]l[idx] = kl[r[k]] = idxr[k] = idxidx += 1if __name__ == "__main__":m = int(input())init()for _ in range(m):op = list(input().split())if op[0] == "L":x = int(op[1])insert(0,x)elif op[0] == "R":x = int(op[1])insert(l[1],x)elif op[0] == "D":k = int(op[1])delete(k+1)elif op[0] == "IL":k = int(op[1])x = int(op[2])insert(l[k+1],x)else:k = int(op[1])x = int(op[2])insert(k+1,x)i = 0res = []while r[i] != 1:val = e[r[i]]res.append(val)i = r[i]print(" ".join(map(str,res)))

解析

1. 数组设计

   • e[idx]：存放编号为 idx 的节点的值。

   • l[idx]：存放编号为 idx 的左指针（前驱节点下标）。

   • r[idx]：存放编号为 idx 的右指针（后继节点下标）。

2. 哨兵节点（边界节点）

   • 下标 0 表示链表的 左端点（不存值）。

   • 下标 1 表示链表的 右端点（不存值）。

   • 初始化时：

     r[0] = 1 # 左端点指向右端点
l[1] = 0 # 右端点指向左端点
idx = 2 # 有效数据节点从下标 2 开始

3. 传入函数时要用 k+1

   • 哨兵占用了下标 0 和 1

     • 下标 0：左端点（不存值）。

     • 下标 1：右端点（不存值）。

     • 所以真正存数据的节点是从 idx = 2 开始。

   • 题目里的第 k 个插入操作 vs 实际数组下标

     • 第 1 次插入得到的节点，逻辑上是“第 1 个元素”，但它的数组下标是 2。

     • 一般情况：第 k 个插入的元素对应数组下标 k+1。