数据结构和算法，和语言是无关的
单向链表
- 既然有数组为什么用链表
- 数组的创建需要申请一段连续的内存空间(一整块的内存)，并且大小是固定的(大多数编程语言数组都是固定的)，所以如果当前数组不能满足容量需求时，需要扩容。(一般情况是申请一个更大的数组，比如2倍，然后将原数组中的元素复制过去)
- 而且在数组开头或中间位置插入数据的成本很高，需要进行大量元素位移
- 为了解决上面的问题，我们需要链表这种数据结构
- 特点
- 不同于数组，链表中的元素在内存中不必是连续的空间
- 链表的每个元素由一个存储元素本身的节点，和一个指向下一个元素的引用(有些语言称为指针)组成
- 相较于数组的优点
- 内存空间不必是连续的，可以充分利用计算机的内存。实现灵活的动态管理
- 链表不必在创建时就确定大小，并且大小可以无限的延伸下去
- 链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多
- 相较于数组的缺点
- 链表访问任何一个位置的元素，都需要从头开始访问。(无法跳过第一个元素访问任何其他元素)
- 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应元素
- 单向链表封装
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/**
* 声明节点对象
*/
function Node(element) {
// 保存元素
this.element = element;
// 保存指针(指向下一个节点)
this.next = null;
}
/**
* 声明链表
*/
function LinkedList() {
// 链表头
this.head = null;
// 链表长度
this.length = 0;
// append(element) 向链表尾部追加元素
this.append = function(element) {
// 1.根据element创建Node对象
var newNode = new Node(element);
// 2.追加到最后
if (!this.head) {
// 节点不存在的时候
this.head = newNode;
} else {
// 节点存在的时候，从Head依次找到最后一个节点
var current = this.head;
while(current.next) {
current = current.next;
}
// 将最后一个节点的next指向新创建的Node就可以
current.next = newNode;
}
// length
this.length++;
}
// insert(position, element) 向链表的特定位置插入某一个元素
this.insert = function (position, element) {
// 1.判断越界
if (position < 0 || position > this.length) {
return false;
}
// 2. 创建新的节点
var newNode = new Node(element);
// 3. 插入元素
if (position === 0) {
// 插入到头部的时候
newNode.next = this.head;
this.head = newNode;
} else {
var index = 0;
var current = this.head;
var previous = null;
while(index++ < position) {
previous = current;
current = current.next;
}
previous.next = newNode;
newNode.next = current;
}
this.length++;
return true;
}
// get(position) 获取对应位置的元素
this.get = function (position) {
// 1.判断越界
if (position < 0 || position > this.length - 1) {
return null;
}
// 2. 查找元素
var index = 0;
var current = this.head;
while (index++ < position) {
current = current.next;
}
return current.element;
}
// indexOf(element) 返回元素在列表中的索引。如果列表中没有该元素，则返回-1
this.indexOf = function (element) {
// 1. 获取第一个元素
var current = this.head;
var index = 0;
while(current) {
if (current.element === element) {
return index;
}
current = current.next;
index++;
}
return -1;
}
// update(position, element) 修改某个位置的元素
this.update = function (position, element) {
// 1.remove
var result = this.removeAt(position);
// 2.insert
this.insert(position, element);
return result;
}
// removeAt(position) 从列表指定位置移除一项
this.removeAt = function (position) {
// 1.判断越界
if (position < 0 || position > this.length - 1) {
return null;
}
// 2.删除元素
var current = this.head;
var previous = null;
var index = 0;
if (position === 0) {
this.head = current.next;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
// 到这里说明已经找到要删除的元素
previous.next = current.next;
}
this.length--;
// 返回删除的元素
return current.element;
}
// remove(element) 从列表中移除一项
this.remove = function (element) {
// 1.获取删除元素的位置
var index = this.indexOf(element);
if (index === -1) return;
// 2.删除元素
var result = this.removeAt(index);
return result
}
// isEmpty() 链表不包含任何元素，返回true
this.isEmpty = function () {
return this.length === 0;
}
// size() 链表中元素个数
this.isEmpty = function () {
return this.length;
}
}
