链表 - Hero · 算法 · Hello 算法
链表
内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。
「链表 linked list」是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。
链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。
常用操作
- 初始化链表
- 插入节点
- 删除节点
- 访问节点
- 查找节点
数组和链表的比较
| 数组 | 链表 | |
|---|---|---|
| 存储方式 | 连续内存空间 | 分散内存空间 |
| 容量扩展 | 长度不可变 | 可灵活扩展 |
| 内存效率 | 元素占用内存少，但有可能浪费空间 | 元素占用内存多 |
| 访问元素 | O(1) | O(n) |
| 添加元素 | O(n) | O(1) |
| 删除元素 | O(n) | O(1) |
常见链表类型
- 单向链表
- 环形链表
- 双向链表
链表 - Hero · 算法 · Hello 算法
https://wanmeishijie.xyz/notes/hero/algo/hello-algo/第4章 数组与链表(二)/