链表

链表用来存储有序的元素集合，与数组不同，链表中的元素并非保存在连续的存储空间内，每个元素由一个存储元素本身的节点和一个指向下一个元素的指针构成。当要移动或删除元素时，只需要修改相应元素上的指针就可以了。对链表元素的操作要比对数组元素的操作效率更高

5.1 单项链表

下面是单项链表的数据结构展示图：

Image

要表示链表中的元素，我们需要一个助手类，叫作Node。表示我们想要添加到链表中的项，它包含一个element属性，该属性表示要加入链表元素的值，和一个next属性，该属性是指向链表中下一个元素的指针。它的代码如下：

1
2
3
4
5
6
7
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}

然后我们需要创建主类，叫LinkedList类，我们来规划一下这个类可用到的方法以及方法的作用。

**push(element)**： 向链表尾部添加节点

**insert(position, element)**： 在链表的指定位置插入节点

**removeAt(position)**：删除链表中指定位置的元素，并返回这个元素的值

**remove(element)**：删除链表中对应的元素

**indexOf(element)**：在链表中查找给定元素的索引

**getElementAt(position)**：返回链表中索引所对应的元素

**isEmpty()**：判断链表是否为空

**size()**：返回链表的长度

**getHead()**：返回链表的头元素

**clear()**：清空链表

**toString()**：辅助方法，按指定格式输出链表中的所有元素，方便测试验证结果

让我们从查找链表元素的方法**getElementAt()**开始，因为后面我们会多次用到它。

1
2
3
4
5
6
7
8
getElementAt(position) {
    if (position < 0 || position >= this.length) return undefined;
    let current = this.head;
    for (let i = 0; i < position; i++) {
        current = current.next;
    }
    return current;
}

向链表尾部添加元素

向链表尾部添加一个元素时，可能有两种场景：

场景1：链表为空，那添加的就是第一个元素

Image

场景2：链表不为空

Image

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
push(element) {
    let node = new Node(element);
    let current;
    if (this.head === undefined) {
        this.head = node;
    } else {
        current = this.head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = node;
    }
    this.length++;
}

从链表中移除元素
场景一：删除第一个元素，如果要删除的节点为链表的头部，只需要将head移到下一个节点即可。如果当前链表只有一个节点，那么下一个节点为null，此时将head指向下一个节点等同于将head设置成null，删除之后链表为空。
Image
场景二：删除不是第一个元素，如果要删除的节点在链表的中间部分，我们需要找出position所在位置的前一个节点，将它的next指针指向position所在位置的下一个节点。总之，删除节点只需要修改相应节点的指针，使断开位置左右相邻的节点重新连接上。被删除的节点由于再也没有其它部分的引用而被丢弃在内存中，等待垃圾回收器来清除。

Image
实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
     * 删除链表中指定位置的元素，并返回这个元素的值
     * @param position
     */
    removeAt(position) {
        if (position < 0 || position >= this.length) return undefined;
        let current = this.head;
        if (position === 0) {
            this.head = current.next;
        } else {
            let previous = this.getElementAt(position - 1);
            current = previous.next;
            previous.next = current.next;
        }
        this.length--;
        return current.element;
    }

完整的LinkedList类代码如下：

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
class Node {
    constructor(element) {
        this.element = element;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.length = 0;
        this.head = undefined;
    }

    /**
     * 向链表尾部添加节点
     * @param element
     */
    push(element) {
        let node = new Node(element);
        let current;
        if (this.head === undefined) {
            this.head = node;
        } else {
            current = this.head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = node;
        }
        this.length++;
    }

    /**
     * 在链表的指定位置插入节点
     * @param position
     * @param element
     */
    insert(position, element) {
        // position不能超出边界值
        if (position < 0 || position > this.length) return false;
        let node = new Node(element);
        if (position === 0) {
            node.next = this.head;
            this.head = node;
        } else {
            let previous = this.getElementAt(position - 1);
            let current = previous.next;
            node.next = current;
            previous.next = node;
        }
        this.length++;
        return true;
    }

    /**
     * 删除链表中指定位置的元素，并返回这个元素的值
     * @param position
     */
    removeAt(position) {
        if (position < 0 || position >= this.length) return undefined;
        let current = this.head;
        if (position === 0) {
            this.head = current.next;
        } else {
            let previous = this.getElementAt(position - 1);
            current = previous.next;
            previous.next = current.next;
        }
        this.length--;
        return current.element;
    }

    /**
     *  删除链表中对应的元素
     * @param element
     */
    remove(element) {
        let index = this.indexOf(element);
        return this.removeAt(index);
    }

    /**
     * 在链表中查找给定元素的索引
     * @param element
     */
    indexOf(element) {
        let current = this.head;
        for (let i = 0; i < this.length; i++) {
            if (current.element === element) return i;
            current = current.next;
        }
        return -1;
    }

