链表
链表是由多个节点共同组成的一组线性数据结构。每个节点都包含一个数据域和一个指针域，数据域用于存储数据，指针域用于存储下一个节点的地址。
1
class
Node
{
2
value
:
number
3
next
:
Node
|
null
4
}
在内存的存储上，链表是不连续的内存空间，而是通过相同类型的指针将多个节点串联在一起。因此，和数组相比
- 链表访问一个节点，需要从链表的头部开始，依次遍历，时间复杂度为 ，访问效率比数组慢很多
- 数组不需要额外存储一个指针，因此，在内存的存储上，链表比数组更耗费内存
- 链表的插入和删除操作，只需要修改指针的指向，时间复杂度为 ，而数组的插入和删除操作，需要移动大量的元素，时间复杂度为 ，因此，链表的元素操作比数组更高效
- 当数据量很大时，内存空间很难提供比较充裕的连续内存空间，这种情况下，链表就会更有优势
定义链表结构
和数组不同，我们并不需要完整的定义链表结构，只需要定义链表的首节点、以及链表节点的类型即可。
1
class
Node
{
2
value
:
number
3
next
:
Node
|
null
4
}
5
6
const
linkedList
= new
Node
(
1
,
null
)
在后续的操作过程中，如果有新的节点加入，只需要将新节点的 next
指针指向当前的节点即可。
1
const
newNode
= new
Node
(
2
,
null
)
2
linkedList.next
=
newNode
我们也可以再定义一个变量，用于记录链表的尾节点
1
const
node
= new
Node
(
2
,
null
)
2
3
// 头节点
4
const
head
=
node
5
// 尾节点
6
const
tail
=
node
在末尾插入一个节点时
1
// 将新节点插入到尾节点后面
2
const
newNode
= new
Node
(
3
,
null
)
3
tail.next
=
newNode
4
// 更新尾节点
5
tail
=
newNode
用老的尾节点的 next
指针，指向新的节点，表示新的节点插入到链表的末尾
然后，我们还要更新尾节点的指针，指向新的尾节点
注意观察 tail
的变化。链表在写法上是最简单的数据结构，但是，由于过于灵活，因此，代码写出来之后，理解起来会比较绕，新手朋友很难快速的理解链表的各个指针变来变去的到底在干啥，因此，学习链表时要
稍微把速度放慢一点，结合图例慢慢消化
访问链表中的第 n 个节点
由于链表不是连续的内存结构，因此，我们不能直接用下标来访问链表中的元素。而是需要从头节点开始，依次遍历，直到找到第 n 个节点。
10
function
getNode
(
head
:
Node
,
n
:
number
) {
20
let
current
=
head
30
if
(n
===
0
) {
40
return
current
50
}
60
for
(
let
i
=
1
; i
<
n; i
++
) {
70
if
(
!
current) {
80
return
null
90
}
10
current
=
current.next
11
}
12
return
current
13
}
时间复杂度为 ，因为需要遍历链表中的每个节点，直到找到第 n 个节点。所以链表的访问效率比数组低很多。
在链表中插入一个节点
由于我们只定义了头结点和尾节点的指针，因此，如果在中间插入一个节点，需要先找到插入的位置，然后修改指针的指向。
10
function
insertNode
(
head
:
Node
,
n
:
number
,
value
:
number
) {
20
const
newNode
= new
Node
(value,
null
)
30
40
if
(n
===
0
) {
50
newNode.next
=
head
60
head
=
newNode
70
return
head
80
}
90
10
let
current
=
head
11
12
for
(
let
i
=
1
; i
<
n
-
1
; i
++
) {
13
current
=
current.next
14
}
15
16
current.next
=
newNode
17
newNode.next
=
current.next
18
19
return
head
20
}
图例演示如下
在链表中删除一个节点
对于链表而言，删除节点的操作比较好理解。例如，我们删除给定节点的下一个节点，只需要将给定节点的 next
指针，指向给定节点的下一个节点的下一个节点即可。
10
function
deleteNode
(
current
:
Node
) {
20
if
(
!
current.next) {
30
return
null
40
}
50
60
// 获取要删除的节点
70
const
p
=
current.next
80
90
// 将当前节点的 next 指针，指向要删除的节点的下一个节点
10
current.next
=
p.next
11
12
// 释放要删除的节点
13
p.next
=
null
14
15
return
p
16
}
但是有的时候，我们很难找到要删除的节点是哪一个。例如，我想要删除给定节点的上一个节点。此时就需要从头部开始遍历，找到给定节点的前一个节点。所以成本很高，这个时候，我们可以构建一个双向链表，这样就可以从任意一个节点，快速找到前一个节点和后一个节点。
10
function
deletePrevNode
(
current
:
Node
) {
20
if
(
!
current.prev) {
30
return
null
40
}
50
60
// 获取要删除的节点
70
const
p
=
current.prev
80
// p 的前一个节点
90
const
prev
=
p.prev
10
11
// 将当前节点的 prev 指针，指向要删除的节点的上一个节点
12
current.prev
=
prev
13
// 将 p 的前一个节点的 next 指针，指向当前节点
14
prev.next
=
current
15
16
// 释放要删除的节点
17
p.prev
=
null
18
p.next
=
null
19
20
return
p
21
}
一定要注意指针的变动。反复体会。链表是一个理解起来比较容易的概念，但是在代码的表现上理解起来会很困难，因为指针的变动可读性本身就比较差。所以，学习的时候一定要速度放慢，理解清楚了再往下走。
练习题：合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
1
输入：l1
=
[
1
,
2
,
4
], l2
=
[
1
,
3
,
4
]
2
输出：[
1
,
1
,
2
,
3
,
4
,
4
]
10
/**
20
* Definition for singly-linked list.
30
* class ListNode {
40
* val: number
50
* next: ListNode | null
60
* constructor(val?: number, next?: ListNode | null) {
70
* this.val = (val===undefined ? 0 : val)
80
* this.next = (next===undefined ? null : next)
90
* }
10
* }
11
*/
12
13
function
mergeTwoLists
(
list1
:
ListNode
|
null
,
list2
:
ListNode
|
null
)
:
ListNode
|
null
{
14
15
};
总结
链表的基础知识比较少，我们在后续的学习中，还会基于链表实现栈、队列等数据结构，后续的每日一题中，还会基于链表解决更多的难题。
接下来还会学习循环链表、双向链表、双向循环链表等。