一、先从一道实际业务问题说起数据结构学的到底是什么我最早产生“数据结构得好好补课”的念头是因为一个再普通不过的接口性能问题。当时某个后台模块需要给用户展示最近半年的行为记录数据量撑死也就几十万行数据库完全hold得住可接口就是慢而且是越来越慢。慢在哪后来定位到排序和倒序取值那块每次都要把全量数据取出来再排一遍时间全耗在“取出来”和“排一遍”这两个动作上。当时如果脑子里有清晰的“数据结构”观念根本不会这么写。数据的存储和组织方式直接决定了数据的访问方式而访问方式决定了时间复杂度和空间复杂度。同样是存一条记录塞进数组里和塞进链表里读法和写法完全不一样同样是查一条数据哈希表能做到平均O(1)二叉搜索树能做到O(log n)而数组线性扫一遍是O(n)。这不是什么考试知识点而是每天写代码都在用的事实。从这个引子出发这篇文章把最常用的八种基础数据结构拿出来逐个过一遍。这八种结构分别是数组、链表、栈、队列、哈希表、树、堆、图。它们覆盖了绝大多数业务场景存储、检索、排序、调度、路由、缓存、TopN、范围查询……说白了后端实现功能靠的是业务逻辑但让功能跑得稳、跑得快靠的是数据结构。文章不会去堆定义我按自己的习惯来每种结构先讲它“天生适合解决什么问题”再用一小段代码示例把它落地最后补一些我实际用的时候踩过的坑。标题里说“附示例截图”但帖子里的示例我统一用可运行的代码片段代替效果比截图更直接复制下来就能玩。二、线性结构四件套数组、链表、栈、队列的实战场景线性结构是最基础的一类容器它们的共同点是数据排列在一条线上遍历逻辑一维展开。但同样是线性的四种结构的取舍和使用场景差异非常大。2.1 数组连续内存带来的“确定性”和“代价”数组最核心的资本是内存连续、按下标随机访问时间复杂度O(1)。CPU缓存加载数据是按块预取的数组遍历起来对缓存特别友好——这一点在数据量大以后体现得很明显。另一个特征是扩容代价动态数组满了之后扩容要把老数据整体搬到新位置均摊下来是O(1)但单次扩容可能很疼。我经常跟新人说一句话当你需要“频繁随机读取、按位置访问”时优先考虑数组当你需要“频繁在头部或中间增删”时要非常小心。数组头插的代价是O(n)因为后续元素全部要往后挪挪完还要考虑容量够不够。实际业务里最典型的数组应用是各种内存缓冲、日志环形缓冲、矩阵运算的底层存储以及哈希表解决冲突时的“开放地址法”底层形态。写个小示例感受一下数组和链表在“头部插入”上的差别import time import sys # 动态数组头部插入 arr [] start time.time() for i in range(100000): arr.insert(0, i) # 每次插入都要移动后面所有元素 print(数组头部插入10万次耗时:, time.time() - start) # 链表用collections.deque模拟头插实际是双向链表 from collections import deque linked deque() start time.time() for i in range(100000): linked.appendleft(i) # 头插是O(1) print(链表头部插入10万次耗时:, time.time() - start)跑完这个对比你就能直观感受到为什么“头插”选链表而不是数组。注意Python内置的list本质上是动态数组不是链表。很多刚从C语言转过来的同学容易搞混。数组的另一面是“定长空间的浪费”。动态数组的容量通常会比实际元素多预分配会白白占用内存。在Java里ArrayList默认初始容量是10扩容到原容量的1.5倍Python的list扩容机制也类似只不过增长倍数不一样。理解这个机制你就知道为什么“先new一个大容量数组再填充”在某些场景下反而比反复自动扩容更省时间。2.2 链表用指针换来插入删除自由链表的核心特征是节点分散在内存各处连接靠指针/引用。所以它随机访问是O(n)但已知节点位置的插入和删除是O(1)。它的代价也很直观每个节点额外存一个next指针双向链表还要存prev内存占用比数组高加上节点内存不连续遍历时缓存命中率低所以同一份数据用链表遍历通常比数组慢。链表的经典应用我印象最深的三个LRU缓存、内存池、文件系统的块链表。LRU缓存几乎是最经典的双向链表哈希表组合哈希表提供O(1)查找双向链表提供O(1)的插入删除。每次访问一个key把它挪到链表头部超出容量时淘汰尾部节点。这个组合实现“按访问时间排序”的结构在系统设计里反复出现。内存池里空闲块的管理经常用空闲链表分配一块就摘下一个节点释放一块就重新挂回链表时间开销固定。文件系统的块链表则是为了解决“文件内容不连续存储”问题每个块记录后继块的地址虽然现在更多用索引节点但链表的思想依然贯穿其中。链表“O(1)插入删除”有个前提你已经定位到了那个节点。如果单单给定一个值要“先找到再删”那还是O(n)。这个细节面试必问实际写代码也容易忽略。我见过一个同事把“删除LinkedList中间某元素先遍历”理解成O(1)导致热点接口性能下降后来换成“把下一个节点的值拷贝到当前节点再删除下一个节点”才解决——这是一种常见的链表删除技巧面试题“在单链表中删除指定节点不提供头节点”就是这么解的。2.3 栈后进先出是天然的“回溯”模型栈这个结构非常简单但它的思想渗透在各个角落。函数调用就是栈浏览器后退是栈编辑器撤销是栈递归本身就是隐式栈。看到“最近”“最外层”“短时间内连续嵌套”这类字眼第一反应应该是栈。举一个最典型的例子括号匹配校验。遍历字符串遇到左括号入栈遇到右括号看栈顶是否匹配匹配就弹出到最后栈是空的说明全部闭合。这个逻辑用栈写干净利落def is_valid_brackets(s: str) - bool: stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in ([{: stack.append(ch) else: # 栈空说明右括号多了或者栈顶不匹配 if not stack or stack[-1] ! pairs[ch]: return False stack.pop() return len(stack) 0实际生产里栈不光处理括号。表达式求值的“中缀转后缀”就是典型的栈操作很多模板引擎要处理嵌套标签的闭合也是栈模型。函数调用栈的深度还从侧面解释了一个常见问题递归写多了会栈溢出。有些人一上来就开大数组做全局递归结果程序运行时爆栈就是因为每次递归调用都会在系统栈上压一层帧深度太高就溢出了。解决办法是把递归改成显式的栈迭代或者改成循环。我在工程中另一条经验是实现“撤销/重做”功能时如果只有单层回溯用栈就够了如果要支持分支历史、回退后重新编辑栈就不好使了得用带版本的链表或树结构。栈能解决的是“线性回溯”不能解决“树形回溯”这个边界要分清。2.4 队列先进先出为一切缓冲和公平调度兜底队列是先进先出的模型它解决的核心问题就是一个字序。谁先来谁先处理大家有序、公平不插队。工程上消息队列、任务队列、线程池的等待队列本质都是这个思想。BFS广度优先搜索也依赖队列因为它天然要求“先访问的节点的邻居先被访问”。队列最简单的落地是“用列表模拟”但工程上如果要追求性能和确定性的内存占用需要实现成环形队列。环形队列的好处是不反复移动元素通过头和尾的下标循环复用空间而且容量设置为2的幂的时候(tail 1) (cap - 1)比取模更快虽然现代编译器对取模2的幂也有优化但自己用位运算实现时更显清晰。class RingQueue: def __init__(self, capacity): # 为了好计算容量按2的幂取 self.cap capacity self.data [None] * capacity self.head 0 self.tail 0 self.size 0 def push(self, val): if self.size self.cap: raise OverflowError(queue full) self.data[self.tail] val self.tail (self.tail 1) % self.cap self.size 1 def pop(self): if self.size 0: raise IndexError(queue empty) val self.data[self.head] self.head (self.head 1) % self.cap self.size - 1 return val def is_full(self): return self.size self.cap环形队列在音频缓冲、网络收发包缓冲、底层驱动里到处都是很多系统性能问题的根因就出在“缓冲设计用了列表反复pop(0)”那个操作的复杂度是O(n)换成环形队列立刻不一样。栈和队列放在一起说的时候有一个有意思的对比我们常说的“双端队列”可以用来实现栈也可以用来实现队列也可以实现滑动窗口。滑动窗口最大值问题经典解法就是单调队列——双端队列里存下标保证队头是窗口内最大值的下标这个解法既能练结构又能练思维。三、哈希表和树形结构检索与有序性怎么权衡进入非线性结构之前先抛一个最关键的问题你到底是“按key精确查”还是“按顺序范围查”这两个需求导向完全不同前者是哈希表的地盘后者是树的强项。3.1 哈希表用空间和时间互相换代价是“无序”哈希表的核心是哈希函数 冲突解决。理想状态下每个key通过哈希函数映射到数组中的一个槽位查找、插入、删除都是O(1)。但哈希冲突是不可避免的解决冲突常用的两种方式一是链地址法冲突的key挂在同一个槽位下的链表二是开放地址法冲突了往后探测下一个空位。理解哈希表的关键是看三个概念负载因子元素数量/桶数量。负载因子越高冲突概率越大性能下降越快。Java的HashMap负载因子默认0.75到了就扩容。Python的dict也有类似的扩容机制。扩容rehash扩容时要重新计算所有key的哈希并搬移位置这个操作是O(n)所以“一次性塞几百万条数据进空哈希表”可能引发多次扩容耗时飘忽有时候可以先预估容量初始化避免中途多次rehash。哈希函数的均匀性哈希函数如果写得太烂大量key映射到同一个槽位链表会越挂越长性能从O(1)退化成O(n)。最典型的是字符串哈希如果只是取字母ASCII码的和那么 abc 和 cba 会落到同槽位一堆短字符串会集中在部分桶里分布。哈希表工程上最常见的应用是“字典/Map”、“缓存”、去重、索引映射、布隆过滤器底层等。几乎所有编程语言的标准库里都有它的踪影但很少有人细想它的“无序性”带来的坑。我举一个真实场景做排行榜功能时为了快速按用户ID取分数我把数据存在哈希表里后来要输出“分数前100名”我直接遍历整个哈希表排序压测之后发现延迟很高。问题不在排序本身几百万元素排序也就一两秒在于每次都要全量遍历。正确的做法是维护一个堆或者数据库索引让“TopN”查询不依赖全表扫描。哈希表天生擅长的是“点查”不擅长“范围查”和“顺序遍历”这是选型的时候要牢牢记住的。为了直观展示“点查”的优势可以做个简单测试import time data_list list(range(2000000)) data_dict {i: i for i in range(2000000)} target 1999999 t0 time.time() count 0 for i in range(10000): if target in data_list: # 列表in是O(n) count 1 print(列表查找耗时:, time.time() - t0, count) t0 time.time() count 0 for i in range(10000): if target in data_dict: # 字典in是O(1) count 1 print(字典查找耗时:, time.time() - t0, count)跑几次感受下数量级差距比空谈原理强得多。3.2 二叉搜索树与平衡树有序数据结构的主力如果说哈希表擅长“点查”二叉搜索树BST擅长的是“有序性操作”。BST的基本性质是左小右大所以中序遍历出来天然有序。在此基础上它可以支持范围查询、找前驱、找后继、求排名这些都是哈希表做不了的。但普通BST有个致命缺陷插入顺序如果是有序的比如从小到大BST会退化成链表树的高度变成n查找退化成O(n)。用数据说话一个有序序列构造普通BST查尾部元素和线性扫一遍没区别。所以生产环境用的是平衡树比如AVL树、红黑树。红黑树这个名字在面试里出现频率很高但工程上更重要的是理解它的定位它是一棵近似平衡的二叉搜索树保证最长路径不超过最短路径的两倍插入、删除、查找都是O(log n)。Java的TreeMap、C的std::map、Linux内核的一些调度器结构用的就是红黑树思想。实际应用中树最核心的业务场景是数据库索引。B树和B树都是树结构的变体设计初衷是减少磁盘I/O次数。B树把数据全放在叶子节点并串成链表非常适合范围查询和顺序遍历B树则在内层节点也能存数据查询可能提前命中。这个话题展开能写一本书这里点到为止但你要知道MySQL的InnoDB索引、MongoDB的索引底层都离不开树。树的另一个场景是文件系统目录结构本身就是一棵多叉树遍历目录就是树的遍历。要计算一个目录下所有文件的总大小用DFS还是BFS都行但要注意递归深度目录嵌套太深会栈溢出。实际上很多语言的文件遍历API在遇到深层目录时会抛异常就是因为递归栈太深了改成迭代式DFS显式栈就很稳。写一段BST的查找和范围查询的示例class TreeNode: def __init__(self, val): self.val val self.left None self.right None def insert(root, val): if root is None: return TreeNode(val) if val root.val: root.left insert(root.left, val) else: root.right insert(root.right, val) return root def range_search(root, low, high, result): if root is None: return if low root.val high: result.append(root.val) if root.val low: range_search(root.left, low, high, result) if root.val high: range_search(root.right, low, high, result)注意上面range_search里利用BST的性质做了剪枝当前值还大于等于下界就搜左子树小于等于上界就搜右子树这样范围查询不会全树遍历。3.3 堆不关心全局有序只关心“最大/最小堆顶”堆是一种特殊的完全二叉树常用数组存储。最大堆的堆顶是最大值最小堆的堆顶是最小值。它只保证局部关系父节点永远大于或小于子节点但同一层之间不保证有序。这个特性让堆特别适合处理“只关心最大/最小”的场景典型就是TopK问题、优先队列、定时器管理。Python里用heapq模块操作堆但它是小根堆。要求TopK最大时有两种常见做法维护一个大小为K的小根堆如果新元素比堆顶大弹出堆顶再入堆最后堆里的K个就是最大的K个。反过来如果要求最大的K个有时候直接nlargest(k, iterable)更简洁但底层其实也是堆算法的变体。写一个TopK“用户活跃度最大100个”的典型实现import heapq def topk(iterable, k): heap [] for item in iterable: if len(heap) k: heapq.heappush(heap, item) elif item heap[0]: heapq.heapreplace(heap, item) return heap # 堆内顺序不是整体有序但包含了topk元素很多人第一次写这个会疑惑为什么不是“把所有的都压进堆然后pop K次”“压进堆再pop K次”的时间复杂度是O(n k log n)维护K大小的堆处理每一个元素是O(n log K)。“压进堆再pop K”在K远小于n的时候其实也不差但如果n很大、内存有限维护K大小的堆可以只保留K个元素在内存里这对超大批量数据、流式数据非常关键。所以堆的TopK在内存约束场景下更有优势。堆的另一个常见应用是定时器管理用一个最小堆按超时时间排序每次只检查堆顶是否超时复杂度O(log n)比遍历所有定时器高效得多。Dijkstra最短路径算法里也用到了优先队列最小堆每次从堆里取出当前距离最小的节点这是“贪心优先队列”的经典组合。还有一个容易忽视的用法维护流数据的中位数。可以用两个堆一个大根堆存较小的一半一个小根堆存较大的一半保持两边数量差不超1中位数就是两个堆顶之一。这个技巧在数据量动态增长、实时流式场景很常用。四、图的定位网络建模的底层语言图是我觉得最容易“眼高手低”的一个结构。光看定义好像很简单顶点和边而已。但实际应用里图的难点不在于“建图”而在于“在图上做什么”——最短路、可达性、连通分量、拓扑排序、最小生成树每一个都对应一类实际业务问题。八种基础数据结构里图是结构上最复杂、内容最多的一种也是很多算法面试痛点的来源。4.1 图的表示法邻接矩阵和邻接表选型看“稀疏/稠密”图要先解决存储问题。两种最常用的表示方式邻接矩阵用二维数组存边matrix[i][j]1表示i到j有边有向、加权也可以存权重。优点是判断两个顶点是否相邻是O(1)缺点是空间复杂度O(V^2)顶点数上万之后矩阵会巨大无比。适合稠密图。邻接表每个顶点挂一张邻居列表空间复杂度O(VE)适合稀疏图。绝大多数实际业务图都是稀疏的所以邻接表是主力。工程上邻接表怎么实现最粗犷的是一个dict映射到list。但要注意如果边的操作频繁增删、查权重可以升级为dict映射到dict。我用Python经常是graph {} graph[1] [(2, 5), (3, 8)] # 邻接表顶点1可以到顶点2权5、顶点3权8另一种常见写法是把邻接表直接存成二维列表用数组下标表示顶点编号这样对密集操作更友好。判断一个图是否“稠密”的参考依据是边数和顶点数的关系。如果E远小于V^2就是稀疏图。实际社交网络里每个人平均好友几十上百个顶点几百万显然用邻接矩阵会直接内存爆炸邻接表才是合理选择。4.2 BFS和DFS的工程用途不只是算法题图的BFS可以求无权图的最短路径因为BFS天然按层遍历先到达某顶点的路径一定是最短边数。DFS则适合做可达性判断、连通分量、拓扑排序、环检测。实战里最能体现图结构威力的是依赖分析。一个典型的场景构建系统需要知道模块的编译顺序模块之间有依赖边A依赖B那么B必须先构建。这个问题用拓扑排序解决而拓扑排序的本质就是对DAG有向无环图做DFS或者Kahn算法。环怎么办有环就说明存在循环依赖拓扑排序做不了必须先告警。另一个实际应用是无权最短路径的传播层数。比如好友关系、消息传播。用BFS算两个用户之间的“距离”在很多业务里就是一个常见需求from collections import deque def shortest_path_bfs(graph, start, target): if start target: return 0 queue deque([start]) visited {start} distance 0 while queue: distance 1 for _ in range(len(queue)): node queue.popleft() for neighbor in graph.get(node, []): if neighbor not in visited: if neighbor target: return distance visited.add(neighbor) queue.append(neighbor) return -1 # 不可达值得注意的一个工程细节以“层”为单位做BFS时要在循环里固定for _ in range(len(queue))不然你无法区分当前是哪一层会导致路径长度计算错误。这个问题我在笔试里见过不少人栽过。图的DFS如果递归深度过深也会爆栈。像深度很大的图结构去遍历几十万层递归是顶不住的。处理大图遍历一个常用的解法是“显式栈”代替系统递归调用栈。显式栈本质上还是模拟递归过程只是栈的空间自己掌控不受系统递归深度限制。五、八种结构横向对比一张表说清选型逻辑前面把每个结构单独过了现在拉通做一次横向对比。数据结构的选型本质就是在“时间复杂度、空间复杂度、工程复杂度、适用场景”之间做权衡。结构查找插入删除空间特点核心能力典型场景数组O(1)按下标O(n)移位O(n)移位连续内存可能有预留空间随机访问、缓存友好内存缓冲、矩阵、动态数组链表O(n)O(1)已知节点O(1)已知节点节点指针额外内存频繁增删已知位置LRU、内存池、文件分块栈O(n)O(1)栈顶O(1)栈顶连续或链式后进先出、回溯函数栈、撤销、表达式求值队列O(n)O(1)队尾O(1)队头连续或链式先进先出、缓冲消息队列、BFS、任务调度哈希表O(1)平均O(1)平均O(1)平均数组桶负载因子控制key点查、去重字典、缓存、布隆过滤器底层树平衡O(log n)O(log n)O(log n)节点指针有序、范围查询数据库索引、TreeMap、目录堆O(1)取堆顶O(log n)O(log n)删堆顶数组存储完全二叉树最大/最小TopK优先队列、定时器、TopK图---邻接表O(VE)多跳关系建模社交网络、地图导航、依赖分析这个表有两点要提醒第一表里的复杂度是“平均”或“典型”的不是全部情况。比如普通BST最坏O(n)但平衡树是O(log n)。哈希表在冲突严重时退化成O(n)好设计要控制负载因子和哈希函数。第二选型不能只盯着时间复杂度的渐近系数。比如数据量很小的时候数组遍历可能比哈希查找更快因为哈希查找有哈希计算和缓存不命中的成本。说是“大数据结构”的选型真正的核心其实是“数据量变大以后谁更稳”小数据量的性能差异经常被代码整洁度和可维护性覆盖不要为了“炫技”选一个难维护的结构。还有一个特别常见的选型错误把所有数据塞进List然后用Stream/LINQ去各种查和排序。如果数据量只有几千完全没问题如果数据量到了几百万每秒被请求几十次那就是在浪费资源。查什么用哈希表排什么用树或堆范围查用有序结构结果集大小有限用TopK堆——这些判断要形成肌肉记忆。实际面试和系统设计里我经常被问到这样一个简化版问题设计一个系统支持“按用户ID查信息”也支持“按用户注册时间范围查出前N个注册的新用户”。第一步信息放哈希表点查O(1)第二步单独维护一个按注册时间排序的结构比如树或时间分区索引。这两个结构不冲突可以同时用只是要维护它们的一致性。很多人误以为“选了哈希表就不能做范围查询”事实是你可以维护多份结构服务于不同查询模式只是要承担额外的写入维护成本。这个取舍是工程核心。六、我的几个踩坑经验和给自学者的建议文章最后一部分不讲理论了聊聊我实际工作中和数据结构相关的几个坑和体会。这些东西不是看书能看出来的都是线上事故、压测报告、排查日志里磨出来的。第一个坑哈希表遍历求TopN。我前面已经提过但值得再强调一遍。一次排行榜需求数据结构选用了Map存储玩家分数上线初期很好后来玩家数到几百万需要输出全服前100名直接在Map上values()排序接口直接超时。后来改成“维护一个小顶堆只保留Top100”之后问题消除。核心思想非常简单不要为了TopN去遍历大容器用堆或预排序索引。第二个坑递归变遍历的“栈溢出”。我处理过一个定时任务递归遍历一个目录树深度大概两三万层Python递归直接报RecursionError。解决方式很简单把递归改成显式栈迭代。很多人知道这个方案但没实际改过等真正遇到的时候容易懵。技巧在于递归改迭代的时候要特别注意访问顺序前序遍历用栈存右子树后序遍历要加标记位写之前先在纸上走一遍。第三个坑链表的内存碎片和缓存不友好。这个概念是看《数据库系统实现》的时候才真正体会到的。链表遍历慢不只是因为O(n)访问更因为它的节点在内存里是离散的每次访问一个节点都要做一次内存随机访问缓存几乎帮不上忙。所以同样是O(n)遍历数组比链表快很多倍。实际工程里如果项目追求极致性能能用连续内存的优先用连续内存链表在内存占用和局部性上都吃亏。第四个坑图的邻接表里重复边问题。构建图的时候如果不做去重两条相同的边会让BFS/DFS重复遍历很多次。尤其从数据库批量建图时SQL查出来的关联关系可能天然有重复要在建图阶段或者读图阶段做一次去重。我见过一版程序因为没去重在图里多了几十倍冗余边导致最短路径计算结果正确但是慢得离谱。顺着这些经验谈一谈学习路线。如果读者是零基础我的建议是不要一上来就啃完全平衡树和红黑树的实现先把手写数组、链表、栈、队列四个基本结构练熟把它们的时间和空间复杂度问到自己能讲明白。接下来是哈希表的原理特别是为什么负载因子的控制这么重要这个既要看理论也要动手跑实验。之后再看树和堆树的重点是平衡树的性质和B树的应用场景堆的重点是TopK、优先队列、中位数模拟这几个实用的驾驶场景。图放在最后因为图涉及的方法论更多但你先掌握好“邻接表建图BFS/DFS”就够日常了。数据结构的学习方式我强烈建议手写一遍。写代码的过程不是重复实现“标准答案”而是逼自己去想“这个结构的内存形态到底是什么样”。比如手写完红黑树的人和不手写的人对“父子节点颜色变换”这种操作的理解完全不一样虽然业务代码可能永远用不到手写红黑树但这就像弹钢琴的哈农练习练的是手指肌肉也就是思维肌肉。我个人的习惯是每学一个结构就问自己三个问题它在现实世界里对应什么问题如果我不用它会用什么代替它在极端情况下会退化到什么程度三个问题想清楚这个结构才算真正装进脑子里。这个习惯救了我不止一次在真正写业务的时候很多“性能问题”都是因为初始选错了结构后面再用什么技巧优化都是隔靴搔痒。数据结构这东西不背不行但更不能死记——背的是各种结构的能力边界死的却是在实际场景里做权衡的能力。把上面八种结构的能力边界搞清楚工程里百分之八十的问题都能一眼看穿底层逻辑。