usehook - 前端码易

链表

链表是由多个节点共同组成的一组线性数据结构。每个节点都包含一个数据域和一个指针域，数据域用于存储数据，指针域用于存储下一个节点的地址。

1class Node {
2  value: number
3  next: Node | null
4}

在内存的存储上，链表并不关注内存空间是否连续，而是通过相同类型的指针将多个节点串联在一起。因此，和数组相比

链表访问一个节点，需要从链表的头部开始，依次遍历，时间复杂度为 $O(n)$ ，访问效率比数组慢很多
数组不需要额外存储一个指针，因此，在内存的存储上，链表比数组更耗费内存
链表的插入和删除操作，只需要修改指针的指向，时间复杂度为 $O(1)$ ，而数组的插入和删除操作，需要移动大量的元素，时间复杂度为 $O(n)$ ，因此，链表的元素操作比数组更高效
当数据量很大时，内存空间很难提供比较充裕的连续内存空间，这种情况下，链表就会更有优势

定义链表结构

和数组不同，我们并不需要完整的定义链表结构，只需要定义链表的首节点、以及链表节点的类型即可。

1class Node {
2  value: number
3  next: Node | null
4} 
5
6const linkedList = new Node(1, null)

在后续的操作过程中，如果有新的节点加入，只需要将新节点的 next 指针指向当前的节点即可。

1const newNode = new Node(2, null)
2linkedList.next = newNode

我们也可以再定义一个变量，用于记录链表的尾节点

1const node = new Node(2, null)
2
3// 头节点
4const head = node
5// 尾节点
6const tail = node

在末尾插入一个节点时

1// 将新节点插入到尾节点后面
2const newNode = new Node(3, null)
3tail.next = newNode
4// 更新尾节点
5tail = newNode

用老的尾节点的 next 指针，指向新的节点，表示新的节点插入到链表的末尾

然后，我们还要更新尾节点的指针，指向新的尾节点

注意观察 tail 的变化。链表在写法上是最简单的数据结构，但是，由于过于灵活，因此，代码写出来之后，理解起来会比较绕，新手朋友很难快速的理解链表的各个指针变来变去的到底在干啥，因此，学习链表时要稍微把速度放慢一点，结合图例慢慢消化

访问链表中的第 n 个节点

由于链表不是连续的内存结构，因此，我们不能直接用下标来访问链表中的元素。而是需要从头节点开始，依次遍历，直到找到第 n 个节点。

10function 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}

时间复杂度为 $O(n)$ ，因为需要遍历链表中的每个节点，直到找到第 n 个节点。所以链表的访问效率比数组低很多。

在链表中插入一个节点

由于我们只定义了头结点和尾节点的指针，因此，如果在中间插入一个节点，需要先找到插入的位置，然后修改指针的指向。

10function 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  const next = current.next
16  current.next = newNode
17  newNode.next = next
18  
19  return head
20}

图例演示如下

在链表中删除一个节点

对于链表而言，删除节点的操作比较好理解。例如，我们删除给定节点的下一个节点，只需要将给定节点的 next 指针，指向给定节点的下一个节点的下一个节点即可。

10function 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}

但是有的时候，我们很难找到要删除的节点是哪一个。例如，我想要删除给定节点的上一个节点。此时就需要从头部开始遍历，找到给定节点的前一个节点。所以成本很高，这个时候，我们可以构建一个双向链表，这样就可以从任意一个节点，快速找到前一个节点和后一个节点。

10function 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}

一定要注意指针的变动。反复体会。链表是一个理解起来比较容易的概念，但是在代码的表现上理解起来会很困难，因为指针的变动可读性本身就比较差。所以，学习的时候一定要速度放慢，理解清楚了再往下走。

练习题：合并两个有序链表

原题地址：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
13function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
14    
15};

题目解析

总结

链表的基础知识比较少，我们在后续的学习中，还会基于链表实现栈、队列等数据结构，后续的每日一题中，还会基于链表解决更多的难题。

接下来还会学习循环链表、双向链表、双向循环链表等。

1、数组

3、环形链表

专栏首页

到顶

专栏目录