Fork me on GitHub

JavaScript数据结构04 - 链表

stack

一、定义

1.1 概念

前面我们学习了数组这种数据结构。数组(或者也可以称为列表)是一种非常简单的存储数据序列的数据结构。在这一节,我们要学习如何实现和使用链表这种动态的数据结构,这意味着我们可以从中任意添加或移除项,它会按需进行扩容。

要存储多个元素,数组(或列表)可能是最常用的数据结构,它提供了一个便利的[]语法来访问它的元素。然而,这种数据结构有一个缺点:(在大多数强类型语言中)数组的大小是固定的,需要预先分配,从数组的起点或中间插入或移除项的成本很高,因为需要移动元素。
(注意:在JavaScript中数组的大小随时可变,不需要预先定义长度)

链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

相对于传统的数组,链表的一个好处在于,添加或删除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的元素,而想要访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。

火车可以当做生活中一个典型的链表的例子。一列火车是由一系列车厢组成的。每节车厢都相互连接。你很容易分离一节车厢,改变它的位置,添加或移除它。

1.2 分类

链表最常用的有三类

  1. 单向链表
  2. 双向链表
  3. 循环链表

二、链表的实现

2.1 单向链表

创建单向链表类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// SinglyLinkedList
function SinglyLinkedList () {
function Node (element) {
this.element = element;
this.next = null;
}

var length = 0;
var head = null;

this.append = function (element) {};
this.insert = function (position, element) {};
this.removeAt = function (position) {};
this.remove = function (element) {};
this.indexOf = function (element) {};
this.isEmpty = function () {};
this.size = function () {};
this.getHead = function () {};
this.toString = function () {};
this.print = function () {};
}

SinglyLinkedList需要一个辅助类Node。Node类表示要加入链表的项。它包含一个element属性,即要添加到链表的值,以及一个next属性,即指向链表中下一个节点项的指针。

链表里面有一些声明的辅助方法:

  • append(element):向链表尾部添加新项
  • insert(position, element):向链表的特定位置插入一个新的项
  • removeAt(position):从链表的特定位置移除一项
  • remove(element):从链表中移除一项
  • indexOf(element):返回元素在链表中的索引。如果链表中没有该元素则返回-1
  • isEmpty():如果链表中不包含任何元素,返回true,如果链表长度大于0,返回false
  • size():返回链表包含的元素个数,与数组的length属性类似
  • getHead():返回链表的第一个元素
  • toString():由于链表使用了Node类,就需要重写继承自JavaScript对象默认的toString()方法,让其只输出元素的值
  • print():打印链表的所有元素

下面我们来一一实现这些辅助方法:

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
// 向链表尾部添加一个新的项
this.append = function (element) {
var node = new Node(element);
var currentNode = head;

// 判断是否为空链表
if (currentNode === null) {
// 空链表
head = node;
} else {
// 从head开始一直找到最后一个node
while (currentNode.next) {
// 后面还有node
currentNode = currentNode.next;
}
currentNode.next = node;
}

length++;
};

// 向链表特定位置插入一个新的项
this.insert = function (position, element) {
if (position < 0 && position > length) {
// 越界
return false;
} else {
var node = new Node(element);
var index = 0;
var currentNode = head;
var previousNode;

if (position === 0) {
node.next = currentNode;
head = node;
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}

previousNode.next = node;
node.next = currentNode;
}

length++;

return true;
}
};

// 从链表的特定位置移除一项
this.removeAt = function (position) {
if (position < 0 && position >= length || length === 0) {
// 越界
return false;
} else {
var currentNode = head;
var index = 0;
var previousNode;

if (position === 0) {
head = currentNode.next;
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}

length--;

return true;
}
};

// 从链表的特定位置移除一项
this.removeAt = function (position) {
if (position < 0 && position >= length || length === 0) {
// 越界
return false;
} else {
var currentNode = head;
var index = 0;
var previousNode;

if (position === 0) {
head = currentNode.next;
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}

length--;

return true;
}
};

// 从链表中移除指定项
this.remove = function (element) {
var index = this.indexOf(element);
return this.removeAt(index);
};

// 返回元素在链表的索引,如果链表中没有该元素则返回-1
this.indexOf = function (element) {
var currentNode = head;
var index = 0;

while (currentNode) {
if (currentNode.element === element) {
return index;
}

index++;
currentNode = currentNode.next;
}

return -1;
};

// 如果链表中不包含任何元素,返回true,如果链表长度大于0,返回false
this.isEmpty = function () {
return length == 0;
};

// 返回链表包含的元素个数,与数组的length属性类似
this.size = function () {
return length;
};

// 获取链表头部元素
this.getHead = function () {
return head.element;
};

// 由于链表使用了Node类,就需要重写继承自JavaScript对象默认的toString()方法,让其只输出元素的值
this.toString = function () {
var currentNode = head;
var string = '';

while (currentNode) {
string += ',' + currentNode.element;
currentNode = currentNode.next;
}

return string.slice(1);
};

this.print = function () {
console.log(this.toString());
};

