顺序表与链表的对比
本节把顺序表和链表放在一起比较。
顺序表和链表都可以实现线性表，但它们的存储方式不同，导致操作成本和适用场景也不同。理解这组对比，可以帮助你在真实问题中做出更合适的结构选择。
存储方式不同
Section titled “存储方式不同”顺序表使用连续空间保存元素。元素在内存中按顺序排列，逻辑顺序和存储顺序一致。
链表使用节点保存元素，每个节点通过指针或引用找到下一个节点。节点之间不要求连续存放，只要连接关系正确，就能表达线性顺序。
可以简单理解为：
顺序表：元素排在连续格子里链表：元素分散存放，通过线连起来这个差异会直接影响访问、插入、删除和空间成本。
访问能力不同
Section titled “访问能力不同”顺序表支持高效随机访问。只要知道下标，就能直接定位元素，通常是 。
链表不支持高效随机访问。即使你想访问第 100 个节点，也通常需要从头节点开始，沿着连接关系走过去。因此，链表按位置访问通常是 。
如果一个场景经常需要根据下标访问元素，顺序表往往更合适。
插入删除成本不同
Section titled “插入删除成本不同”顺序表在中间插入或删除元素时，通常需要移动后续元素来保持连续性。因此，在开头或中间插入删除的最坏时间复杂度通常是 。
链表插入删除时主要修改连接关系。如果已经知道相关节点，插入和删除本身通常是 。但是，如果需要先查找位置，查找过程仍可能是 。
所以不能简单地说“链表插入删除一定更快”。更准确的说法是：链表在已知节点位置时，插入删除的局部操作更高效。
空间使用不同
Section titled “空间使用不同”顺序表只需要保存元素本身。如果使用动态数组，可能会预留一部分空余容量，但整体结构比较紧凑。
链表中的每个节点除了保存数据，还需要保存指向下一个节点的指针或引用。因此，链表通常有额外空间开销。
同时，顺序表连续存储，对缓存更友好；链表节点可能分散在内存各处，遍历时可能不如顺序表高效。
适用场景不同
Section titled “适用场景不同”顺序表更适合：
- 经常按下标访问元素。
- 经常遍历所有元素。
- 数据量相对稳定。
- 插入删除主要发生在末尾。
- 希望存储结构紧凑。
链表更适合：
- 不需要频繁按下标访问。
- 经常在已知节点位置插入或删除。
- 数据规模变化较频繁。
- 不方便提前申请连续大空间。
- 需要灵活调整节点连接关系。
选择结构时，不要只看单个操作，而要看整个场景中最频繁的操作是什么。
一个常见误区
Section titled “一个常见误区”很多初学者会记住一句话：“数组查询快，链表增删快。”
这句话有一定道理，但不够严谨。
更准确的理解应该是：
- 顺序表按下标访问快。
- 顺序表按值查找不一定快，通常仍需要 。
- 链表在已知节点位置时插入删除快。
- 链表如果需要先查找位置，整体仍可能是 。
顺序表和链表都是线性表的实现方式，但它们的核心取舍不同。
顺序表用连续空间换来高效随机访问和紧凑存储；链表用额外引用换来更灵活的插入删除。选择哪一种结构，要根据操作频率、数据规模、空间需求和实现复杂度综合判断。