数组和链表的区别

数组（Array）和链表（Linked List）是计算机科学中最基础的两种线性数据结构。它们在内存分配、操作效率以及适用场景上有着本质的区别。以下是它们的核心对比：

1. 内存存储方式

• 数组：在内存中是连续分配的。这意味着一旦创建了数组，它在内存中占据的是一段完整的空间。
• 链表：在内存中是离散分配的。链表的节点可以存在于内存的任何位置，节点之间通过保存下一个节点的内存地址（指针/引用）来串联。

2. 增删改查的效率差异

• 随机访问（查询）：
  • 数组极快：因为内存连续，可以通过索引直接计算出目标元素的内存地址，时间复杂度为 O(1)。
  • 链表较慢：不支持随机访问。要找到第 N 个元素，必须从头节点开始顺着指针逐个遍历，时间复杂度为 O(N)。
• 插入与删除：
  • 数组较慢：如果在中间插入或删除元素，为了保持内存的连续性，必须将该位置之后的所有元素整体向后或向前移动，时间复杂度为 O(N)。
  • 链表极快：只要找到了目标位置，修改前后节点的指针指向即可，不需要移动任何元素，时间复杂度为 O(1)。（注：如果包含“查找目标位置”的时间，则依然是 O(N)）。

3. 空间大小与扩容机制

• 数组：通常在创建时就需要指定固定的大小。如果元素满了需要扩容，就必须申请一块更大的新内存，并将旧数据全部复制过去，这个过程比较消耗性能。
• 链表：天生支持动态大小。每次添加新元素时，只需动态申请一个新节点的空间即可，不存在扩容和整体数据迁移的问题。

总结与选型建议

在实际开发中如何选择？

• 选择数组的场景：当你需要频繁地根据索引读取数据，或者数据量相对固定、较少进行中间位置的增删操作时（例如：缓存列表、配置项）。此外，由于数组内存连续，对 CPU 缓存极其友好，遍历速度通常比链表更快。
• 选择链表的场景：当你的业务需要极其频繁地在头部或中间进行数据的插入与删除，且很少进行随机索引查找时（例如：实现 LRU 缓存淘汰算法、消息队列、音乐播放器的上一首/下一首切换）。