要点:单链表详解、JavaScript单链表方法的封装
认识链表
一、链表和数组
链表和数组一样,可以用于存储一系列的元素,但是链表和数组的实现机制完全不同。
1.1 数组
数组特点:
存储多个元素,数组(或列表)可能是最常用的数据结构。
几乎每一种编程语言都有默认实现数组结构,提供了一个便利的 []
语法来访问数组元素。
数组缺点:
数组的创建需要申请一段连续的内存空间(一整块内存),并且大小是固定的,当前数组不能满足容量需求时,需要扩容。 (一般情况下是申请一个更大的数组,比如 2 倍,然后将原数组中的元素复制过去)
在数组开头或中间位置插入数据的成本很高,需要进行大量元素的位移。
1.2 链表
链表特点:
存储多个元素,另外一个选择就是使用链表。
不同于数组,链表中的元素在内存中不必是连续的空间。
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针)组成。
链表优点:
内存空间不必是连续的,可以充分利用计算机的内存,实现灵活的内存动态管理。
链表不必在创建时就确定大小,并且大小可以无限延伸下去。
链表在插入和删除数据时,时间复杂度可以达到 $O(1)$,相对数组效率高很多。
链表缺点:
访问任何一个位置的元素时,需要从头开始访问。(无法跳过第一个元素访问任何一个元素)
无法通过下标值直接访问元素,需要从头开始一个个访问,直到找到对应的元素。
虽然可以轻松地到达下一个节点,但是回到前一个节点是很难的。
1.3 链表和数组到底有多大的差异?
数组和链表同样作为线性的数组结构,二者在很多方便都是相同的,只在细微的操作和使用场景上有差异而已。而使用场景,很难在题目中直接考察。
对于我们做题来说,二者的差异通常就只是细微的操作差异。这么说大家可能感受不够强烈,举几个例子。
数组的遍历:
1 2 3
| for(int i = 0; i < arr.size();i++) { print(arr[i]) }
|
链表的遍历:
1 2 3
| for (ListNode cur = head; cur != null; cur = cur.next) { print(cur.val) }
|
**可以看出二者逻辑是一致的,只不过细微操作不一样。**比如:
- 数组是索引 ++
- 链表是 cur = cur.next
如果我们需要逆序遍历呢?
1 2 3
| for(int i = arr.size() - 1; i > - 1;i--) { print(arr[i]) }
|
如果是链表,通常需要借助于双向链表。而双向链表在力扣的题目很少,因此大多数你没有办法拿到前驱节点,这也是为啥很多时候会自己记录一个前驱节点 pre 的原因。
1 2 3
| for (ListNode cur = tail; cur != null; cur = cur.pre) { print(cur.val) }
|
如果往数组末尾添加一个元素就是:
链表的话,很多语言没有内置的数组类型。比如力扣通常使用如下的类来模拟。
1 2 3 4 5 6 7
| public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }
|
我们是不能直接调用 push 方法的。想一下,如果让你实现这个,你怎么做?
其实很简单:
1 2 3
| tail.next = new ListNode('lucifer') tail = tail.next
|
经过上面两行代码之后, tail 仍然指向尾部节点。
比如有的题目需要你复制一个新的链表, 你是不是需要开辟一个新的链表头,然后不断拼接(push)复制的节点?这就用上了。
对于数组的底层也是类似的,一个可能的数组 push 底层实现:
1 2
| arr.length += 1 arr[arr.length - 1] = 'lucifer'
|
总结一下, 数组和链表逻辑上二者有很多相似之处,不同的只是一些使用场景和操作细节,对于做题来说,我们通常更关注的是操作细节。关于细节,接下来给大家介绍,这一小节主要让大家知道二者在思想和逻辑的神相似。
有些小伙伴做链表题先把链表换成数组,然后用数组做,本人不推荐这种做法,这等于是否认了链表存在的价值,小朋友不要模仿。
单向链表
一、链表结构
单向链表类似于火车,有一个火车头,火车头会连接一个节点,节点上有乘客,并且这个节点会连接下一个节点,以此类推。
链表的火车结构

链表的数据结构
head 属性指向链表的第一个节点。
链表中的最后一个节点指向 null
。
当链表中一个节点也没有的时候,head 直接指向 null
。

给火车加上数据后的结构

