双向链表
- 之前的单向链表只能通过 Node 中 next 属性从头遍历链表，完成搜索
- 双向链表中的 Node 增加 prev 属性，指向该节点上一个节点
- 双向链表查找元素可以从 first 或 last 两个方向开始查找，故而可以提高效率
- Java 官方 LinkedList 就是双向链表
实现双向链表
相比单向链表，双向链表需要重写查找节点、添加节点、删除节点、清空链表四个方法
1. 属性
增加 last 指向尾节点，Node 中增加 prev 指向前一个节点
public class LinkedList<E> {
// 当前链表元素的数量
private int size;
// 链表的头节点
private Node<E> first;
// 链表的尾节点
private Node<E> last;
// 未查找到元素下标的返回值
private static final int MINUS_ONE = -1;
// 节点内部类
private static class Node<E> {
// 前驱节点
Node<E> prev;
// 后继节点
Node<E> next;
// 存储的数据元素
E element;
// 构造器
Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
}
2. 构造器
// 构造器
LinkedList() {
first = null;
last = null;
size = 0;
}
3. 查找节点
判断要查找的位置是在链表前半段还是后半段，选择从前向后还是从后向前查找
// 查找节点
private Node<E> getNode(int index) {
checkRange(index);
if(index < (size>>1)) {
// 目标index小于长度的中间值，从前往后找
Node<E> node = first;
for(int i=0;i<index;i++) {
node = node.next;
}
return node;
}else {
// 目标index大于中间值，从后往前找
Node<E> node = last;
for(int i=size-1;i>index;i--) {
node = node.prev;
}
return node;
}
}
4. 添加元素
- 向链表尾部追加元素
- 空链表
- 非空链表
- 向非尾部插入元素
- 插入到第一个位置
- 其他位置
// 添加元素
public void add(int index,E ele) {
checkRangeForAdd(index);
// 向最后添加元素
if(index==size) {
Node<E> oldLast = last;
last = new Node<>(oldLast,ele,null);
// 如果链表是空的，添加的元素是第一个元素
if(oldLast==null) {
first = last;
}else {
oldLast.next = last;
}
}else {
// 插入位置原节点成为新节点的后继
Node<E> next = getNode(index);
// 插入位置原节点的前驱成为新节点的前驱
Node<E> prev = next.prev;
// 创建新节点
Node<E> node = new Node<>(prev,ele,next);
// 设置 next 的 prev
next.prev = node;
// 如果插入到第一个位置，也就是说 index==0
if(prev==null) {
first = node;
}else {
prev.next = node;
}
}
size ++;
}
// 向尾部添加元素
public void add(E ele) {
add(size,ele);
}
5. 删除元素
删除元素，将前驱的 next 指向后继，后继的 prev 指向前驱，如果是头节点 (prev==null) 或尾节点 (next==null) 需要特殊处理
// 删除元素
public E remove(int index) {
checkRange(index);
Node<E> node = getNode(index);
Node<E> prev = node.prev;
Node<E> next = node.next;
if(prev==null) {
first = next;
}else {
prev.next = next;
}
if(next==null) {
last = prev;
}else {
next.prev = prev;
}
size --;
return node.element;
}
6. 清空链表
只需要把 first 和 last 置空，size 置 0 即可，JDK 源码中还依次置空了 Node，因为迭代器可能引用着其中某个节点，导致其他节点被简介引用，无法被回收
// 清空链表
public void clear() {
first = null;
last = null;
size = 0;
}
双向链表 vs 动态数组
- 动态数组：开辟、销毁内存的次数少，可能造成内存空间浪费
- 双向链表：开辟、销毁内存的次数多，但不会有内存空间浪费
如和选择两种数据结构
- 频繁尾部添加、删除：二者皆可
- 频繁头部添加、删除：双向链表
- 频繁任意位置添加、删除：双向链表
- 频繁查询（随机访问）：动态数组