【JavaScript算法与数据结构】4.链表

《学习JavaScript数据结构与算法》第5章-链表。

四、链表

链表中的元素在内存中并不是连续放置的

添加或移除元素:不需要移动其他元素

访问元素:从起点(表头)开始迭代

1. 创建LinkedList

a.链表元素

1
2
3
4
function Node(element){
this.element = element; // 值
this.next = null; // 指针
};

b.链表

用到的指针:head,current,previous

用到的变量:length,index

对指定位置(position)的处理:要检查是否越界

插入/删除:分别考虑第一个/中间/最后一个3种情况;修改length,index

append(element):在尾部添加新元素

head,current;length,index

  1. 空链表
  2. 非空链表

removeAt(position):移除指定位置的元素

head,current,previous;length,index

  1. 移除第一个元素
  2. 移除最后一个元素
  3. 移除中间元素

insert(position, element):特定位置添加新元素

head,current,previous;length,index

  1. 移除第一个元素
  2. 移除最后一个元素
  3. 移除中间元素

remove(element):移除指定元素

indexOf(element):返回指定元素的索引,若不存在返回-1

isEmpty():是否为空链表

size():链表长度

getHead():链表头(第一个元素)

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
function LinkedList() {
let Node = function(element){
this.element = element; // 值
this.next = null; // 指针
};
let length = 0; // 链表长度
let head = null; // 存储第一个节点的引用
// 在尾部添加新元素
this.append = function(element){
let node = new Node(element),
current;
if (head === null){ //first node on list
head = node;
} else {
current = head;
//loop the list until find last item
while(current.next){
current = current.next;
}
//get last item and assign next to added item to make the link
current.next = node;
}
length++; //update size of list
};
// 特定位置添加新元素
this.insert = function(position, element){
//check for out-of-bounds values
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //add on first position
node.next = current;
head = node;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++; //update size of list
return true;
} else {
return false;
}
};
// 移除指定位置的元素
this.removeAt = function(position){
//check for out-of-bounds values
if (position > -1 && position < length){
let current = head,
previous,
index = 0;
//removing first item
if (position === 0){
head = current.next;
} else {
while (index++ < position){
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
// 移除指定元素
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
// 返回指定元素的索引,若不存在返回-1
this.indexOf = function(element){
let current = head,
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
// 是否为空链表
this.isEmpty = function() {
return length === 0;
};
// 链表长度
this.size = function() {
return length;
};
// 返回链表头(第一个元素)
this.getHead = function(){
return head;
};
// 链表转为字符串形式(只输出元素的值)
this.toString = function(){
let current = head,
string = '';
while (current) {
string += current.element + (current.next ? ', ' : '');
current = current.next;
}
return string;
};
// 打印链表
this.print = function(){
console.log(this.toString());
};
}

2. 双向链表

双向链表提供了两种迭代列表的方法:从头到尾,从尾到头

a. 变动

1
2
3
4
5
6
7
8
9
10
11
function DoublyLinkedList() {
var Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //新增的
};
var length = 0;
var head = null;
var tail = null; //新增的
//这里是方法
}

b. 方法


用到的指针:head,tail,current,previous

用到的变量:length,index

对指定位置(position)的处理:要检查是否越界

插入/删除:分别考虑第一个/中间/最后一个3种情况;修改index

append(element):在尾部添加新元素

head,tail,current;length,index

  1. 空链表
  2. 非空链表

removeAt(position):移除指定位置的元素

head,tail,current,previous;length,index

  1. 移除第一个元素
  2. 移除最后一个元素
  3. 移除中间元素

insert(position, element):特定位置添加新元素

head,tail,current,previous;length,index

  1. 移除第一个元素
  2. 移除最后一个元素
  3. 移除中间元素

remove(element):移除指定元素

indexOf(element):返回指定元素的索引,若不存在返回-1

isEmpty():是否为空链表

size():链表长度

getHead():链表头(第一个元素)

getTail():链表尾(最后一个元素)

toString():链表顺序转为字符串形式(只输出元素的值)

inverseToString():链表逆序转为字符串形式(只输出元素的值)

printInverse():逆序打印链表

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
function DoublyLinkedList() {
let Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //NEW
};
let length = 0;
let head = null;
let tail = null; //NEW
// 在尾部添加新元素
this.append = function(element){
let node = new Node(element),
current;
if (head === null){ //first node on list
head = node;
tail = node; //NEW
} else {
//attach to the tail node //NEW
tail.next = node;
node.prev = tail;
tail = node;
}
length++; //update size of list
};
// 特定位置添加新元素
this.insert = function(position, element){
//check for out-of-bounds values
if (position >= 0 && position <= length){
let node = new Node(element),
current = head,
previous,
index = 0;
if (position === 0){ //add on first position
if (!head){ //NEW
head = node;
tail = node;
} else {
node.next = current;
current.prev = node; //NEW {1}
head = node;
}
} else if (position === length) { //last item //NEW
current = tail; // {2}
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position){ //{3}
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
current.prev = node; //NEW
node.prev = previous; //NEW
}
length++; //update size of list
return true;
} else {
return false;
}
};
// 移除指定位置的元素
this.removeAt = function(position){
//check for out-of-bounds values
if (position > -1 && position < length){
let current = head,
previous,
index = 0;
//removing first item
if (position === 0){
head = current.next; // {1}
//if there is only one item, then we update tail as well //NEW
if (length === 1){ // {2}
tail = null;
} else {
head.prev = null; // {3}
}
} else if (position === length-1){ //last item //NEW
current = tail; // {4}
tail = current.prev;
tail.next = null;
} else {
while (index++ < position){ // {5}
previous = current;
current = current.next;
}
//link previous with current's next - skip it to remove
previous.next = current.next; // {6}
current.next.prev = previous; //NEW
}
length--;
return current.element;
} else {
return null;
}
};
// 移除指定元素
this.remove = function(element){
let index = this.indexOf(element);
return this.removeAt(index);
};
// 返回指定元素的索引,若不存在返回-1
this.indexOf = function(element){
let current = head,
index = -1;
//check first item
if (element == current.element){
return 0;
}
index++;
//check in the middle of the list
while(current.next){
if (element == current.element){
return index;
}
current = current.next;
index++;
}
//check last item
if (element == current.element){
return index;
}
return -1;
};
// 是否为空链表
this.isEmpty = function() {
return length === 0;
};
// 链表长度
this. size = function() {
return length;
};
// 链表顺序转为字符串形式(只输出元素的值)
this.toString = function(){
let current = head,
s = current ? current.element : '';
while(current && current.next){
current = current.next;
s += ', ' + current.element;
}
return s;
};
// 链表逆序转为字符串形式(只输出元素的值)
this.inverseToString = function() {
let current = tail,
s = current ? current.element : '';
while(current && current.prev){
current = current.prev;
s += ', ' + current.element;
}
return s;
};
// 顺序打印链表
this.print = function(){
console.log(this.toString());
};
// 逆序打印链表
this.printInverse = function(){
console.log(this.inverseToString());
};
// 返回链表头(第一个元素)
this.getHead = function(){
return head;
};
// 返回链表尾(最后一个元素)
this.getTail = function(){
return tail;
}
}

3. 循环链表

a. 单向循环链表

head

b. 双向循环链表

head,tail

您的支持将鼓励我继续创作!
------本文结束感谢阅读------