线性表 (Linear List)
1. 数组 (Array)
连续内存分配，索引访问 ，插入删除 。
- 动态数组 (Vector/ArrayList)
2. 链表 (Linked List)
非连续内存，节点包含数据和指针。
- 单链表：单向指针。
- 双向链表：前后指针。
- 循环链表：首尾相连。
3. 比较
| 特性 | 数组 | 链表 |
|---|---|---|
| 访问 | ||
| 插入/删除 | (已知位置) | |
| 空间 | 预分配/扩容 | 动态分配 |
连续内存分配，索引访问 O(1)，插入删除 O(n)。
非连续内存，节点包含数据和指针。
| 特性 | 数组 | 链表 |
|---|---|---|
| 访问 | O(1) | O(n) |
| 插入/删除 | O(n) | O(1) (已知位置) |
| 空间 | 预分配/扩容 | 动态分配 |