最近在复习算法知识，打算用JS来实现算法，估计会有一个系列的文章产出。
进入正题。
一般来说，链表这类数据结构插入和删除，而单纯的数组则擅长随机访问。不过对于JS这种神奇的语言，数组本身就是一类特别的对象，JS数组非常灵活，比如长度不固定可以随时扩展，并且其数据在内存中也不连续，对于多数语言来说，数组要从起点或者中间插入元素，或者从中间移除元素，这类操作的开销都很高，JS自己的array相关方法其实都可以方便做到这些操作。本身其实Object 和 Array 都够用了，。不过从 引擎实现的角度考虑，其实其他语言中数组存在的这些问题，在JS底层的背后也是存在的（比如V8就是C++写的）。
链表特点：
- 存储有序的元素集合。
- 每个元素存储元素本身和指向下一个节点的应用
创建链表
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
|
let LinkedList = (function(){
class Node{
constructor (element){
// 构造节点类，表示要插入的元素和指向下一个节点的指针
this.element = element
this.next = null
}
}
//利用WeapMap的不会干扰垃圾回收的特点，
//当weak map中的健在weak map外不存在应用的时候，
//该健与对应的值就被回收
// 长度
const length = new WeapMap()
// 头
const head = new WeaMap()
class LinkedList {
constructor(){
// 初始化一个空链表，长度0，第一个元素为null
this.length = length.set(this,0)
this.head = head.set(this,null)
}
//常见辅助方法
size() {
return length.get(this)
}
isEmpty() {
return this.size() === 0
}
getHead() {
return head.get(this)
}
//追加
append(element){
let node = new Node(element)
let current
if(this.getHead() === null){
//链表为空，则直接加入元素
head.set(this,node)
} else {
// 从第一个元素开始循环，直到current指向最后一项
current = this.getHead()
while(current.next){
current = current.next
}
// 找到最后一项元素后，讲next指向这个新加入的元素node，建立链接
current.next = node
}
//更新长度
let l = this.size()
l++
length.set(this,l)
}
//插入
insert (position,element){
//判断是否越界
if(position>=0 && position <= this.size()){
let node = new Node(element)
//current变量是对列表中第一个元素的引用
let current = this.getHead()
let previous
let index = 0
// 列表的起点添加一个元素，也就是第一个位置
if(position === 0){
node.next = current
head.set(this.node)
}else{
while(index++ < position){
previous = current
current = current.next
}
nodex.next = current
previous.next = node
}
let l = this.size()
l++
length.set(this,l)
return true
} else {
return false
}
}
//移除
removeAt(position){
//判断是否越界
if(position>-1 && position <= this.size()){
//current变量是对列表中第一个元素的引用
let current = this.getHead()
let previous
let index = 0
// 列表的起点移除一个元素，也就是第一个位置
if(position === 0){
head.set(this.current.next)
}else{
while(index++ < position){
previous = current
current = current.next
}
previous.next = current.next
}
let l = this.size()
l--
length.set(this,l)
return true
} else {
return false
}
}
//查找
indexOf(element){
let current = this.getHead()
let index = -1
while(current) {
if(element === current.element){
return index
}
index++
current = current.next
}
return -1
}
}
return LinkedList
})()
|
-EOF-