手写链表、栈、队列、二叉树和哈希表是掌握数据结构核心原理的关键：链表理解指针与动态内存；栈/队列厘清LIFO/FIFO底层控制；二叉树强化递归与遍历逻辑；哈希表揭示冲突解决与扩容机制。
手写链表：理解指针与动态结构的核心
链表是很多高级数据结构（如栈、队列、哈希表拉链法）的基础。手写单向链表能帮你真正理解“节点+指针”的内存逻辑。
关键点：
- 每个节点包含 数据域 和 next 指针
- 头节点不存实际数据，仅作入口；也可用普通节点作头，但需额外处理空链表
- 插入、删除时间复杂度为 O(1)（已知位置），查找为 O(n)
简单实现示例：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
<p>class LinkedList:
def <strong>init</strong>(self):
self.head = None # 空链表</p><pre class='brush:python;toolbar:false;'>def append(self, val):
new_node = ListNode(val)
if not self.head:
self.head = new_node
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = new_node手写栈和队列：LIFO 与 FIFO 的底层控制
Python 内置 list 可模拟栈（.append()/.pop()），但手写能明确边界行为和异常处理。
栈（Stack）：
- 基于数组或链表均可，数组更简洁
- 必须检查是否为空再 pop，否则抛 IndexError 或自定义异常
- 支持 push、pop、top、is_empty
队列（Queue）：
- 单链表实现最自然：头部出、尾部进，O(1) 均摊
- 避免用 list 的 pop(0)（O(n) 移动开销）
- 双端队列（deque）虽高效，但手写有助于理解 front/rear 指针维护
手写二叉树与遍历：递归逻辑的直观落地
二叉树不是容器，而是结构模型。手写节点类 + 常见遍历（前/中/后序、层序），能打通递归思维和指针跳转。
立即学习“Python免费学习笔记（深入）”；
要点：
- 节点含 val、left、right，初始均为 None
- 前序遍历 = 根 → 左 → 右；中序常用于 BST 排序输出；后序适合释放内存
- 层序遍历必须用队列（BFS），不能只靠递归
中序遍历递归版示意：
def inorder(root):
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
手写哈希表（简易版）：理解冲突与扩容本质
不必追求工业级性能，但应写出开放寻址或拉链法核心逻辑，明白为什么 dict 查找平均 O(1)。
推荐拉链法（更易懂）：
- 底层用 list 存 buckets，每个 bucket 是链表或 list（存 (key, value) 对）
- hash 函数用 hash(key) % capacity，注意负数取模修正
- 装载因子 > 0.7 时触发扩容（新建两倍容量数组，rehash 所有键）
- get 和 set 需先定位 bucket，再遍历查找 key（解决冲突）
关键细节：
- key 必须可哈希（不可变），否则运行时报错
- 相同 key 多次 set 应覆盖 value，不是追加
