前端新一水算法系列：每日一题Day1：链表入门

链表（Linked List）是数据结构里非常重要、又非常基础的一种结构。它不难，但如果没有人给你讲清楚“为什么需要它”“它和数组有什么不同”，很容易看完概念还是一头雾水。

这篇文章会用生活化比喻 + 逐步拆解的方式，让你真正理解链表到底是什么、为什么存在、怎么使用。

链表是什么？（用生活例子理解）

你可以把链表理解成一串散落在不同地方，但互相“牵着手”的节点。

一个链表由很多“节点（Node）”组成，每个节点有两部分内容：

1. 数据（value）
2. 指向下一个节点的指针（next）

生活化理解：

想象有一队人排队，每个人都用手指指向他前面或后面的那个人，这样你就能沿着“指向”一路找到整条队伍。这就是链表。

即使这些人并不是站在一起（内存不连续），只要指向关系存在，队伍仍然完整。

链表长什么样？

常见的单向链表可以表示为：

其中每个方块都是一个节点：

• value：节点存的数据
• next：指向下一个节点的位置
• 最后为 null，表示链表结束

和数组有什么区别？

1. 内存排列方式不同

• 数组：连续摆放
• 链表：离散存放，通过指针连接

就像：

• 数组 = 排得整整齐齐的一排储物柜
• 链表 = 放在不同位置的箱子，每个箱子里贴着“下一个箱子在哪”

2. 查找 vs 增删

• 数组查找快：可以通过下标直接找到
• 链表增删快：只需修改指针，不涉及大规模移动节点

举例：

想在数组中插入一个元素，后面的所有元素可能要整体移动

链表插入时，只需要改几处指针，其他节点完全不动

因此常见总结：

链表的类型

1. 单向链表（最基础）

每个节点只有一个 next 指针，指向下一个节点。

2. 双向链表

每个节点多一个 prev 指针，能前后移动，使用灵活，但占用更多空间。

3. 循环链表

链表最后一个节点不是指向 null，而是指向第一个节点，形成一个环。

为什么程序里需要链表？

场景一：频繁插入和删除

如：

• LRU 缓存
• 音乐播放器播放列表
• 操作系统任务管理

在数组里频繁插入/删除很低效，但链表能轻松做到。

场景二：内存分散、不连续

链表不需要一块完整连续的空间，非常适合内存碎片化的环境。

链表节点的代码长什么样？

用 JavaScript 举例：

function ListNode(val) {
    this.val = val;
    this.next = null;
}

创建一个链表：

let node1 = new ListNode(1)
let node2 = new ListNode(2)
let node3 = new ListNode(3)

node1.next = node2
node2.next = node3

// node1 就是链表的头节点

链表的基本操作示例

下面用最简单的方式理解链表操作的原理。

1. 遍历链表

let cur = node1
while (cur !== null) {
    console.log(cur.val)
    cur = cur.next
}

你可以把它理解成“顺着指针，一个一个往前走”。

2. 在链表中间插入节点

往 [2] 后面插入一个 [99]

1 -> 2 -> 3

变成：

1 -> 2 -> 99 -> 3

只需要改两个指针：

let newNode = new ListNode(99)

newNode.next = node2.next
node2.next = newNode

3. 删除节点

删除节点 [2]：

1 -> 2 -> 3

删除后：

1 ------> 3

只需修改：

node1.next = node2.next

链表的缺点

虽然链表增删强大，但它也有明显弱点：

1. 不支持随机访问

不能直接跳到第 k 个节点，必须从头慢慢往后找。

2. 额外的指针开销

每个节点都要多存一个 next（或 prev）

3. 使用不如数组直观

总结

链表的核心思想：

1. 由节点组成，每个节点记住下一个节点的位置
2. 不需要连续内存
3. 适合频繁插入删除
4. 不适合随机访问

用一句话记住链表：

链表是一种“靠指针连起来的散落节点”的结构，让你能快速插入、快速删除。

前端新一水版权所有，侵权必究！