【数据结构与算法】系列四 - 双向链表

发表于 | 分类于 ， ，
| 字数统计 1.8k 字 | 阅读时长 7 分钟

单向链表的特点是每一个元素只有一个next指向下一个元素，直到最后一个元素指向null。每次查找元素都只能从头节点开始，并且是一条线往下找，效率相对比较低。

一、双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

1.1. 添加元素

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
public void add(int index, E element) {
    rangeCheckForAdd(index);

    if (index == size) { // 往最后面添加元素
      Node<E> oldLast = last;
      last = new Node<>(oldLast, element, null);
      if (oldLast == null) { // 这是链表添加的第一个元素
        first = last;
      } else {
        oldLast.next = last;
      }
    } else {
      Node<E> next = node(index); 
      Node<E> prev = next.prev; 
      Node<E> node = new Node<>(prev, element, next);
      next.prev = node;
      
      if (prev == null) { // index == 0
        first = node;
      } else {
        prev.next = node;
      }
    }
    
    size++;
}

只有一个元素时，元素的prev和next都指向null。

1.2. 删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public E remove(int index) {
    rangeCheck(index);

    Node<E> node = node(index);
    Node<E> prev = node.prev;
    Node<E> next = node.next;
    
    if (prev == null) { // index == 0
      first = next;
    } else {
      prev.next = next;
    }
    
    if (next == null) { // index == size - 1
      last = prev;
    } else {
      next.prev = prev;
    }
    
    size--;
    return node.element;
}

1.3. 双向链表和单向链表

粗略对比一下删除的操作数量：

操作数量缩减了近一半。

有了双向链表，单向链表是否就没有任何用处了？并非如此，在哈希表的设计中就用到了单链表。

1.4. 双向链表和动态数组

动态数组： 开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容解决）。

双向链表： 开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费。

  • 如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
  • 如果频繁在头部进行添加、删除操作，建议选择使用双向链表
  • 如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表
  • 如果有频繁的查询操作（随机访问操作），建议选择使用动态数组

二、单向循环链表

单向循环链表是在单向链表的基础上，尾节点的next指向了头节点。

2.1. 添加元素

考虑特殊情况：只有一个节点时，next指向自己：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void add(int index, E element) {
    rangeCheckForAdd(index);
    
    if (index == 0) {
      Node<E> newFirst = new Node<>(element, first);
      // 拿到最后一个节点
      Node<E> last = (size == 0) ? newFirst : node(size - 1);
      last.next = newFirst;
      first = newFirst;
    } else {
      Node<E> prev = node(index - 1);
      prev.next = new Node<>(element, prev.next);
    }
    size++;
}

2.2. 删除元素

一定要考虑只有一个节点的情况，否则无法删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public E remove(int index) {
    rangeCheck(index);
    
    Node<E> node = first;
    if (index == 0) {
      if (size == 1) { // 一定要考虑只有一个节点的情况，否则无法删除
        first = null;
      } else {
        // 下面的代码顺序不能改变
        Node<E> last = node(size - 1);
        first = first.next;
        last.next = first;
      }
    } else {
      Node<E> prev = node(index - 1);
      node = prev.next;
      prev.next = node.next;
    }
    size--;
    return node.element;
}

三、双向循环链表

双向循环链表是在双向链表的基础上，尾节点的next指向头节点，头节点的prev指向尾节点。

3.1. 添加元素

考虑特殊情况：只有一个节点时，prev和next都指向自己：

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
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // size == 0
    // index == 0
    if (index == size) { // 往最后面添加元素
      Node<E> oldLast = last;
      last = new Node<>(oldLast, element, first);
      if (oldLast == null) { // 这是链表添加的第一个元素
        first = last;
        first.next = first;
        first.prev = first;
      } else {
        oldLast.next = last;
        first.prev = last;
      }
    } else {
      Node<E> next = node(index); 
      Node<E> prev = next.prev; 
      Node<E> node = new Node<>(prev, element, next);
      next.prev = node;
      prev.next = node;
      
      if (next == first) { // index == 0
        first = node;
      }
    }
    
    size++;
}

3.2. 删除元素

一定要考虑只有一个节点的情况，否则无法删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private E remove(Node<E> node) {
    if (size == 1) {
      first = null;
      last = null;
    } else {
      Node<E> prev = node.prev;
      Node<E> next = node.next;
      prev.next = next;
      next.prev = prev;
      
      if (node == first) { // index == 0
        first = next;
      }
      
      if (node == last) { // index == size - 1
        last = prev;
      }
    }
    
    size--;
    return node.element;
}

四、静态链表

前面所介绍的链表，是依赖于指针（引用）实现的。有些编程语言是没有指针的，比如早期的BASIC、FORTRAN语言。

没有指针的情况下，如何实现链表？可以通过数组来模拟链表，称为静态链表。数组的每个元素存放2个数据：值和下个元素的索引。数组0位置存放的是头结点信息，索引-1代表尾节点，也可以用0表示指向头结点，形成循环。

思考：如果数组的每个元素只能存放1个数据呢？那就使用2个数组，1个数组存放索引关系，1个数组存放值。

五、约瑟夫问题

约瑟夫问题（有时也称为约瑟夫斯置换，是一个计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）。

例如：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=8，M=3，被杀掉的顺序是：3，6，1，5，2，8，4。

分析：
（1）由于对于每个人只有死和活两种状态，因此可以用布尔型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。

可以考虑增设1个成员变量、3个方法：

  • current ：用于指向某个节点
  • void reset() ：让current指向头结点first
  • E next() ：让current往后走一步，也就是current = current.next
  • E remove() ：删除current指向的节点，删除成功后让current指向下一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void reset() {
    current = first;
  }

  public E next() {
    if (current == null) return null;
    
    current = current.next;
    return current.element;
  }

  public E remove() {
    if (current == null) return null;
    
    Node<E> next = current.next; 
    E element = remove(current);
    if (size == 0) {
      current = null;
    } else {
      current = next;
    }
    
    return element;
}

使用双向循环链表封装操作并使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CircleLinkedList<Integer> list = new CircleLinkedList<>();
// 添加8个元素
for (int i = 1; i <= 8; i++) {
    list.add(i);
}
// 指向头结点（指向1）
list.reset();
// 循环
while (!list.isEmpty()) {
    // 移动两步
    list.next();
    list.next();
    // 移除元素
    list.remove();
}