链表
概念
链表是存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素有一个存储元素本身的节点和一个指向下一个元素的引用（指针）组成
看上图我们将链表的尾元素指向了 null 节点，表示链接结束的位置，链表的起始位置比较麻烦，我们添加一个header的特殊节点表示头节点，如下：
插入节点
确定插入节点的位置，修改前驱节点指向插入的新节点，新节点指向原来前驱节点指向的节点，如下图
删除节点
待删除的前驱节点指向待删除节点的下一节点，如下图
链表和数组对比
数组和链表都可以实现存储多个元素，两者各有自己的优劣。
- 数组可以通过元素的下表，直接访问任何位置的任何元素；而想要访问链表中间的一个元素，需要从起点（表头）开始迭代链表，直到找到所需的元素
- 链表对比数组的一个好处是，添加或移除元素的时候不需要移动其他元素
链表的设计
写两个类，一个Node类表示节点，一个LinkedList类提供插入、删除节点等一些操作
Node类
// 节点
function Node(element) {
this.element = element // 当前节点的元素
this.next = null // 下一个节点链接
}
1
2
3
4
5
2
3
4
5
LinkedList类
// 链表类
function LinkedList () {
this.head = new Node( 'head' ); // 头节点
this.find = find; // 查找节点
this.insert = insert; // 插入节点
this.remove = remove; // 删除节点
this.findPrev = findPrev; // 查找前一个节点
this.display = display; // 显示链表
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
head节点的next属性初始化为 null ，当有新元素插入时，next会指向新的元素
insert方法：插入一个节点
// 插入节点
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
currNode.next = newNode;
}
1
2
3
4
5
6
7
2
3
4
5
6
7
find方法：查找给定节点
思路
- 创建一个新节点，将链表的头节点赋给这个新创建的节点
- 然后在链表上循环，如果当前节点的 element 属性和我们要找的信息不符，就将当前节点移动到下一个节点
- 如果查找成功，该方法返回包含该数据的节点；否则，就会返回null
// 查找给定节点
function find ( item ) {
var currNode = this.head;
while ( currNode.element != item ){
currNode = currNode.next;
}
return currNode;
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
dispaly方法：打印链表
// 显示链表元素
function display () {
var currNode = this.head;
while ( !(currNode.next == null) ){
console.log( currNode.next.element );
currNode = currNode.next;
}
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
remove方法：删除一个节点
思路
- 找到待删除节点的前一个节点
- 修改它的 next 属性，使其不再指向待删除的节点，而是待删除节点的下一个节点
- 我们定义一个 findPrevious 方法遍历链表，查找待删除节点的前一个节点
// 查找带删除节点的前一个节点
function findPrev( item ) {
var currNode = this.head;
while ( !( currNode.next == null) && ( currNode.next.element != item )){
currNode = currNode.next;
}
return currNode;
}
// 删除节点
function remove ( item ) {
var prevNode = this.findPrev( item );
if( !( prevNode.next == null ) ){
prevNode.next = prevNode.next.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例
// 节点
function Node(element) {
this.element = element // 当前节点的元素
this.next = null // 下一个节点链接
}
// 链表类
function LinkedList () {
this.head = new Node( 'head' ); // 头节点
this.find = find; // 查找节点
this.insert = insert; // 插入节点
this.remove = remove; // 删除节点
this.findPrev = findPrev; // 查找前一个节点
this.display = display; // 显示链表
}
// 插入节点
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
currNode.next = newNode;
}
// 查找给定节点
function find ( item ) {
var currNode = this.head;
while ( currNode.element != item ){
currNode = currNode.next;
}
return currNode;
}
// 显示链表元素
function display () {
var currNode = this.head;
while ( !(currNode.next == null) ){
console.log( currNode.next.element );
currNode = currNode.next;
}
}
// 查找带删除节点的前一个节点
function findPrev( item ) {
var currNode = this.head;
while ( !( currNode.next == null) && ( currNode.next.element != item )){
currNode = currNode.next;
}
return currNode;
}
// 删除节点
function remove ( item ) {
var prevNode = this.findPrev( item );
if( !( prevNode.next == null ) ){
prevNode.next = prevNode.next.next;
}
}
// 示例
var nameList = new LinkedList()
nameList.insert('木子', 'head')
nameList.insert('小明', '木子')
nameList.insert('凯阳', '小明')
nameList.display() // 木子 小明 凯阳
nameList.insert('林夕', '木子')
nameList.display() // 木子 林夕 小明 凯阳
nameList.remove('木子')
nameList.display() // 林夕 小明 凯阳
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
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
第二种设计
var LinkedList = function() {
const Node = function(element) {
this.element = element
this.next = null
}
let head = null
let current
let length = 0
// 在链表末尾加入元素
this.append = function(element) {
const node = new Node(element)
if (head === null) { // 插入第一个链表
head = node
} else {
current = head
while (current.next) { // 找到最后一个节点
current = current.next
}
current.next = node
}
length++
}
// 移除指定位置元素
this.removeAt = function(position) {
if (position > -1 && position < length) {
let previous
let index = 0
if (position === 0) { // 如果是第一个链表的话, 特殊对待
head = head.next
} else {
current = head
while (index < position) { // 循环找到当前要删除元素的位置
previous = current
current = current.next
index++
}
previous.next = current.next
}
length--
}
}
// 在指定位置加入元素
this.insert = function(position, element) {
const node = new Node(element)
let index = 0
let current, previous
if (position > -1 && position < length + 1) {
if (position === 0) { // 在链表最前插入元素
current = head
head = node
head.next = current
} else {
current = head
while (index < position) { // 同 removeAt 逻辑, 找到目标位置
previous = current
current = current.next
index++
}
previous.next = node // 在目标位置插入相应元素
node.next = current
}
length++
}
}
// 链表中是否含有某个元素, 如果有的话返回相应位置, 无的话返回 -1
this.indexOf = function(element) {
let index = 0
current = head
while (index < length) {
if (current.element === element) {
return index
}
current = current.next
index++
}
return -1
}
// 移除某元素
this.remove = function(element) {
const position = this.indexOf(element)
this.removeAt(position)
}
// 获取大小
this.size = function() {
return length
}
// 获取最开头的链表
this.getHead = function() {
return head
}
// 是否为空
this.isEmpty = function() {
return length === 0
}
// 打印链表元素
this.log = function() {
current = head
let str = current.element
while (current.next) {
current = current.next
str = str + ' ' + current.element
}
return str
}
}
// 示例
var animals = new LinkedList()
animals.append('马')
animals.append('羊')
animals.append('牛')
animals.append('猪')
animals.log() // 马 羊 牛 猪
animals.remove('牛')
animals.log() // 马 羊 猪
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
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
双向链表
TODO
待补充
循环链表
TODO
待补充