数据结构：链表与栈队列

线性家族的另一半纪律是 只从哪一端进出。Python 标准库不提供教科书式单链表类型；生产路径是：

纪律	用这个	不要用
栈（stack） 后进先出	list.append / list.pop	头插 insert(0, …)
队列（queue） 先进先出	collections.deque 的 append / popleft	list.pop(0)
双端队列（double-ended queue，deque）	同一个 deque 两头都动	手写双向节点当默认

段末注释：栈 / 队列 是 ADT（谁能进出），链表 是实现。CPython 的 deque 不是「一节点一元素」的链表，而是双向串起来的 64 槽指针块。

---

1. 为什么日常几乎不写链表

已知节点处插入删除是 (O(1))，但「找到那个节点」在 Python 里通常已经 (O(n))。每个节点一次堆分配、两次指针跳转，缓存极差。CPython 自己实现队列时，选择 块状双向链表：每块 64 个 PyObject*，块与块之间才有 prev / next。

deque
  leftblock ⇄ block ⇄ … ⇄ rightblock
  每块：[ptr × 64]
  leftindex / rightindex 标出两端用到哪一格

两端 append / pop 均摊 (O(1))，且不 realloc 整块数据。maxlen 满员时从对面丢掉，用来做滑动窗口。

---

2. 栈：list 就够

def eval_rpn(tokens):
    """后缀表达式求值（栈的经典用法）。

    输入：tokens，数字与 + - * / 的字符串序列。
    输出：计算结果 int。
    处理：数字入栈；遇到算符弹出两个操作数，算完压回。
    """
    st = []
    for t in tokens:
        if t not in {"+", "-", "*", "/"}:
            st.append(int(t))
            continue
        b, a = st.pop(), st.pop()
        if t == "+":
            st.append(a + b)
        elif t == "-":
            st.append(a - b)
        elif t == "*":
            st.append(a * b)
        else:
            st.append(int(a / b))  # 向零截断，对齐题面常见约定
    return st[-1]

递归调用栈也是栈，只是你看不见。显式 list 当栈的好处是可控、可迭代、不会撞递归上限。

线程间的栈用 queue.LifoQueue（内部有锁），不要多线程共用一个裸 list。

---

3. 队列与双端队列：deque

from collections import deque

def sliding_max(nums, k):
    """滑动窗口最大值。

    输入：nums 序列，窗口长 k。
    输出：每个窗口的最大值列表。
    处理：单调双端队列存下标，队头过期就弹，队尾小于当前就弹。
    """
    dq, out = deque(), []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

操作	deque	list
右端进/出	(O(1))	(O(1))
左端进/出	(O(1))	(O(n))
按下标	(O(n))（要跨块走）	(O(1))
按值查找	(O(n))	(O(n))

deque 不是数组：不要用它当随机访问容器。d[0] / d[-1] 可以，中间下标会慢。

线程安全队列：queue.Queue（FIFO）、queue.PriorityQueue（堆 + 锁）。单线程算法题不要用它们，锁是纯开销。

---

4. 手写链表：只为把指针讲清楚

生产代码默认不要走这条路。面试或要在已知节点 (O(1)) 摘链时才写。

class Node:
    """单向链表节点：value 为载荷，next 指向后继或 None。"""

    def __init__(self, value, nxt=None):
        self.value = value
        self.next = nxt


def reverse(head):
    """原地反转单向链表。

    输入：head，链头或 None。
    输出：新链头。
    处理：三指针 prev / cur / nxt 逐个掉头。
    """
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

双向节点多一个 prev，删除当前节点不必找前驱。循环链表让尾的 next 指回头，用来做约瑟夫环或环形缓冲的教学模型；工程环形缓冲用 deque(maxlen=…) 或一块 bytearray。

---

5. 组合体：哈希表 + 双向链表 = LRU

最近最少使用（Least Recently Used，LRU） 要同时：按键 (O(1)) 找到、(O(1)) 把该节点挪到「最新」端。标准库现成方案：

from collections import OrderedDict

class LRUCache:
    """容量固定的 LRU。

    输入：构造参数 cap 为正整数。
    get(key) → 值或 -1；put(key, value) 写入，超员淘汰最旧。
    处理：OrderedDict 保插入序，move_to_end 当「刷新」，popitem(last=False) 淘汰队头。
    """

    def __init__(self, cap):
        self.cap = cap
        self.od = OrderedDict()

    def get(self, key):
        if key not in self.od:
            return -1
        self.od.move_to_end(key)
        return self.od[key]

    def put(self, key, value):
        if key in self.od:
            self.od.move_to_end(key)
        self.od[key] = value
        if len(self.od) > self.cap:
            self.od.popitem(last=False)

函数结果缓存直接 @functools.lru_cache，不要自己造。OrderedDict 在 3.7+ 的普通 dict 已保序之后，仍多了 move_to_end / popitem(last=)，这才是它留下的理由。

---

6. 踩坑

1. list 当队列：pop(0) 总复杂度 (O(n^2))。
2. 多线程共用 deque：deque 两端操作大致原子，但「先看长度再 pop」不是原子。跨线程用 queue.Queue。
3. 在 deque 中间 insert：合法但 (O(n))，失去选它的意义。
4. 手写链表当默认容器：分配与缓存成本通常大于 list 搬指针。
5. 递归当队列：递归是栈，宽搜必须显式队列。

---

7. 自检

1. 用一张表说出栈 / 队列 / deque 在 CPython 里各用谁实现。
2. deque 为什么比「一元素一节点」快？块大小是多少？
3. 什么情况下值得手写 Node？
4. LRU 为什么必须「哈希 + 双向链（或 OrderedDict）」两样一起上？

---

8. 社区口径与风险

队列实现见 CPython Modules/_collectionsmodule.c（BLOCKLEN = 64）。算法题社区默认 from collections import deque。第三方几乎不必为「普通队列」再引包。风险：把 Java LinkedList 的用法直接翻译成 Python 手写链，常数会差一个数量级。