UNPKG

5.29 kBMarkdownView Raw
1# 单向链表
2
3在计算机科学中, 一个 **链表** 是数据元素的线性集合, 元素的线性顺序不是由它们在内存中的物理位置给出的。 相反, 每个元素指向下一个元素。它是由一组节点组成的数据结构,这些节点一起,表示序列。
4
5在最简单的形式下，每个节点由数据和到序列中下一个节点的引用(换句话说，链接)组成。这种结构允许在迭代期间有效地从序列中的任何位置插入或删除元素。
6
7更复杂的变体添加额外的链接，允许有效地插入或删除任意元素引用。链表的一个缺点是访问时间是线性的(而且难以管道化)。
8
9更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存位置。
10
11![Linked List](https://upload.wikimedia.org/wikipedia/commons/6/6d/Singly-linked-list.svg)
12
13## 基本操作的API及示例
14
15### 追加
16
17```text
18append(value)
19向链表中追加一个节点，参数为要追加的节点的值，返回链表的头结点
20示例：
21 let linklist = new LinkList();
22 linklist.append(1);
23 linklist.append(2);
24描述：
25 1——>2——>null
26```
27
28### 向前追加
29
30```text
31prepend(value)
32向链表头部之前添加一个节点，该节点会成为新的头结点，参数为要添加的节点的值，返回链表的头结点
33示例：
34 let linklist = new LinkList();
35 linklist.append(1);
36 linklist.append(2);
37 linklist.prepend(0);
38描述：
39 0——>1——>2——>null
40```
41
42### 弹出尾节点
43
44```text
45pop()
46推出尾节点，返回推出的节点
47示例：
48 let linklist = new LinkList();
49 linklist.append(1);
50 linklist.append(2);
51 linklist.prepend(0);
52 linklist.pop();
53描述：
54 0——>1——>null
55```
56
57### 推出头结点
58
59```text
60shift()
61推出头节点，返回推出的节点
62示例：
63 let linklist = new LinkList();
64 linklist.append(1);
65 linklist.append(2);
66 linklist.append(3);
67 linklist.shift();
68描述：
69 2——>3——>null
70```
71
72### 清空链表
73
74```text
75clear()
76清空链表
77示例：
78 let linklist = new LinkList();
79 linklist.append(1);
80 linklist.append(2);
81 linklist.clear();
82描述：
83 null
84```
85
86### 查找节点
87
88```text
89findNode(arg|value)
90查找链表中的节点，参数为节点的值或者查询条件函数，返回查找的节点
91示例：
92 let linklist = new LinkList();
93 linklist.append(1);
94 linklist.append(2);
95 linklist.findNode(value=>value===1);
96描述：
97 1——>2——>null
98```
99
100### 删除节点
101
102```text
103deleteNode(arg|value)
104删除链表中的节点，参数为节点的值或者查询条件函数，返回删除的节点
105示例：
106 let linklist = new LinkList();
107 linklist.append(1);
108 linklist.append(2);
109 linklist.deleteNode(1);
110 linklist.deleteNode(value=>value===2);
111描述：
112 2——>null
113```
114
115### 向后插入
116
117```text
118insertAfter(value,node)
119在某个节点后插入一个新节点，第一个参数为要插入的新节点的值，第二个参数为要在其后插入新节点的节点，返回true或false
120示例：
121 let linklist = new LinkList();
122 linklist.append(1);
123 linklist.append(2);
124 let node = linklist.findNode(1);
125 linklist.insertAfter(3,node);
126描述：
127 1——>3——>2——>null
128```
129
130### 获取头结点
131
132```text
133getHeadNode()
134示例：
135 let linklist = new LinkList();
136 linklist.append(1);
137 linklist.append(2);
138 let headNode = linklist.getHeadNode();
139描述：
140 1——>2——>null
141```
142
143### 获取尾结点
144
145```text
146getTailNode()
147示例：
148 let linklist = new LinkList();
149 linklist.append(1);
150 linklist.append(2);
151 let headNode = linklist.getTailNode();
152描述：
153 1——>2——>null
154```
155
156### 转换字符串
157
158```text
159toString()
160将链表转为字符串
161示例：
162 let linklist = new LinkList();
163 linklist.append(1);
164 linklist.append(2);
165 let str = linklist.toString(); // 1,2
166描述：
167 1——>2——>null
168```
169
170### 转双向链表
171
172```text
173toDoubleLinkList()
174将单向链表转换为双向链表
175示例：
176 let linklist = new LinkList();
177 linklist.append(1);
178 linklist.append(2);
179 let doublelinklist = linklist.toDoubleLinkList();
180描述：
181 1<——>2——>null
182```
183
184### 转循环链表
185
186```text
187toCycleLinkList()
188将单向链表转换为双向链表
189示例：
190 let linklist = new LinkList();
191 linklist.append(1);
192 linklist.append(2);
193 let cyclelinklist = linklist.toCycleLinkList();
194```
195
196### 链表转数组
197
198```text
199toArray()
200将链表转为数组
201示例：
202 let linklist = new LinkList();
203 linklist.append(1);
204 linklist.append(2);
205 let array = linklist.toArray(); // [1,2]
206描述：
207 1——>2——>null
208```
209
210### 数组转链表
211
212```text
213fromArray(array)
214该方法为静态方法，可以将数组装换为单向链表，参数为待转换的数组，返回值为转换后的单向链表
215示例：
216 LinkList.fromArray([1,2,3,4,5]);
217描述：
218 1——>2——>3——>4——>5——>null
219```
220
221### 链表长度
222
223```text
224Size
225该属性用去获取链表的长度
226示例：
227 let linklist = new LinkList();
228 linklist.append(1);
229 linklist.append(2);
230 linklist.append(3);
231 let size = linklist.Size; // 3
232描述：
233 1——>2——>3——>null
234```
\No newline at end of file