链表(Linked List)

定义

链表是由若干节点组成的线性结构，每个节点保存数据和指向下一个节点的指针。常见形式有单向链表、双向链表和循环链表。与数组不同，链表节点在内存中无需连续。

原理

节点通过指针逐个串联，访问元素必须从头节点沿指针逐步遍历。插入和删除只需修改相邻节点的指针，不需要移动其他元素，因此在已知位置时效率很高；但无法像数组那样按下标直接定位。双向链表额外保存指向前驱的指针，便于反向遍历和 O(1) 删除已知节点。

复杂度

• 按位置访问/查找：O(n)
• 已知节点处插入/删除：O(1)
• 头部插入：O(1)
• 空间复杂度：O(n)（额外存指针）

应用场景

• 频繁在中间插入删除、不要求随机访问的场景
• 实现栈、队列、哈希表的拉链法冲突链
• LRU 缓存（双向链表配合哈希表）