2.链表 | OneYoung's Blog

链表（Linked List）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。

引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

1.常用操作

/* 链表节点类 */
class ListNode {
  constructor(val, next) {
    this.val = (val === undefined ? 0 : val)       // 节点值
    this.next = (next === undefined ? null : next) // 指向下一节点的引用
  }
}

1-1.初始化

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
const n0 = new ListNode(1)
const n1 = new ListNode(3)
const n2 = new ListNode(2)
const n3 = new ListNode(5)
const n4 = new ListNode(4)
// 构建节点之间的引用
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

1-2.插入

/* 在链表的节点 n0 之后插入节点 P */
function insert(n0, P) {
  const n1 = n0.next
  P.next = n1
  n0.next = P
}

1-3.删除

/* 删除链表的节点 n0 之后的首个节点 */
function remove(n0) {
  if (!n0.next) return
  // n0 -> P -> n1
  const P = n0.next
  const n1 = P.next
  n0.next = n1
}

1-4.访问

/* 访问链表中索引为 index 的节点 */
function access(head, index) {
  for (let i = 0; i < index; i++) {
    if (!head) {
      return null
    }
    head = head.next
  }
  return head
}

1-5.查找

/* 在链表中查找值为 target 的首个节点 */
function find(head, target) {
  let index = 0
  while (head !== null) {
    if (head.val === target) {
      return index
    }
    head = head.next
    index += 1
  }
  return -1
}

2.优缺点

数组与链表采用两种相反的存储策略，因此各种性质和操作效率也呈现对立的特点。

	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活扩展
内存效率	元素占用内存少、但可能浪费空间	元素占用内存多
访问元素	`O(1)`	`O(n)`
添加元素	`O(n)`	`O(1)`
删除元素	`O(n)`	`O(1)`

3.常见链表类型

常见的链表类型包括三种：

单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。
环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间

4.应用

单向链表通常用于实现栈、队列、哈希表和图等数据结构。

栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。

双向链表常用于需要快速查找前一个和后一个元素的场景。

高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。

时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。

1.常用操作 ​

1-1.初始化 ​

1-2.插入 ​

1-3.删除 ​

1-4.访问 ​

1-5.查找 ​

2.优缺点 ​

3.常见链表类型 ​

4.应用 ​