前言

❤️笔芯❤️~

链表

链表数据结构,向链表添加元素,从链表移除元素,使用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
function LinkedList() {
let Node = function(element) {
// LinkedList数据结构还需要一个Node辅助类
this.element = element;
this.next = null;
};

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

let length = 0;
// LinkedList类也有存储列表项的数量的length属性
let head = null;
// 需要存储第一个节点的引用,这个引用存储在一个为head的变量中

// append(element),向列表尾部添加一个新的项
this.append = function(element){};

// insert(position,element),向列表的特定位置插入一个新的项
this.insert = function(position, element){};

// removeAt(position),从列表的特定位置移除一项
this.removeAt = function(position){};

// remove(element),从列表中移除一项
this.remove = function(element){};

// indexOf(element),返回元素在列表中的索引,如果列表中没有该元素则返回-1
this.indexOf = function(element){};

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

// 返回链表包含的元素个数
this.size = function(){};
this.getHead = function(){};

// 由于列表项使用了Node类,就需要重写继承来自JavaScript对象默认的toString方法,让其只输出元素的值
this.toString = function(){};
this.print = function(){};
}

向链表尾部追加元素

场景:

  1. 列表为空,添加第一个元素
  2. 列表不为空,向其追加元素
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
this.append = function(element){
// 需要把element作为值传入,创建Node项
let node = new Node(element),
//
current;

if(head === null) {
// 列表中第一个节点
// 在向列表添加第一个元素
// 下一个node元素将会自动成为null
head = node;
}else{
// 要向列表的尾部添加一个元素,首先需要找到最后一个元素
current = head;

// 循环列表,直到找到最后一项
while(current.next){
// 需要一个指向列表中current项的变量
current = current.next
}
// 找到最后一项,将其next赋为node,建立链接
current.next = node
}
length++; // 更新列表的长度
};
1
2
3
let list = new LinkedList();
list.append(1);
list.append(2);

从链表中移除元素

场景:1,移除第一个元素;2,移除第一个以外的任一元素

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
// 从特定位置移除一个元素

// 根据元素的值移除元素

this.removeAt = function(position) {
// 检查越界值
if(position > -1 && position < length) {
// 该方法要得到需要移除的元素的位置,就需要验证这个位置是有效的
let current = head, // 将用current变量创建一个对列表中第一个元素的引用
previous, //
index = 0; //

// 移除第一项
if(position === 0) {
// 从列表中移除第一个元素 让head指向列表的第二个元素
// 把head赋为current.next,就会移除第一个元素
head = current.next;
} else {
while (index++ < position) {
// 需要依靠一个细节来迭代列表,直到到达目标位置
previous = current; // 对当前元素的前一个元
素的引用
current = current.next; // current变量总是为对所循环列表的当前元素的引用
}

// 将previous与current的下一项链接起来,跳过current,从而移除它
previous.next = current.next;
// 要从列表中移除当前元素,要做的就是将previous.next和current.next链接起来
}
length--; //
return current.element;
}else{
return null; // 如果不是有效的位置,就返回null
}
}

在任意位置插入元素

使用insert方法,可以在任意位置插入一个元素

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
this.insert = function(position, element){ 
//检查越界值
if (position >= 0 && position <= length){
//需要检查越界值
let node = new Node(element),
current = head, // current变量是对列表中第一个元素的引用
previous,
index = 0;
if (position === 0){ //在第一个位置添加
node.next = current; //把node.next的值设为current
head = node; // 把head的引用改为node
// head和node.next都指向了current
} else {
// 在列表中间或尾部添加一个元素
while (index++ < position){ //需要循环访问列表,找到目标位置
previous = current;
current = current.next;
}
node.next = current; //当跳出循环时,current变量将是对想要插入新元素的位置之后一个元素的引用
// previous.next指向node
previous.next = node; //previous将是对想要插入新元素的位置之前一个元素的引用
}
length++; //更新列表的长度
return true;
} else {
return false; //返回false值,表示没有添加项到列表中
}
};

  • previous将是对列表最后一项的引用
  • current将是null
  • node.next将指向current,而previous.next将指向node

  • 需要把node.next的值指向current。然后把previous.next的值设为node

toString方法会把LinkedList对象转换成一个字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
this.toString = function(){ 
// 会把current变量当作索引
let current = head, //需要有一个起点
string = ''; //还需要初始化用于拼接元素值的变量

while (current) { //循环访问列表中的每个元素

string += current.element + (current.next ? 'n' : '');
//得到了元素的内容,将其拼接到字符串中

current = current.next;
//继续迭代下一个元素
}
return string; //返回列表内容的字符串
};

