近来无聊，在GitHub上找到了一个不错的数据结构和算法教程，索性Fork之后，学习一下。
按照教程推荐的顺序，这一篇就从链表开始说起好了。
任何数据结构都有自己的适用场景。链表的存在就是为插入快，删除快的操作而存在的，从时间复杂度来讲为O(1)。但是链表也有其缺点，就是查询速度慢，时间复杂度为O(n)，呈线性增长。
以下是用JavaScript代码实现的链表结构
首先，我们先创建基础的节点类LinkedListNode，一个节点类包含了一个值和一个指针，指针指向为下一个节点的地址。
1
2
3
4
5
6
| export default class LinkedListNode {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
|
然后我们创建链表类LinkedList，每一个链表都必须包含一个头部和一个尾部，类型都为LinkedListNode。空链表的头部和尾部都为null，只包含一个元素的链表头部和尾部为同一元素。
1
2
3
4
5
6
7
8
9
| export default class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
}
|
插入操作
append
append操作是把元素加入到链表的尾部，该操作的时间复杂度为O(1)，因为它直接定位到尾部元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
* @param {*} value
* @return {LinkedList}
*/
append(value) {
const newNode = new LinkedListNode(value);
if(!this.head) {
this.head = newNode;
this.tail = newNode;
return this;
}
this.tail.next = newNode;
this.tail = newNode;
return this;
}
|
prepend
prepand操作是把元素加入到链表的头部，该操作的时间复杂度为O(1)，因为它直接定位到头部元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
* @param {*} value
* @return {LinkedList}
*/
prepand(value) {
const newNode = new LinkedListNode(value, this.head);
this.head = newNode;
if(!this.tail) {
this.tail = newNode;
}
return this;
}
|
搜索操作
find
find操作是遍历链表元素的操作，找的到则返回元素，找不到则返回null。因为它的时间复杂度为O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| find(value) {
if(!this.head) {
return null;
}
let currentNode = this.head;
while(currentNode) {
if(currentNode.value === value) {
return currentNode;
}
currentNode = currentNode.next;
}
return null;
}
|
删除操作
delete
delete操作是删除元素的操作，下面的例子采用了遍历链表的方法，时间复杂度为O(n)。但实际上，链表删除的操作可以实现时间复杂度为O(1)。
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
| delete(value) {
if(!this.head) {
return null;
}
let node = this.head;
if(this.head.value === value) {
if(this.head == this.tail) {
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
}
return node;
}
while(node.next && node.next.value !== value) {
node = node.next;
}
if(node.next) {
if(node.next == this.tail) {
this.tail = node;
}
node.next = node.next.next;
return node;
} else {
return null;
}
}
|
