【数据结构】--链表

【数据结构】--链表

五月 26, 2018

什么是链表?

来自Wiki: 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存贮到下一个节点的指针(Pointer)。

直白的说就是: 链表有成千上万个节点,他们象积木一样排列成直线,每一个节点存储的是下一个节点的位置信息,而不是积木本身。

链表有什么用?

为了性能。通常在对性能要求高的地方会放弃数组,而是用链表

链表定义

一个基本的链表(蛇)需要要有的功能包括:

  • 蛇头: getHead():获取表头

  • 蛇长: size():获取长度

  • 蛇是否还活着: isEmpty():判空

  • 蛇身弱点位置(七寸): indexOf(element):按元素内容查找位置

  • 切一寸蛇肉: removeAt(position):按位置删除

  • 切一截坏肉(胆囊): remove(element):按元素内容删除

  • 蛇也要长身体: append(element):向表尾部追加元素

  • 蛇能够变形: insert(position, element):按位置插入

  • 滑稽: printSelf():打印自己

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
// snake有2个属性,一个是蛇头,一个是蛇长.
// 蛇头与蛇身都是由node节点构成
'use strict'

function sanke() {
this.head = null
this.len = 0
}
var Node = function (val) {
this.val = val
this.next = null
}
sanke.prototype = {
getHead: function () {
return this.head
},
size: function () {
return this.len
},
isEmpty: function () {
return this.len === 0;
},
indexOf: function (val) {
var current = this.head,
index = 0;
while (current) {
if (val === current.val) {
return index;
}
index++;
current = current.next;
}
return -1;
},
// 返回被删掉的节点
removeAt: function (position) {
// 越界检查
if (position > -1 && position < this.len) {

var current = this.head,
previous,
index = 0;
if (position === 0) {
this.head = current.next
} else {
while (index++ < position) {
previous = current;
current = current.next
}
// current是被删除的元素,前一个与后一个连接起来
// 自然断掉了与current的链接
previous.next = current.next
}
this.len--;
return current.val
} else {
return null
}
},
remove: function (element) {
// 利用已有方法
var index = this.indexOf(element)
return this.removeAt(index)
},
append: function (val) {
var node = new Node(val)
var current;

if (this.head == null) {
this.head = node
} else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.len++;
},
insert: function (position, element) {
// 越界检查
if (position >= 0 && position <= this.len) {

var node = new Node(element),
current = this.head,
previous,
index = 0;

if (position === 0) {
node.next = current;
this.head = node;
} else {
while (index < position) {
previous = current;
current = current.next
index++;
}
node.next = current;
previous.next = node;
}
// this.append(element)
this.len++;
return true;
}
},
printSelf: function () {
var current = this.head,
string = "";

while (current) {
string += current.val + (current.next ? " " : "");
current = current.next;
}
console.log(string);
}
}

// 验证

var link = new sanke()
link.append('a')
link.append('b')
link.append('c')
link.append('d')

console.log(link);
console.log(link.indexOf('c'));
console.log(link.removeAt(1));
console.log(link);
console.log(link.removeAt(1));
console.log(link);
link.insert(1, 'mm')
console.log(link);
link.printSelf()

数据结构优劣

数据结构图