    /**
     * 返回链表中索引所对应的元素
     * @param position
     */
    getElementAt(position) {
        if (position < 0 || position >= this.length) return undefined;
        let current = this.head;
        for (let i = 0; i < position; i++) {
            current = current.next;
        }
        return current;
    }

    /**
     * 判断链表是否为空
     */
    isEmpty() {
        return this.length === 0;
    }

    /**
     * 返回链表的长度
     */
    size() {
        return this.length;
    }

    /**
     * 返回链表的头元素
     */
    getHead() {
        return this.head;
    }

    /**
     * 清空链表
     */
    clear() {
        this.head = null;
        this.length = 0;
    }

    /**
     * 辅助方法，按指定格式输出链表中的所有元素，方便测试验证结果
     */
    toString() {
        let current = this.head;
        let content = '';
        while (current) {
            let next = current.next;
            next = next ? next.element : null;
            content += `{ element: ${current.element}, next: ${next} },`;
            current = current.next;
        }
        if (content) {
            content = content.substring(0, content.length - 1);
        }
        content = `[${content}]`;
        return content;
    }
}

应用LinkedList类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let linkedList = new LinkedList();
linkedList.push('张三');
linkedList.push('李四');
linkedList.push('王五');
linkedList.push('Cat');
linkedList.push('Dog');
console.log(linkedList.toString())
linkedList.removeAt(2);
console.log(linkedList.toString())
linkedList.remove('张三')
console.log(linkedList.toString())
linkedList.insert(2,'阿狗')
console.log(linkedList.toString())
console.log(linkedList.indexOf('阿狗'))

以上效果输出如下：
单项链表输出.png

5.2 双向链表

链表有多种不同的类型，双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。

如图所示：

Image

由于双向链表具有单向链表的所有特性，因此我们的双向链表类可以继承自前面的单向链表类，不过辅助类Node需要添加一个prev属性，用来指向前一个节点。

1
2
3
4
5
6
7
class Node{
    constructor(element) {
        this.element = element;
        this.next = null;
        this.pre = null;
    }
}

下面是继承自LinkedList类的双向链表类的基本骨架：

1
2
3
4
5
6
class DoubleLinkedList extends LinkedList {
    constructor() {
        super();
        this.tail = null;
    }
}

先来看看push()方法的实现。当链表为空时，除了要将head指向当前添加的节点外，还要将tail也指向当前要添加的节点。当链表不为空时，直接将tail的next指向当前要添加的节点node，然后修改node的pre指向旧的tail，最后修改tail为新添加的节点。我们不需要从头开始遍历整个链表，而通过tail可以直接找到链表的尾部，这一点比单向链表的操作要更方便。最后将length的值加1，修改链表的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
push(element) {
    let node = new Node(element);
    // 当链表为空
    if (this.head === null) {
        this.head = node;
        this.tail = node;
    } else {
        //否则将当前节点添加到链表尾部
        this.tail.next = node;
        node.pre = this.tail;
        this.tail = node;
    }
    this.length++;
}

