Skip to main content

1 / 4概念

Linear Structures

线性结构把元素排成一条序列,区别在于元素在内存里是否连续、插入删除是否移动、查找靠不靠哈希。判断标准不是“数组还是链表高级”,而是访问模式、更新位置、内存布局和是否需要顺序。

1 概念​

1.1 一句话定义​

线性结构是元素之间只有前驱/后继关系的容器:数组用连续内存和下标寻址,链表用节点指针串起来,栈/队列/双端队列约束访问端点,哈希表用哈希函数把键映射到桶以实现平均 O(1) 查找。

1.2 它解决什么问题​

  • 随机访问:数组用下标 O(1) 定位,是缓存、缓冲区、矩阵的基础。
  • 频繁插删:链表在已知节点处 O(1) 接入/摘除,不需要搬移后续元素。
  • 顺序约束:栈保证后进先出,队列保证先进先出,双端队列两端都可进出。
  • 键值查找:哈希表把“按键找值”从 O(n) 降到平均 O(1),是字典、缓存、去重的默认结构。

1.3 不属于本页的内容​

主题去哪
二叉树、平衡树、B+ 树、堆Trees & Heaps
邻接表、邻接矩阵、并查集Graph Structures
排序与二分查找Sorting & Searching
渐进记号与摊还分析Complexity Analysis
并发容器、锁与无锁队列并发与操作系统相关页面

1.4 关键术语​

术语含义容易混淆的点
连续存储元素在内存中相邻不是“逻辑上连续”
动态数组容量可增长的连续数组扩容不是免费的
摊还 O(1)一串操作的平均代价单次仍可能 O(n)
负载因子元素数 / 桶数链式可大于 1,开放寻址必须小于 1
冲突不同键落到同一桶冲突不可避免,只能管理
开放寻址冲突时在表内找下一个空位删除要墓碑或重排
链地址法每个桶挂一条链表/红黑树额外指针和分配开销
哨兵不存数据的边界节点简化边界判断,不是业务数据
迭代器失效修改容器后旧迭代器不可用不同容器规则不同
环形缓冲区头尾下标取模复用数组满/空判断要额外计数