数组和链表是最基础的线性数据结构，理解它们是学习更复杂数据结构（栈、队列、哈希表）的前提。
一、数组（Array）
数组在内存中连续存储，通过下标访问。
- 优点：随机访问 O(1)，缓存友好
- 缺点：插入/删除中间元素要移动后续元素 O(n)
- 扩容：动态数组满后需复制到更大空间
二、链表（Linked List）
链表由节点组成，每个节点存数据和指向下一节点的指针，内存不连续。
class Node:
def __init__(self, val):
self.val = val
self.next = None- 优点：插入/删除 O(1)（已知节点位置时）
- 缺点：访问第 n 个元素要 O(n)，需遍历
- 额外开销：每个节点要存指针
三、复杂度对比
操作 数组 链表
访问 O(1) O(n)
头部插入 O(n) O(1)
尾部插入 O(1)* O(1)（有尾指针）
查找 O(n) O(n)
* 动态数组均摊选型原则：频繁随机访问用数组；频繁在头尾插入删除用链表。现代 CPU 缓存让数组在大多数场景更快。
四、链表变体
- 单向链表：只有 next 指针
- 双向链表：有 prev 和 next，可双向遍历
- 循环链表：尾节点指向头
五、典型应用
- 数组：缓存、查找表、动态规划
- 链表：实现栈/队列、LRU 缓存、多项式运算
- 双向链表 + 哈希表 = LRU 缓存的经典实现
六、常见面试题
- 反转链表
- 检测链表是否有环（快慢指针）
- 合并两个有序链表
- 数组去重、双指针求和
七、小结
数组和链表是基础中的基础。理解它们的时间空间权衡，是算法学习的起点。后续的栈、队列、树都建立在它们的思想上。