一、 什么是链表？

链表（Linked List）是一种非连续、非顺序的线性数据结构。与数组在内存中连续存储不同，链表的节点在物理存储上可以分散在内存各处。它的逻辑顺序是通过节点中的“指针”链接来实现的。每个节点包含两部分：

• 数据域：存储实际的数据元素。
• 指针域：存储下一个（或上一个）节点的内存地址。

二、 链表的常见分类

根据指针的数量和首尾连接方式，链表主要分为以下三类：

1. 单链表：每个节点只有一个指向下一个节点的指针（next），只能从头向尾单向遍历。尾节点的 next 指向 null。
2. 双向链表：每个节点包含两个指针，分别指向前一个节点（prev）和后一个节点（next），支持双向遍历。
3. 循环链表：尾节点的 next 指向头节点，形成一个闭环。可以从任意节点出发遍历所有节点。

三、 链表的核心术语

• 头结点 (dummy / 虚拟头结点)：不存储有效数据，作为链表的开头。使用它可以简化头部的增删操作，使头部和中间节点的操作逻辑完全统一。
• 头指针 (head)：指向链表中第一个有效节点的指针。
• 尾结点：next 指针为 null（单链表）或指向头节点（循环链表）的节点。

四、 链表 vs 数组

• 优点：插入和删除元素效率高（找到位置后时间复杂度为 O(1)），无需提前分配连续大块内存，支持动态扩容。
• 缺点：不支持随机访问，查找元素必须从头遍历（时间复杂度为 O(n)）；每个节点需要额外存储指针，空间开销相对较大。

五、 基础操作与实战技巧

1. 遍历列表：必须使用临时指针（如 cur = head）进行遍历，切忌直接使用 head 指针移动，否则会丢失链表起点。
2. 删除节点：单链表删除节点时，必须找到待删节点的“前驱节点”，通过修改前驱节点的 next 指针来跳过目标节点。
3. 快慢指针（双指针）思想：这是链表算法中的核心技巧。慢指针一次走一步，快指针一次走两步。常用于寻找链表中点、判断链表是否有环以及寻找环的入口节点。

六、 典型应用场景

• 实现栈与队列：利用链表头部插入/删除的高效性，轻松实现后进先出（LIFO）的栈或先进先出（FIFO）的队列。
• 浏览器前进/后退：利用双向链表实现页面历史记录的灵活跳转。
• 文本编辑器：在文本中频繁插入、删除字符时，链表比数组更具优势。
• 操作系统：用于进程调度队列、内存管理等动态数据场景。

七、题型

1.203.移除链表元素

   题解

2.707.设计链表

 题解