基本概念
结构：由一系列节点（node）组成的线性序列。
节点：包含两个部分，分别是
- 数据域：存放实际的数据元素
- 指针域：存储一个或多个引用，指向其他节点
特性：
- 非物理连续：节点在内存中不必连续存储
- 动态扩展性：可以快速增加或删除节点
- 顺序访问性：必须通过指针逐个访问，无法直接定位具体的某个元素
分类
单向链表
- 每个节点包含一个指向后继（next）节点的指针
- 终止于一个空指针（nullptr）
- 只能单向遍历
双向链表
- 每个节点包含前驱（prev）和后继（next）两个指针
- 支持双向遍历
- 需要更多的存储空间（存储前驱指针）
循环链表
- 尾节点的指针指向头节点，形成环状结构
- 可分为单向循环和双向循环两种变体
- 没有明确的开始和结束的概念
数组与链表
数组：存储内存连续，大小固定，可以直接访问某个元素（快），插入删除操作慢
链表：存储内存不连续，大小不固定，不能直接访问某个元素（慢），插入删除操作快
时间复杂度
访问
- 随机访问：O(n)
- 顺序访问：O(1)
插入
- 头插：O(1)
- 尾插：O(1)(有尾指针时)或O(n)
- 指定位置插：O(n)查找+O(1)插入
删除
- 头删：O(1)
- 尾删：O(1)(双链表)或O(n)(单链表)
- 指定元素删：O(n)查找+O(1)删除