数据结构与算法之双向链表的设计与实现

前言

文章链接之前所介绍的是单向链表，查找元素只能从头节点开始寻找，判断出符合条件的元素，时间复杂度为O(n)。当链表节点数目过多时，查询性能下降。而有了双向链表后，我们可以从两个方向查询元素，提升查询效率。

一、双向链表

1.1 概念

双向链表是一种数据结构，由若干个节点构成，其中每个节点均由三部分构成，分别是前驱节点，元素，后继节点。双向链表中的节点在内存中是游离状态存在的，如下图所示：

1.2 双向链表的应用

1.1 Java集合框架中LinkedList底层就是通过双向链表实现的，我们可以通过查看，阅读源码进行分析。
1.2 MySQL的Innodb存储引擎管理的数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个 单向链表。如下图所示：

1.3 双向链表的node方法

查询方式:对半查找，若查找的位置小于链表长度的一半，则从头结点开始顺序查找；否则，从尾结点开始逆序查找，这样做可以提高查询效率。

//根据索引找到节点(查找目标节点位置小于链表长度的一半就从前往后找,大于的话从后往前找话)
private Node<E> node(int index) {
    rangeCheck(index);
    Node<E> node;
    if (index < (size >> 1)){
        node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
    }else {
        node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
    }
    return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.4 双向链表的add方法

之前单项链表新增节点操纵需要获取到 index 前面的节点，现在双向链表不需要，可以通过 prev 获取到前驱节点，next 获取到后继节点。

add(E) -- 在链表尾部添加元素，将元素封装到节点中，创建新节点，让新节点和前一个节点建立双向链表的关系。
add(int index，E e) -- 在指定位置插入元素，其过程实际上就是断开链，重新构建链的过程。
1
2

双向链表只有一个节点的时候，如下图所示：

@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);
    //一开始index == 0 size() == 0 则 old.next == null
    if (size == index){//往最后面添加元素
        //获取到最后一个节点
        Node<E> old = last;
        //创建新的尾节点,last指向新的尾节点
        last = new Node<>(last, element, null);
        if (old == null){
            first = last;
        }else {
            //之前的尾节点的next指向新的尾节点
            old.next = last;
        }
    }else {
        //获取指定index的节点
        Node<E> next = node(index);
        //获取指定index的节点前一个节点
        Node<E> prev = next.prev;
        //创建新节点并指定他的prev和next
        Node<E> node = new Node<>(prev, element, next);
        next.prev = node;
        if (prev == null){
            first = node;
        }else{
            prev.next = node;
        }
    }
    size++;
}
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

1.5 双向链表的remove方法

remove(int index) – 删除指定位置的元素，其过程实际上依然是断开链，重新构建链的过程。

@Override
public E remove(int index) {
    rangeCheck(index);
    //获取index位置的节点
    Node<E> node = node(index);
    //获取index位置的上一个节点
    Node<E> prev = node.prev;
    //获取index位置的下一个节点
    Node<E> next = node.next;
    //prev == null 则说明删除的是第一个节点 0位置节点
    if (prev == null){
        first = next;
    }else {
        prev.next = next;
    }
     //next == null 则说明删除的是最后一个节点 size()位置节点
    if (next == null){
        last = prev;
    }else{
        next.prev = prev;
    }
    size--;
    return node.element;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.6 整体代码

package com.hbx.linkedList.bidirection;

import com.hbx.module.AbstractList;

public class LinkedList<E> extends AbstractList<E> {

    private Node<E> first;
    private Node<E> last;

    // 链表中的节点
    private static class Node<E> {
        E element; // 节点元素
        Node<E> prev; // 节点指向下一个节点
        Node<E> next; // 节点指向下一个节点

        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder();
            if(prev != null){
                sb.append(prev.element);
            }else{
                sb.append("null");
            }
            sb.append("_").append(element).append("_");
            if(next != null){
                sb.append(next.element);
            }else{
                sb.append("null");
            }

            return sb.toString();
        }
    }

    @Override
    public void clear() {
        size = 0;
        //jvm的gcRoots(可达性分析)
        first = null;
        last = null;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }
    /**
     * 根据索引找到节点
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        if (index < (size >> 1)) { // 索引小于一半从前往后找
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else { // 索引大于一半从后往前找
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    @Override
    public E set(int index, E element) {
        /*
         * 最好:O(1)
         * 最坏:O(n)
         * 平均:O(n)
         */
        E old = node(index).element;
        node(index).element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        //一开始index == 0 size() == 0 old.next == null
        if (size == index){//往最后面添加元素
            Node<E> old = last;
            last = new Node<>(old, element, null);
            if (old == null){
                first = last;
            }else {
                old.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){
                first = node;
            }else{
                prev.next = node;
            }
        }
        size++;
    }

    @Override
    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){
            first = next;
        }else {
            prev.next = next;
        }
        if (next == null){
            last = prev;
        }else{
            next.prev = prev;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        // 有个注意点, 如果传入元素为null, 则不能调用equals方法, 否则会空指针
        // 因此需要对元素是否为null做分别处理
        Node<E> node = first;
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (node.element == null)
                    return i;
                node = node.next;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (node.element.equals(element))
                    return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("[size=").append(size).append(", ");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                string.append(", ");
            }
            string.append(node);
            node = node.next;
        }
        string.append("]");
        return string.toString();
    }

}
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

1.7 接口测试

@Test
public void test(){
    List<Integer> list = new LinkedList<>();
    list.add(11);
    list.add(22);
    list.add(33);
    list.add(44);
    list.add(0,55);//55, 11,22, 33, 44
    list.add(2,66);//55, 11, 66, 22, 33, 44
    list.add(list.size(),77);//55, 11, 66, 22, 33, 44, 77

    list.remove(0);
    list.remove(2);
    list.remove(list.size()-1);
    System.out.println(list);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、对比学习

2.1 单向链表 vs 双向链表

粗略对比一下删除的操作数量：操作数量缩减了近一半

2.2 双向链表 vs 动态数组

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

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

2.3 ArrayList和LinkedList的区别

1. ArrayList底层是数组实现的，LinkedList底层是双向链表，二者的数据结构是不同的。
2. 因为数据结构不同，所以最终的性能是不同的；
   查询元素:
   ArrayList是根据下标查找元素,查询效率非常高,时间复杂度为O(1)。
   LinkedList中若查找头部/尾部的元素,其查询效率还是比较高的,但是若查找偏中间位置的元素,其查询效率是比较低下的。
   增删元素:
   ArrayList：若在尾部添加增删元素，此时性能可能会很高，在头部和中间位置进行增删操作，其效率都不是很高。
   LinkedList：若在头尾部分增删元素，此时性能很高，但是若在偏中间位置进行增删元素，此时性能不高的(因为增删，会先查询指定位置的节点，查询效率是低下的)。
   整体而言:
   ArrayList查询性能是高于LinkedList的，但是若LinkedList进行头尾查询，此时效率也是非常高的。
   若进行的是偏头部和尾部的增删操作，选择LinkedList，而若对其他位置进行增删，此时ArrayList和LinkedList的效率是差不多的。
   ArrayList查询方面性能更好，增删方面，除了头尾增删，其他增删和LinkedList差不多，所以经常使用ArrayList。
   面试标准回答：
   ArrayList查询性能更高，LinkedList进行头尾增删，性能很高，除此之外，其他增删，ArrayList和LinkedList差不多。