数据结构-链表

前言

我们前面栈和队列实质上使用数组这种结构实现的,在存储上数组元素的物理地址都是连续,而多个的数组存贮因为地址不连续就会造成多个内存片段冗余,有很多空白的内存空间被浪费,为避免资源浪费,链表应运而生。

链表特性

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。一般的链表节点包括表内容、指向下个节点的指针。如下图:

链表实现思路

链表的实现: 包括节点的定义(借助辅助类:节点内容和一个节点的指向)、各个节点如何串连起来(在上个节点里保存下个节点的指向信息)、然后实现基本的添加,删除功能即可。注意表尾下个节点指向为空。

代码实现

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
var LinkedList = function(){
// 表头
var head = null;
// 表长度
var length = 0;

// 节点定义
var Node = function(element, next){
this.element = element;
this.next = null;
}

// 尾部添加
this.append = function(element){
// 创建新节点
var node = new Node(element);
// 当链表头为空,说明链表为空,则将新元素赋值给表头
if(head == null){
head = node;
}else{
var current = head;
while(current.next){
current = current.next;
}
/** while 循环结束,current已经是最后一项了 */
current.next = node;
}
length++;
}

// 获取表头
this.getHead = function(){
return head;
}

// 插入
this.insert = function(position, element){
// 不越界
if(position>-1 && position<length){
var node = new Node(element);
if(position === 0){
// 替换头部
let current = head;
head = node;
head.next = current;
}else{
let index = 0;
let current = head;
let previous = null;
while(current.next && index != position){
previous = current;
current = current.next;
index++;
}
// 在previous与current间插入node
previous.next = node;
node.next = current;
}
length++;
}
}

// 按位置删除
this.removeAt = function(position){
if(position>-1 && position<length){
// 删除第一个
if(position === 0){
let current = head;
// 第二个节点覆盖一个
head = current.next;
}else{
let current = head;
let previous = null;
let index = 0;
while(current.next && index != position){
previous = current;
current = current.next;
index++;
}
previous.next = current.next;
}
length--;
// 返回删除元素
return current;
}
return null;
}

// 查找元素索引
this.indexOf = function(element){
let current = head;
let index = 0;
while(current){
if(current.element == element){
return index;
}
current = current.next;
index++;
}
// 找不到返回-1
return -1;
}

// 移除元素
this.remove = function(element){
return this.removeAt(this.indexOf(element))
}

// 是否为空
this.isEmpty = function(){
return length === 0;
}
// 长度
this.size = function(){
return length;
}
}

链表是一种比较特殊的数据结构,链式结构也导致了元素移除是一件比较容易的实情(改变链接的指向),不像线性结构那样得移动大量的元素。同时不必将元素保存在连续的地址上,避免了碎片化造成不必要的空间浪费。

坚持原创技术分享,您的支持将鼓励我继续创作!