双向链表

  • 之前的单向链表只能通过 Node 中 next 属性从头遍历链表,完成搜索
  • 双向链表中的 Node 增加 prev 属性,指向该节点上一个节点
  • 双向链表查找元素可以从 first 或 last 两个方向开始查找,故而可以提高效率
  • Java 官方 LinkedList 就是双向链表

双向链表

实现双向链表

相比单向链表,双向链表需要重写查找节点、添加节点、删除节点、清空链表四个方法

1. 属性

增加 last 指向尾节点,Node 中增加 prev 指向前一个节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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. 构造器

1
2
3
4
5
6
// 构造器
LinkedList() {
    first = null;
    last = null;
    size = 0;
}

3. 查找节点

判断要查找的位置是在链表前半段还是后半段,选择从前向后还是从后向前查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 查找节点
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. 添加元素

  • 向链表尾部追加元素
    • 空链表
    • 非空链表
  • 非尾部插入元素
    • 插入到第一个位置
    • 其他位置
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 添加元素
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) 需要特殊处理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 删除元素
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,因为迭代器可能引用着其中某个节点,导致其他节点被简介引用,无法被回收

1
2
3
4
5
6
// 清空链表
public void clear() {
    first = null;
    last = null;
    size = 0;
}

双向链表 vs 动态数组

  • 动态数组:开辟、销毁内存的次数少,可能造成内存空间浪费
  • 双向链表:开辟、销毁内存的次数多,但不会有内存空间浪费

如和选择两种数据结构

  • 频繁尾部添加、删除:二者皆可
  • 频繁头部添加、删除:双向链表
  • 频繁任意位置添加、删除:双向链表
  • 频繁查询(随机访问):动态数组

参考