数据结构-链表

链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

创建链表

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
function LinkedList() {
// Node类表示要加入链表的项,element是项的值,next是指向下一项的指针。
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) {
// 检查越界值
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 {
return false;
}
};
// 从特表特定位置移除一项
this.removeAt = function(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 {
return null;
}
};
// 从列表中移除一项
this.remove = function(element) {
var index = this.indexOf(element);
return this.removeAt(index);
};
// 返回元素所有列表的索引。如果列表没有此元素则返回-1
this.indexOf = function(element) {
var current = head,
index = 0;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
// 如果列表为空,返回true。否则为false
this.isEmpty = function() {
return length === 0;
};
// 返回链表中的元素个数
this.length = 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);
};
}