数据结构 双向链表LinkedList

双向链表

  • 之前的单向链表只能通过 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 动态数组

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

如和选择两种数据结构

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

参考