一、單鏈表

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。