相关术语
头指针:
指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针;
头指针具有标识作用,所以常用头指针冠以链表的名字;
无论链表是否为空,头指针均不为空。头指针是链表的必要元素
头结点:
头结点是为了操作的统一和方便而设立的,放在第一元素的结点之前,其数据域一般无意义(也可存放链表的长度)
有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了
头结点不一定是链表必须要素
首元结点:是指链表中存储第一个数据元素a1的结点
有头结点有什么好处?
①有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了
②便于空表和非空表的统一处理
当链表不设头结点时,假设L为单链表的头指针,它应该指向首元结点,则当单链表为长度n为0的空表时,L指针为空(判定空表的条件可记为:L==NULL
)。增加头结点后,无论链表是否为空,头指针都是指向头结点的非空指针。头指针指向头结点。若为空表,则头结点的指针域为空(判定空表的条件可记为:L ->next== NULL
)
顺序表每个元素的存储位置都可从线性表的起始位置计算得到。而在单链表中,各个元素的存储位置都是随意的。取得第i
个数据元素必须从头指针出发顺链进行寻找,也称为顺序存取的存取结构。之前说的顺序表是随机存取而链表是顺序存储
单链表是由若干个结点构成,所以先定义一下结点。每一个结点都是有两部分组成,一部分是数据元素本身(数据域data)其数据类型根据实际问题的需要确定。另一部分是指向下一个元素(结点)的指针(指针域next)存放下一个元素的地址,结点可以用C语言中的结构体实现当中包含两个成员。
二、链表中的常见操作
JavaScript方法
append(element)
向链表尾部添加一个新的项。
insert(position, element)
向链表的特定位置插入一个新的项。
get(position)
获取对应位置的元素。
indexOf(element)
返回元素在链表中的索引。如果链表中没有该元素就返回-1。
update(position, element)
修改某个位置的元素。
removeAt(position)
从链表的特定位置移除一项。
remove(element)
从链表中移除一项。
isEmpty()
如果链表中不包含任何元素,返回 true,如果链表长度大于 0 则返回 false。
size()
返回链表包含的元素个数,与数组的 length 属性类似。
toString()
由于链表项使用了 Node 类,就需要重写继承自 JavaScript 对象默认的 toString 方法,让其只输出元素的值。
三、单向链表的封装
C语言使用结构体来创建链表与结点;
JavaScript中使用类来创建链表与结点。
创建单向链表类
先创建单向链表类 LinkedList
,添加基本属性,再逐步实现单向链表的常用方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class LinkedList { length = 0;
head = null;
Node = class { data; next = null; constructor(data) { this.data = data; } }; }
|
实现 append()
代码实现
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
| append(data) {
const newNode = new this.Node(data);
if (this.length === 0) { this.head = newNode; } else { let currentNode = this.head;
while (currentNode.next !== null) { currentNode = currentNode.next; }
currentNode.next = newNode; }
this.length++; }
|
过程图解
首先让 currentNode
指向第一个节点。

通过 while
循环使 currentNode
指向最后一个节点,最后通过 currentNode.next = newNode
,让最后一个节点指向新节点 newNode
。

代码测试
1 2 3 4 5 6
| const linkedList = new LinkedList();
linkedList.append("A"); linkedList.append("B"); linkedList.append("C"); console.log(linkedList);
|

