【第1章】数据结构

摘自《我的第一本算法书》，用漫画方式理解数据结构。以下是阅读后的要点整理。

什么是数据结构

数据结构是「数据的排列方式」。同样的数据，用不同结构存储，查找、插入、删除的效率完全不同。选错结构，程序就会变慢。

数组（Array）

元素在内存中连续排列，通过索引直接访问。

适合：数据量固定、频繁按下标访问的场景。

索引: 0 1 2 3
[10] [20] [30] [40]

链表（Linked List）

每个节点存数据和指向下一个节点的指针，内存不必连续。

*已知节点位置时 O(1)，查找位置需 O(n)。

适合：频繁在头部或中间增删的场景。双向链表可 O(1) 删除已知前驱的节点。

栈（Stack）

后进先出（LIFO），只在一端操作。

• push：入栈
• pop：出栈
• peek：查看栈顶

应用：函数调用栈、括号匹配、撤销操作、DFS。

队列（Queue）

先进先出（FIFO），一端入队一端出队。

• enqueue：入队
• dequeue：出队

应用：BFS、任务调度、消息缓冲。双端队列（Deque）两端都可操作。

散列表（Hash Table）

通过哈希函数将 key 映射到数组下标，理想情况下查找 O(1)。

hash("apple") % size → 下标 3 → 存取

冲突处理：

• 链地址法：同一槽位用链表存多个元素
• 开放寻址法：冲突时探测下一个空槽

负载因子过高时需扩容并 rehash。

如何选择

读后感

这本书用漫画降低了入门门槛，但核心要记住的是：没有万能的数据结构，只有适合当前场景的选择。理解每种结构的优缺点，比背定义更重要。