数据结构之单向链表

链表是一种非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个组成单元称为结点)组成,每个结点包括两个部分:存储在该节点的数据指向下一个节的指针。起始节点称为头结点(head), 最后一个节点的下一个节点为空,其包含的指针指向null

链表的特点

  • 链表非连续存储结构,可以动态调整链表大小,节省了存储空间

链表的分类

常见的链表结构分为以下几类:

  • 单链表
  • 双链表
  • 循环单向链表
  • 循环双向链表

单链表

单链表是最基础的一种链表结构,每个节点(Node)只包含了两个基础数据,数据下一个节点指针

单向链表

我们先设计实现单链表, 单链表结构中包含两个数据类型:节点类(Node), 链表类(LinkList)

Node类

节点类负责存储数据和一个指向下一个节点的指针:

1
2
3
4
function Node = function(data) {
this.data = data; // 存储的数据
this.next = null; // 指向下一个节点指针
}

LinkList类

LinkList类负责管理操作节点,例如:添加节点、删除节点、搜索节点、遍历节点等。其构造函数如下:

1
2
3
4
function LinkList() {
this.head = null; // 头结点
this.length = 0; // 记录节点长度
}

添加节点一般有几种实现方式:追加(append)节点(在尾部添加节点)和指定位置插入(insert)节点

追加节点

追加节点是在链表尾部直接加入一个新的节点,当链表没有节点时,先需要创建一个头结点,否则就顺着节点指针,移动到最后一个节点,将当前链表最后一个节点的指针指向新的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
this.append = function(data) {
var node = new Node(data);
if (this.head == null) {
this.head = node;
} else {
var current = this.head;
var previous;
while(current) {
previous = current;
current = current.next;
}
previous.next = node;
}
this.length++;
}

插入节点

插入节点是在指定位置插入一个新的节点,但是插入位置不能超过当前节点的长度。插入时,要需要先移动到链表指定插入位置:

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
this.insert = function(pos, data) {
var node = new Node(data);

if (pos > -1 && pos < length) {
// 如果插在头结点
if (pos == 0) {
node.next = this.head;
this.head = node;
} else {
var current = this.head;
var previous;
var index = 0;
while(index++ < pos) {
previous = current;
current = current.next;
}

previous.next = node;
node.next = current;
}


this.length++;
return true;
}
return false;
}

删除节点

删除指定位置的节点,需要先移动到指定位置的上一个节点,将上一个节点的指针指向当前位置的下一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
this.removeAt = function(pos) {
if (pos > -1 && pos < length) {
var current = this.head;
var previous;
var index = 0;
while(index++ < pos) {
previous = current;
current = current.next;
}

previous.next = current.next;

this.length--;
return true;
}

return false;
}

搜索节点

将每个节点的存储数据和给定元素匹配,如果匹配成功则返回节点,否则返回null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
this.search = function(data) {
if (data) {
var current = this.head;

while (current) {
if (current.data == data) {
return current;
}
current = current.next;
}

}
return null;
}

遍历节点

遍历节点其实在相关链表操作中都有运用,遍历节点需要一直移动到链表最后一个节点,即包含的指针指向null的节点,以打印节点为例:

1
2
3
4
5
6
7
8
9
10
11
this.toString = function() {
var str = head.data;
var current = head.next;

while (current) {
str += ','+ current.data;
current = current.next;
}

return str;
}

完整实现代码

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
// 单项链表

function Node = function(data) {
this.data = data;
this.next = null;
}

function LinkList() {

head = null;

length = 0;


// 在链表最后添加节点
this.append = function(data) {
var node = new Node(data);
if (head == null) {
head = node;
} else {
var current = head;
var previous;
while(current) {
previous = current;
current = current.next;
}
previous.next = node;
}
length++;
}

// 指定位置插入节点
this.insert = function(pos, data) {
var node = new Node(data);

if (pos > -1 && pos < length) {
if (pos == 0) {
node.next = head;
head = node;
} else {
var current = head;
var previous;
var index = 0;
while(index++ < pos) {
previous = current;
current = current.next;
}

previous.next = node;
node.next = current;
}


length++;
return true;
}
return false;
}

this.removeAt = function(pos) {
if (pos > -1 && pos < length) {
var current = head;
var previous;
var index = 0;
while(index++ < pos) {
previous = current;
current = current.next;
}

previous.next = current.next;

length--;
return true;
}

return false;
}

// 从链表尾部移除节点
this.pop = function() {
var current = head;
var previous;

while (current.next) {
previous = current;
current = current.next;
}

previous.next = null;

length--;
}

// 搜索节点
this.search = function(data) {
if (data) {
var current = head;
var previous;

while (current) {
if (current.data == data) {
return current;
}
previous = current;
current = current.next;
}

}
return null;
}

// 遍历节点
this.toString = function() {
var str = head.data;
var current = head.next;

while (current) {
str += ','+ current.data;
current = current.next;
}

return str;
}

// 获取链表长度
this.getLength = function() {
return length;
}

}
有用就打赏一下作者吧!