Fork me on GitHub

链表

algorithm/linked-list/banner

链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称为指针或链接,通常叫指针)组成。自己无聊的时候还翻译一点维基百科上的链表的介绍

数组的缺点

栈和队列数据结构中,存储数据我们是使用了数组的形式。但是,数组不总是组织数据的最佳的结构。原因如下:

  1. 数组被实现成对象,与其他语言(比如C++和Java)的数组相比,效率很低。【主要原因】
  2. 数组的长度是固定的,所以当数组已被数据填满的时,再要加入新的元素会非常困难。
  3. 从数组的起点或中间插入或移除项的成本很高。虽然splice等方法能帮方便的实现,但是背后的原理还是需要移动元素。

所以,当数组的代价高的时候,需要考虑其他的数据结构,比如现在要说的链表。

创建链表类

通过一个构造函数创建链表类:

1
2
3
function LinkedList() {
// somecode here ...
}

节点数据也是使用一个类进行存放,这里我们叫做Node类:

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

完整代码

链表的基本的完整代码如下:

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
function LinkedList() {

// 辅助类
var Node = function(element) {
this.element = element; // 存放数据
this.next = null; // 存放指针
};

// 链表的长度
var length = 0;

// 初始化头指针为空
var head = null;

// 向链表尾部追加元素
this.append = function(element){
// 创建一个node节点
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.removeAt = function(position){
// 检查指定移除的position是否越界
if(position > -1 && position < length){ // 未越界
var current = head, // 当前元素指向头节点
previous, // 上一个节点
index = 0; // 节点的索引

// 移除第一项
if(position == 0){
head = current.next;
} else{
while (index++ < position){
previous = current;
current = current.next;
}

// 将previous与current的下一项链接起来:跳过current,从而移除它
previous.next = current.next;
}

// 链表长度减一
length--;

// 返回删除的元素
return current.element;
}else{
// position越界的情况
return null;
}
};

// 任意位置插入一个元素
this.insert = function(position , element){
// 检查position是否越界
if(position >= 0 && position <=length){

var node = new Node(element), // 新建一个节点
current = head, // 初始当前节点指向头节点
previous, // 前一个节点
index = 0; // 默认索引从第一个开始

if(position == 0){ // 在第一个位置添加元素
node.next = current;
head = node;
} else {
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}

// 更新列表长度
length++;

return true;

} else{
// position越界
return false;
}
};

// 将LinkedList对象转换成一个字符串
this.toString = function() {
var current = head,
string = '';

while(current){
string += current.element;
current = current.next;
}

return string;
};

// 查找元素在链表中的位置
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;
}

}

更多的代码请查看https://github.com/reng99/algorithm

循环链表

上面所说的链表是单链表。尽管从链表的头节点遍历到尾节点很简单,但反过来,从后向前遍历九没有那么简单了。这时候我们可以通过给Node对象增加一个头指针的属性就容易多了。

Node类就变成下面这样了:

1
2
3
4
5
function Node(element) {
this.element = element;
this.next = null;
this.prev = null;
}

整个双向链表的类如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
function DoublyLinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
this.prev = null; // 新增的前指针
};

var length = 0;
var head = null;
var tail = null; // 新增的尾节点

// methods here ...
}

其相关的方法和单链表的方法是大同小异,还有一个循环链表也是差不多啦。

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)