我们同时还需要修改insert()和removeAt()这两个方法。记住，与单向链表唯一的区别就是要同时维护head和tail，以及每一个节点上的next和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
26
27
28
29
30
31
insert(element, index) {
    if (index >= 0 && index <= this.length) {
        let node = new Node(element);
        let current = this.head;
        if (index === 0) {
            if (this.head === null) { // 如果链表为空
                this.head = node;
                this.tail = node;
            } else {
                node.next = this.head;
                current.pre = node;
                this.head = node;
            }
        } else if (index === this.length) {
            current = this.tail;
            current.next = node;
            node.pre = current;
            this.tail = node;
        } else {
            let previous = this.getElementAt(index - 1);
            current = previous.next;
            node.next = current;
            previous.next = node;
            current.pre = node;
            node.pre = previous;
        }
        this.length++;
        return true;
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
removeAt(position) {
    // position不能超出边界值
    if (position < 0 || position >= this.length) return null;
    let current = this.head;
    let previous;
    if (position === 0) { // 移除头部元素
        this.head = current.next;
        this.head.pre = null;
        if (this.length === 1) this.tail = null;
    } else if (position === this.length - 1) { // 移除尾部元素
        current = this.tail;
        this.tail = current.pre;
        this.tail.next = null;
    } else { // 移除中间元素
        current = this.getElementAt(position);
        previous = current.pre;
        previous.next = current.next;
        current.next.pre = previous;
    }
    this.length--;
    return current.element;
}

完整的DoubleLinkedList代码：

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
class DoubleLinkedList extends LinkedList {
    constructor() {
        super();
        this.tail = null;
    }

    push(element) {
        let node = new Node(element);
        // 当链表为空
        if (this.head === null) {
            this.head = node;
            this.tail = node;
        } else {
            //否则将当前节点添加到链表尾部
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        this.length++;
    }

    insert(element, index) {
        if (index >= 0 && index <= this.length) {
            let node = new Node(element);
            let current = this.head;
            if (index === 0) {
                if (this.head === null) { // 如果链表为空
                    this.head = node;
                    this.tail = node;
                } else {
                    node.next = this.head;
                    current.pre = node;
                    this.head = node;
                }
            } else if (index === this.length) {
                current = this.tail;
                current.next = node;
                node.pre = current;
                this.tail = node;
            } else {
                let previous = this.getElementAt(index - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
                current.pre = node;
                node.pre = previous;
            }
            this.length++;
            return true;
        }
        return false
    }

    removeAt(position) {
        // position不能超出边界值
        if (position < 0 || position >= this.length) return null;
        let current = this.head;
        let previous;
        if (position === 0) { // 移除头部元素
            this.head = current.next;
            this.head.pre = null;
            if (this.length === 1) this.tail = null;
        } else if (position === this.length - 1) { // 移除尾部元素
            current = this.tail;
            this.tail = current.pre;
            this.tail.next = null;
        } else { // 移除中间元素
            current = this.getElementAt(position);
            previous = current.pre;
            previous.next = current.next;
            current.next.pre = previous;
        }
        this.length--;
        return current.element;
    }

    getTail() {
        return this.tail;
    }

    toString() {
        let current = this.head;
        let s = '';

        while (current) {
            let next = current.next;
            let previous = current.prev;
            next = next ? next.element : 'null';
            previous = previous ? previous.element : 'null';
            s += `[element: ${current.element}, prev: ${previous}, next: ${next}] `;
            current = current.next;
        }

        return s;
    }
}

我们写测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.push(1);
doubleLinkedList.push(3);
doubleLinkedList.push(5);
doubleLinkedList.push(7);
doubleLinkedList.push(9);

console.log(doubleLinkedList.toString())
console.log(doubleLinkedList.size())
console.log(doubleLinkedList.getElementAt(1).element);
console.log(doubleLinkedList.getElementAt(2).element);
console.log(doubleLinkedList.getElementAt(3).element);

doubleLinkedList.insert('Jack',1)
console.log(doubleLinkedList.toString())
doubleLinkedList.removeAt(1)
console.log(doubleLinkedList.toString())

运行结果如下：

双向链表运行结果.png

5.3 循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针(tail.next)不是引用undefined而是指向第一个元素(head)

结构示意图如下：
Image

双向循环链表有指向head元素的tail.next和指向tail元素的head.pre
Image

我们来看创建CircularLinkedList类的代码。

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
class CircularLinkedList extends LinkedList {
    constructor() {
        super();

    }

    push(element) {

        let node = new Node(element);
        if (this.head === undefined) {
            this.head = node;
        } else {
            let current = this.getElementAt(this.length - 1);
            current.next = node;
        }
        node.next = this.head;
        this.length++;
    }

    insert(position, element) {
        if (position < 0 || position >= this.length) return false;
        let node = new Node(element);
        if (position === 0) {
            node.next = this.head;
            let current = this.getElementAt(this.length - 1);
            current.next = node;
            this.head = node;
        } else {
            let previous = this.getElementAt(position - 1);
            node.next = previous.next;
            previous.next = node;
        }
        this.length++;
        return true;
    }

    removeAt(position) {
        if (position < 0 || position >= this.length) return false;
        let current = this.head;
        if (position === 0) {
            this.head = current.next;
        } else {
            let previous = this.getElementAt(position - 1);
            current = previous.next;
            previous.next = current.next;
        }
        this.length--;
        if (this.length > 1) {
            let last = this.getElementAt(this.length - 1);
            last.next = this.head;
        }
        return current.element;
    }

    toString() {
        let current = this.head;
        let s = '';

        for (let i = 0; i < this.length; i++) {
            let next = current.next;
            next = next ? next.element : 'null';
            s += `[element: ${current.element}, next: ${next}] `;
            current = current.next;
        }

        return s;
    }
}

我们来写几个CircularLinkedList测试用例：

1
2
3
4
5
6
7
8
9
10
11
let circularLinkedList = new CircularLinkedList();
circularLinkedList.push(1);
circularLinkedList.push(3);
console.log(circularLinkedList.toString());

circularLinkedList.insert(0, 7);
circularLinkedList.insert(3, 9);
console.log(circularLinkedList.toString());

console.log(circularLinkedList.removeAt(0));
console.log(circularLinkedList.toString());

运行结果如下：

循环链表测试用例.png