Fork me on GitHub

js数据结构2--链表

单向链表

js里面实现链表应该算得上是一个比较困难的知识点了,所以专门用一节来记录,首先链表是一种不同于数组的数据结构,链表中的元素在内存并不是连续放置的(数组在内存中是连续存在的),链表中的每个元素由一个存储元素的本身的节点和一个指向下一个元素的引用(也称指针或链接)组成.

  • 数组中访问元素是比较快的(O(1)),但是往数组中添加元素是比较慢的(O(n))
  • 链表中添加,删除元素是比较快的(O(1)),但是聊表中访问元素是慢的(O(n))

下面我们来尝试创建一个链表:
基本上我们在里面只用实现下面以下几个方法:

  • append(element): 向列表尾部添加一个新的项
  • insert(position,element):向列表的特定位置插入一个新的项
  • remove(element):从列表中移除一项
  • indexOf(element):返回元素在列表中的索引,如果没有则返回-1
  • isEmpty(),判断链表会否为空
  • size(),返回链表包含的元素个数
  • 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
function LinkedList() {
// Node为节点
var Node = function (element) {
this.element = element;
this.next = null;
}
var length = 0; // 记录链表长度
var head = null;
// 向列表尾部添加元素
this.append = function (element) {
var node = new Node(element),
current;
if (head === null) {
head = node;
} else {
current = head;
// 循环链表,找到最后一项
while (current.next) {
current = current.next;
}
// 把最后一项的next指针赋值为node
current.next = node;
}
length++;
};
this.insert = function (position, element) {
// 越界检查,可以插在头部和length下标处
if (position >= 0 && position <= length) {
var node = new Node(element),
current = head,
previous, index = 0;
if (position === 0) {
node.next = current;
index = 0;
} else {
while (index < position) {
previous = current;
current = current.next;
index++;
}
node.next = current;
previous.next = node;
}
length++;
return true;
} else {
return false;
}
};
// 把链表里面特定地方的一个值移除
this.removeAt = function (position) {
// 没越界
if (position > -1 && position < length) {
var current = head,
previous, index = 0;
if (position === 0) { // 移除首位,直接让head指向列表的第二个元素
head = current.next;
} else {
// 先从前遍历,让previous是移除元素前一项元素的引用
while (index < position) {
previous = current;
current = current.next;
index++;
}
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
}
// 在链表中找一个特定元素的值
this.indexOf = function (element) {
var current = head,
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
}
// 删除链表特定元素的值
this.remove = function (element) {
var index = this.indexOf(element);
return this.removeAt(index);
}
this.isEmpty = function () {
return length === 0;
}
this.size = function () {
return length;
}
this.getHead = function () {
return head;
}
this.toString = function () {
var current = head,
string = '';
while (current) {
string += ',' + current.element;
current = current.next;
}
return string.slice(1);
}
}
var list = new LinkedList();
list.append(15);
list.append(10);
console.log(list.toString());
list.removeAt(1);
list.insert(1, 5);
console.log(list.toString());
console.log(list.indexOf(15));
console.log(list.isEmpty());

双向链表

在链表里面,一个节点只有链向下一个下一个节点的链接,而在双向链表中,链表是双向的:一个链向下一个元素,一个链向前一个元素:

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

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
function DoublyLinkedList(){
var Node = function(element){
this.element = element;
this.next = null; // 指向前面一个节点
this.prev = null; // 指向后面一个节点
}
var length = 0;
var head = null; // 保存对前面一项的引用
var tail = null; // 保存对最后一项的引用
this.insert = function( position,element ) {
// 检查越界
if(position >= 0 && position < length){
var node = new Node(element),current = head,previous,index = 0;
if(position === 0){ // 在第一个位置插入元素
if(!head){ // 如果第一个位置是空
head = node;
tail = node;
} else {
node.next = current; // 新增元素的next指针指向当前元素
current.prev = node; // 当前元素的前指针指向新增元素
head = node; // head 更新为 新增元素
}
} else if (position === length) { // 在最后一个位置添加
current = tail; // 让当前元素等于尾部
current.next = node;
node.prev = current;
tail = node ;
} else {
while(index < position) {
previous = current;
current = current.next;
index ++;
}
node.next = current;
previous.next = node;
current.prev = node; // 新增
node.prev = previous; // 新增
}
length ++;
return true;
} else {
return false;
}
}
this.removeAt = function( position ){
// 判断越界
if(position > -1 && position < length){
var current = head,previous,index = 0;
// 移除第一项
if(position === 0){
head = current.next;
// 如果只有一项,更新tail
if(length === 1){
tail = null;
} else {
head.prev = null;
}
} else if(position === length-1){ // 删除最后一项
current = tail;
tail = current.prev;
tail.next = null;
} else {
while(index<position) {
previous = current;
current = current.next;
}
// 将previous 和 current的下一项链接起来 --- 跳过current
previous.next = current.next;
current.next.prev = previous; // 新增
}
length-- ;
return current.element;
} else {
return null;
}
}
};

-------------本文结束感谢您的阅读-------------