实现 toString()
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13
| toString() { let currentNode = this.head; let result = '';
while (currentNode) { result += currentNode.data + ' '; currentNode = currentNode.next; }
return result; }
|
代码测试
1 2
| console.log(linkedList.toString());
|
实现 insert()
代码实现
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
| insert(position, data) {
if (position < 0 || position > this.length) return false;
const newNode = new this.Node(data);
if (position === 0) { newNode.next = this.head;
this.head = newNode; } else {
let currentNode = this.head; let previousNode = null; let index = 0;
while (index++ < position) { previousNode = currentNode; currentNode = currentNode.next; }
newNode.next = currentNode; previousNode.next = newNode; }
this.length++; return newNode; }
|
代码测试
1 2 3 4
| linkedList.insert(0, "123"); linkedList.insert(2, "456"); console.log(linkedList.toString());
|
实现 getData()
获取指定位置(position)的 data。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| getData(position) { if (position < 0 || position >= this.length) return null;
let currentNode = this.head; let index = 0;
while (index++ < position) { currentNode = currentNode.next; } return currentNode.data; }
|
代码测试
1 2 3
| console.log(linkedList.getData(0)); console.log(linkedList.getData(1));
|
实现 indexOf()
indexOf(data) 返回指定 data 的 index,如果没有,返回 -1。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| indexOf(data) {
let currentNode = this.head; let index = 0;
while (currentNode) { if (currentNode.data === data) { return index; } currentNode = currentNode.next; index++; }
return -1; }
|
代码测试
1 2 3
| console.log(linkedList.indexOf("AA")); console.log(linkedList.indexOf("ABC"));
|
实现 update()
update(position, data) 修改指定位置节点的 data。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| update(position, data) { if (position < 0 || position >= this.length) return false;
let currentNode = this.head; let index = 0; while (index++ < position) { currentNode = currentNode.next; }
currentNode.data = data;
return currentNode; }
|
代码测试
1 2 3 4 5
| linkedList.update(0, "12345"); console.log(linkedList.toString()); linkedList.update(1, "54321"); console.log(linkedList.toString());
|
实现 removeAt()
removeAt(position) 删除指定位置的节点。
代码实现
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
| removeAt(position) { if (position < 0 || position >= this.length) return null;
let currentNode = this.head; if (position === 0) { this.head = this.head.next;
} else {
let previousNode = null; let index = 0;
while (index++ < position) { previousNode = currentNode; currentNode = currentNode.next; }
previousNode.next = currentNode.next; }
this.length--;
return currentNode; }
|
代码测试
1 2 3
| linkedList.removeAt(3); console.log(linkedList.toString());
|
实现 remove()
remove(data) 删除指定 data 所在的节点。
代码实现
1 2 3
| remove(data) { this.removeAt(this.indexOf(data)); }
|
代码测试
1 2 3
| linkedList.remove("CC"); console.log(linkedList.toString());
|
实现 isEmpty()
isEmpty() 判断链表是否为空。
代码实现
1 2 3
| isEmpty() { return this.length === 0; }
|
代码测试
1 2
| console.log(linkedList.isEmpty());
|
实现 size()
size() 获取链表的长度。
代码实现
1 2 3
| size() { return this.length; }
|
代码测试
1 2
| console.log(linkedList.size());
|
完整实现
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 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204
| class LinkedList { length = 0;
head = null;
Node = class { data; next = null;
constructor(data) { this.data = data; } };
append(data) { const newNode = new this.Node(data);
if (this.length === 0) { this.head = newNode; } else { let currentNode = this.head;
while (currentNode.next !== null) { currentNode = currentNode.next; }
currentNode.next = newNode; }
this.length++; }
insert(position, data) {
if (position < 0 || position > this.length) return false;
const newNode = new this.Node(data);
if (position === 0) { newNode.next = this.head;
this.head = newNode; } else {
let currentNode = this.head; let previousNode = null; let index = 0;
while (index++ < position) { previousNode = currentNode; currentNode = currentNode.next; }
newNode.next = currentNode; previousNode.next = newNode; }
this.length++; return newNode; }
getData(position) { if (position < 0 || position >= this.length) return null;
let currentNode = this.head; let index = 0;
while (index++ < position) { currentNode = currentNode.next; }
return currentNode.data; }
indexOf(data) { let currentNode = this.head; let index = 0;
while (currentNode) { if (currentNode.data === data) { return index; } currentNode = currentNode.next; index++; }
return -1; }
update(position, data) { if (position < 0 || position >= this.length) return false;
let currentNode = this.head; let index = 0; while (index++ < position) { currentNode = currentNode.next; }
currentNode.data = data;
return currentNode; }
removeAt(position) { if (position < 0 || position >= this.length) return null;
let currentNode = this.head; if (position === 0) { this.head = this.head.next; } else {
let previousNode = null; let index = 0;
while (index++ < position) { previousNode = currentNode; currentNode = currentNode.next; }
previousNode.next = currentNode.next; }
this.length--;
return currentNode; }
remove(data) { this.removeAt(this.indexOf(data)); }
isEmpty() { return this.length === 0; }
size() { return this.length; }
toString() { let currentNode = this.head; let result = "";
while (currentNode) { result += currentNode.data + " "; currentNode = currentNode.next; }
return result; } }
|
Tips:
Please indicate the source and original author when reprinting or quoting this article.