创建单向链表实例进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 创建单向链表实例
var singlyLinked = new SinglyLinkedList();
console.log(singlyLinked.removeAt(0)); // true
console.log(singlyLinked.isEmpty()); // true
singlyLinked.append('Tom');
singlyLinked.append('Peter');
singlyLinked.append('Paul');
singlyLinked.print(); // "Tom,Peter,Paul"
singlyLinked.insert(0, 'Susan');
singlyLinked.print(); // "Susan,Tom,Peter,Paul"
singlyLinked.insert(1, 'Jack');
singlyLinked.print(); // "Susan,Jack,Tom,Peter,Paul"
console.log(singlyLinked.getHead()); // "Susan"
console.log(singlyLinked.isEmpty()); // false
console.log(singlyLinked.indexOf('Peter')); // 3
console.log(singlyLinked.indexOf('Cris')); // -1
singlyLinked.remove('Tom');
singlyLinked.removeAt(2);
singlyLinked.print(); // "Susan,Jack,Paul"

2.2 双向链表

双向链表和普通链表的区别在于,在普通链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素。

创建双向链表类:

1
2
3
4
5
6
7
8
9
10
11
12
// 创建双向链表DoublyLinkedList类
function DoublyLinkedList () {
function Node (element) {
this.element = element;
this.next = null;
this.prev = null; // 新增
}

var length = 0;
var head = null;
var tail = null; // 新增
}

可以看到,双向链表在Node类里有prev属性(一个新指针),在DoublyLinkedList类里也有用来保存对列表最后一项的引用的tail属性。

双向链表提供了两种迭代列表的方法:从头到尾,或者从尾到头。我们可以访问一个特定节点的下一个或前一个元素。

在单向链表中,如果迭代链表时错过了要找的元素,就需要回到链表起点,重新开始迭代。在双向链表中,可以从任一节点,向前或向后迭代,这是双向链表的一个优点。

实现双向链表的辅助方法:

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
// 向链表尾部添加一个新的项
this.append = function (element) {
var node = new Node(element);
var currentNode = tail;

// 判断是否为空链表
if (currentNode === null) {
// 空链表
head = node;
tail = node;
} else {
currentNode.next = node;
node.prev = currentNode;
tail = node;
}

length++;
};

// 向链表特定位置插入一个新的项
this.insert = function (position, element) {
if (position < 0 && position > length) {
// 越界
return false;
} else {
var node = new Node(element);
var index = 0;
var currentNode = head;
var previousNode;

if (position === 0) {
if (!head) {
head = node;
tail = node;
} else {
node.next = currentNode;
currentNode.prev = node;
head = node;
}
} else if (position === length) {
this.append(element);
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}

previousNode.next = node;
node.next = currentNode;

node.prev = previousNode;
currentNode.prev = node;
}

length++;

return true;
}
};

// 从链表的特定位置移除一项
this.removeAt = function (position) {
if (position < 0 && position >= length || length === 0) {
// 越界
return false;
} else {
var currentNode = head;
var index = 0;
var previousNode;

if (position === 0) {
// 移除第一项
if (length === 1) {
head = null;
tail = null;
} else {
head = currentNode.next;
head.prev = null;
}
} else if (position === length - 1) {
// 移除最后一项
if (length === 1) {
head = null;
tail = null;
} else {
currentNode = tail;
tail = currentNode.prev;
tail.next = null;
}
} else {
while (index < position) {
index++;
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
previousNode = currentNode.next.prev;
}

length--;

return true;
}
};

// 从链表中移除指定项
this.remove = function (element) {
var index = this.indexOf(element);
return this.removeAt(index);
};

// 返回元素在链表的索引,如果链表中没有该元素则返回-1
this.indexOf = function (element) {
var currentNode = head;
var index = 0;

while (currentNode) {
if (currentNode.element === element) {
return index;
}

index++;
currentNode = currentNode.next;
}

return -1;
};

// 如果链表中不包含任何元素,返回true,如果链表长度大于0,返回false
this.isEmpty = function () {
return length == 0;
};

// 返回链表包含的元素个数,与数组的length属性类似
this.size = function () {
return length;
};

// 获取链表头部元素
this.getHead = function () {
return head.element;
};

// 由于链表使用了Node类,就需要重写继承自JavaScript对象默认的toString()方法,让其只输出元素的值
this.toString = function () {
var currentNode = head;
var string = '';

while (currentNode) {

string += ',' + currentNode.element;
currentNode = currentNode.next;
}

return string.slice(1);
};

this.print = function () {
console.log(this.toString());
};

创建双向链表实例进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 创建双向链表
var doublyLinked = new DoublyLinkedList();
console.log(doublyLinked.isEmpty()); // true
doublyLinked.append('Tom');
doublyLinked.append('Peter');
doublyLinked.append('Paul');
doublyLinked.print(); // "Tom,Peter,Paul"
doublyLinked.insert(0, 'Susan');
doublyLinked.print(); // "Susan,Tom,Peter,Paul"
doublyLinked.insert(1, 'Jack');
doublyLinked.print(); // "Susan,Jack,Tom,Peter,Paul"
console.log(doublyLinked.getHead()); // "Susan"
console.log(doublyLinked.isEmpty()); // false
console.log(doublyLinked.indexOf('Peter')); // 3
console.log(doublyLinked.indexOf('Cris')); // -1
doublyLinked.remove('Tom');
doublyLinked.removeAt(2);
doublyLinked.print(); // "Susan,Jack,Paul"

2.3 循环链表

循环链表可以像单向链表一样只有单向引用,也可以像双向链表一样有双向引用。循环链表和普通链表之间唯一的区别在于,最后一个元素指向下一个元素的指针(next)不是引用null,而是指向第一个元素(head)。这里就不进行代码实现了,大家可以结合上面的单向链表和双向链表自己实现一个循环链表。

三、结束

本文会同步到我的个人博客,完整代码可以到我的github仓库查看,如果对你有帮助的话欢迎点一个Star~~