4、链表
4.1、使用场景
- 在许多列表，队列和堆栈实现中使用；
- 非常适合创建循环列表；
- 可以轻松地对诸如火车等现实世界的物体进行建模；
- 某些特定的Hashtable实现用于处理散列冲突；
- 用于图的邻接表的实现中。
4.2、术语
Head：链表中的第一个节点；
Tail：链表中的最后一个节点；
Pointer：指向下一个节点；
Node：一个对象，包含数据和Pointer。
4.3、实现思路
这里使用双向链表作为例子进行说明。
4.3.1、插入节点
往第三个节点插入：x
从链表头遍历，直到第三个节点，然后执行如下插入操作：
遍历到节点位置，把新节点指向前后继节点：
后继节点回溯连接到新节点，并移除旧的回溯关系：
前继节点遍历连接到新节点，并移除旧的遍历关系：
完成：
注意指针处理顺序，避免在添加过程中导致遍历出现异常。
4.3.2、删除节点
删除c节点：
从链表头遍历，直到找到c节点，然后把c节点的前继节点连接到c的后继接节点：
把c节点的后继节点连接到c的前继节点：
移除多余指向关系以及c节点：
完成：
同样的，注意指针处理顺序，避免在添加过程中导致遍历出现异常。
4.4、时间复杂度
| 操作 | 单向链表 | 双向链表 |
|---|---|---|
| 查找 | O(n) | O(n) |
| Insert at head | O(1) | O(1) |
| 中间追加 | O(n) | O(n) |
| 尾部追加 | O(1) | O(1) |
| 头部移除 | O(1) | O(1) |
| 尾部移除 | O(n) | O(1) |
| 中间移除 | O(n) | O(n) |
4.5、编程实践
-
JDK中的实现：
java.util.LinkedList -
练习：