indexOf方法接收一个元素的值,如果在列表中找到它,就返回元素的位置,否则返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
this.indexOf = function(element){ 
let current = head, //是current,它的初始值是head

// 需要一个index变量来计算位置数
index = -1;
// 循环访问元素
while (current) {

if (element === current.element) {
return index; //检查当前元素是否是我们要找的。如果是,就返回它的位置
}
index++; //如果不是,就继续计数
current = current.next; //检查列表中下一个节点
}
// 如果列表为空,或是到达列表的尾部
// current = current.next将是null
return -1;
};

其他的方法:

1
2
3
4
this.remove = function(element){ 
let index = this.indexOf(element);
return this.removeAt(index);
};
1
2
3
this.isEmpty = function() { 
return length === 0;
};
1
2
3
this.size = function() { 
return length;
};
1
2
3
this.getHead = function(){ 
return head;
};

双向链表

  • 在双向链表中,链接是双向的
  • 一个链向下一个元素,另一个链向前一个元素

1
2
3
4
5
6
7
8
9
10
11
12
function DoublyLinkedList() { 

let Node = function(element){
this.element = element;
this.next = null;
this.prev = null; //新增的 一个新指针
};
let length = 0;
let head = null;
let tail = null; //新增的
//这里是方法
}

在任意位置插入新元素

  • 控制next和prevprevious,前一个)

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
this.insert = function(position, element){ 

//检查越界值
if (position >= 0 && position <= length){

let node = new Node(element),
current = head,
previous,
index = 0;

// 在列表的第一个位置(列表的起点)插入一个新元素1

if (position === 0){ //在第一个位置添加
if (!head){ //新增的
// 只需要把head和tail都指向这个新节点
head = node;
tail = node;
} else {

node.next = current;
// current.prev指针将由指向null变为指向新元素
current.prev = node; //新增的
head = node;

}
} else if (position === length) { //最后一项 //新增的
current = tail; // 控制着指向最后一个元素的指针(tail)
// current变量将引用最后一个元素

current.next = node; //current.next指针(指向null)将指向node
node.prev = current; //node.prev将引用current
tail = node; // 更新tail
// 它将由指向current变为指向node

} else {
// 在列表中间插入一个新元素
while (index++ < position){ //直到到达要找的位置
previous = current;
current = current.next;
}
node.next = current; //node.next将指向current
previous.next = node; // previous.next将指向node
current.prev = node; //新增的current.prev将指向node
node.prev = previous; //新增的node.prev将指向previous
}
length++; //更新列表的长度
return true;
} else {
return false;
}
};

从任意位置移除元素

示例:

从双向链表移除第一个元素的过程:

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
this.removeAt = function(position){ 

//检查越界值
if (position > -1 && position < length){

// current变量是对列表中第一个元素的引用
let current = head,
previous,
index = 0;

//移除第一项
if (position === 0){
// 改变 head 的引用
head = current.next; //将其从 current 改为下一个元素

//如果只有一项,更新tail //新增的
if (length === 1){
//检查要移除的元素是否是第一个元素,如果是,只需要把tail也设为null
tail = null;
} else {
head.prev = null; //把head.prev的引用改为null
}

} else if (position === length-1){ //最后一项 //新增的
// 从最后一个位置移除元素

current = tail; //把tail的引用赋给current变量
tail = current.prev;
tail.next = null;

} else {
// 从列表中间移除一个元素

while (index++ < position){
//需要迭代列表,直到到达要找的位置
// current变量所引用的就是要移除的元素
// 更新previous.next和current.next.prev的引用

// previous.next将指向current.next

previous = current;

// current.next.prev将指向previous

current = current.next;

}

//将previous与current的下一项链接起来——跳过current
previous.next = current.next; // {6}
current.next.prev = previous; //新增的

}
length--;
return current.element;

} else {
return null;
}
};

从最后一个位置移除元素

从列表中间移除一个元素

从头部、从中间和从尾部移除一个元素

循环链表

循环链表和链表之间唯一的区别在于:最后一个元素指向下一个元素的指针(tail.next)不是引用null,而是指向第一个元素(head

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

总结:

JavaScript数据结构之链表

回看笔者往期高赞文章,也许能收获更多喔!

❤️关注+点赞+收藏+评论+转发❤️,原创不易,鼓励笔者创作更好的文章