很多人在面试里栽跟头，不是栽在什么高深的算法上，而是栽在最基础的线性结构上。

比如被问一句”数组和链表的区别是什么”，能说出”数组连续、链表不连续”的人很多，但能讲清楚”为什么数组按下标访问是 O(1)、链表在中间插入是 O(1)”的人，就少多了。

这篇文章把这四种最基础的线性结构，从底层特性到复杂度一次讲透。

数组：连续内存，随机访问

数组的本质是一块连续的内存。

正因为连续，所以当你知道首地址和元素下标时，可以直接算出目标元素的地址：

1
目标地址 = 首地址 + 下标 × 元素大小

这个计算是常量时间的，所以数组按下标访问是 O(1)，这就是”随机访问”。

但也正因为连续，数组有两个代价：

  1. 插入和删除要搬移数据：在中间插入一个元素，后面的元素都要往后挪一位，平均 O(n)
  2. 扩容成本高：数组创建时要指定大小，满了就得申请更大的新数组、整体拷贝

数组的适用场景：读多写少、大小相对固定。

链表：离散内存，靠指针连接

链表的本质是每个节点存数据和下一个节点的指针，节点之间靠指针串联，不需要连续内存。

  • 优点：插入删除快（只需改指针，O(1)），天然支持动态扩容
  • 缺点：不能随机访问，要找第 n 个元素，必须从头一个个遍历，O(n)

链表的适用场景：频繁增删、不依赖随机访问。

一个容易忽略的点：链表虽然”插入是 O(1)”，但这个 O(1) 有个前提——你已经找到了插入位置。如果找位置本身要遍历（O(n)），那整体还是 O(n)。所以不要笼统说”链表插入快”，要分情况。

数组 vs 链表：一张表对比

操作 数组 链表
按下标访问 O(1) O(n)
头部插入 O(n) O(1)
尾部插入 O(1) O(1)
中间插入/删除 O(n) O(1)（已知位置）
内存 连续，可能浪费 离散，有指针开销
CPU 缓存友好度 高 低

面试技巧：讲到链表插入快，一定要补充”已知位置”这个前提，这会让你看起来真的懂，而不是背结论。

栈：后进先出（LIFO）

栈就像一个只能从顶部操作的盘子堆，后放进去的，先拿出来。

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

栈的应用场景非常多：

  • 函数调用栈：递归的本质就是系统在帮你维护一个栈
  • 括号匹配：左括号入栈，右括号出栈配对
  • 浏览器的前进后退：两个栈实现
  • 表达式求值：中缀转后缀

栈的意义在于：它能天然地”记住”之前的状态，并且按照”最近优先”的顺序回溯。

队列：先进先出（FIFO）

队列就像排队，先来的先处理。

  • enqueue：入队
  • dequeue：出队

队列的应用场景：

  • 消息队列：生产者消费者模型
  • BFS 广度优先遍历：就是靠队列实现的
  • 线程池的任务队列：任务按提交顺序执行

队列的意义在于：它保证处理顺序，天然适合”缓冲”和”公平调度”。

栈和队列的关系

栈和队列其实是一对”镜面”：

  • 栈是”后进先出”，队列是”先进先出”
  • 它们都可以用数组或链表来实现
  • 用两个栈可以实现一个队列，用两个队列也可以实现一个栈

理解了”线性结构 + 出入规则”，就理解了这四种结构的本质：它们都是”存储元素的容器”，区别只在于”怎么取出来”。

写在最后

这四种结构看起来简单，但它们是所有复杂数据结构的基石：

  • 哈希表是”数组 + 链表”的组合
  • 图是”顶点 + 边”，边可以用邻接表（链表）或邻接矩阵（二维数组）表示
  • 堆是”完全二叉树 + 数组存储”

把地基打牢，后面盖楼才稳。下一篇讲哈希表——它就是从”数组 + 链表”长出来的。