2.1 链表基础 --- 1. 链表简介1.1 链表定义链表（Linked List）：一种线性表数据结构，通过一组任意（可连续或不连续）的存储单元，存储同类型数据。
简而言之，链表 是线性表的链式存储实现。
以单链表为例，其结构如下图：
链表如上图所示，链表通过指针将一组任意的存储单元串联起来。每个数据元素及其所在的存储单元构成一个「链节点」。为了将所有节点连接成链，每个链节点除了存放数据元素本身，还需要额外存储一个指向其直接后继节点的指针，称为「后继指针 nextnextnext」。
在链表结构中，数据元素之间的逻辑顺序由指针维护。虽然逻辑上相邻的数据元素在物理内存中可以相邻，也可以完全不相邻，因此链表在物理存储上的分布是非连续、随机的。
链表的优缺点如下：
优点：链表无需预先分配存储空间，按需动态申请，能够有效避免空间浪费；在插入、删除等操作上，链表通常比数组更高效，尤其是在需要频繁修改数据结构时表现突出。缺点：链表除了存储数据本身外，还需额外存储指针信息，因此整体空间开销大于数组；同时，链表不支持随机访问，查找元素时需要从头遍历，效率较低。下面介绍除单链表外的其他链表类型。
1.2 双向链表双向链表（Doubly Linked List）：链表的一种，也称为双链表。每个节点包含两个指针，分别指向其直接前驱和直接后继节点。
双向链表的特点：可以从任意节点高效地访问其前驱和后继节点，支持双向遍历，插入和删除操作更加灵活。双向链表1.3 循环链表循环链表（Circular Linked List）：一种特殊的链表结构，其最后一个节点的指针指向头节点，从而使整个链表首尾相连，形成一个闭环。
循环链表的特点：无论从哪个节点出发，都可以遍历到链表中的任意节点，实现了节点间的循环访问。循环链表下面我们将以最基础的「单链表」为例，详细讲解链表的基本操作。
2. 链表的基本操作在数据结构中，常见的基本操作包括增、删、改、查四类，链表的操作同样主要围绕这四个方面展开。下面我们详细介绍链表的基本操作。
2.1 链表的结构定义链表由若干链节点通过 nextnextnext 指针依次连接而成。通常我们会先定义一个简单的「链节点类」，再基于此实现完整的「链表类」。
链节点类（ListNode）：包含成员变量 valvalval（存储数据元素的值）和 nextnextnext（指向下一个节点的指针）。
链表类（LinkedList）：包含一个链节点变量 headheadhead，用于表示链表的头节点。
创建空链表时，只需将头节点 headheadhead 设为「空指针」。在 Python 中可用 NoneNoneNone 表示，其他语言中常用 NULLNULLNULL、nilnilnil、000 等。
链节点与链表结构的代码实现如下：
# 链节点类
class ListNode:
def __init__(self, val=0, next=None):
self.val = val # 节点的值
self.next = next # 指向下一个节点
class LinkedList:
def __init__(self):
self.head = None # 链表头指针，初始为 None2.2 创建链表创建链表：根据给定的线性表数据，依次生成链表节点，并将它们顺序连接起来，构成完整的链表。
具体步骤如下：
取出线性表的第 111 个元素，创建链表头节点。依次遍历剩余元素，每获取一个数据元素，就新建一个节点，并将其连接到当前链表的尾部。所有元素插入完成后，返回头节点。创建链表 的实现代码如下：
# 根据 data 列表初始化一个新链表
def create(self, data):
if not data:
# 如果输入数据为空，直接返回，不创建链表
return
# 创建头节点，并将 head 指向头节点
self.head = ListNode(data[0])
cur = self.head # cur 用于指向当前链表的尾节点
# 依次遍历 data 中剩余的元素，逐个创建新节点并连接到链表尾部
for i in range(1, len(data)):
node = ListNode(data[i]) # 创建新节点
cur.next = node # 将新节点连接到当前尾节点
cur = cur.next # cur 指向新的尾节点，准备连接下一个节点「创建链表」的操作需要遍历所有数据元素，时间复杂度为 O(n)O(n)O(n)，其中 nnn 为线性表的长度。
2.3 链表长度链表长度：通过一个指针变量 curcurcur 沿着链表的 nextnextnext 指针逐个遍历节点，并用计数器 countcountcount 统计节点数量，最终得到链表长度。
具体步骤如下：
令指针 curcurcur 指向链表头节点（第 111 个节点）。沿着 nextnextnext 指针遍历链表，每访问一个节点，计数器 countcountcount 加 111。当 curcurcur 变为 NoneNoneNone（即遍历到链表末尾）时，遍历结束，此时 countcountcount 即为链表长度，返回该值。「求链表长度」 的实现代码如下：
# 获取线性链表长度
def length(self):
count = 0 # 初始化计数器，记录节点个数
cur = self.head # 从链表头节点开始遍历
while cur: # 只要当前节点不为 None，就继续遍历
count += 1 # 每遍历到一个节点，计数器加 1
cur = cur.next # 指针后移，指向下一个节点
return count # 返回计数器的值，即链表长度「求链表长度」的操作需要遍历链表的所有节点，操作次数为 nnn，因此时间复杂度为 O(n)O(n)O(n)，其中 nnn 为链表长度。
2.4 查找节点链表中查找值为 valvalval 的节点：从头节点 headheadhead 开始，依次遍历链表，查找值等于 valvalval 的节点。如果找到，返回该节点；否则返回 NoneNoneNone。
具体步骤如下：
定义指针变量 curcurcur，初始指向链表的头节点。沿着链表的 nextnextnext 指针依次遍历每个节点： 如果当前节点 curcurcur 的值等于 valvalval，则查找成功，返回该节点。否则，curcurcur 指向下一个节点，继续查找。如果遍历完整个链表仍未找到，说明链表中不存在值为 valvalval 的节点，返回 NoneNoneNone。「链表中查找值为 valvalval 的节点」 的实现代码如下：
# 链表中查找值为 val 的节点
def find(self, val):
cur = self.head # 从链表头节点开始遍历
while cur: # 只要当前节点不为 None，就继续遍历
if val == cur.val: # 如果当前节点的值等于目标值，查找成功
return cur # 返回当前节点
cur = cur.next # 指针后移，指向下一个节点
# 遍历完整个链表都没有找到目标值，返回 None
return None「链表中查找值为 valvalval 的节点」需要遍历链表的所有节点，因此其时间复杂度为 O(n)O(n)O(n)，其中 nnn 表示链表的长度。
2.5 插入节点插入节点：在链表的第 iii 个位置前插入一个值为 valvalval 的新节点。具体步骤如下：
定义指针变量 curcurcur，初始指向链表头节点，同时定义计数器 countcountcount，初始值为 000。沿着链表的 nextnextnext 指针遍历，curcurcur 每指向一个节点，countcountcount 加 111。当 countcountcount 等于 index−1index - 1index−1 时，curcurcur 正好指向第 index−1index - 1index−1 个节点（即新节点的前驱节点），此时停止遍历。创建一个新节点 nodenodenode，其值为 valvalval。将 node.nextnode.nextnode.next 指向 cur.nextcur.nextcur.next，即新节点的后继为原本的第 indexindexindex 个节点。将 cur.nextcur.nextcur.next 指向 nodenodenode，完成插入操作。注意：如果 index=1index = 1index=1，即在头节点前插入，需要特殊处理（如使用虚拟头节点或单独判断）。
插入节点「插入节点」 的实现代码如下：
# 插入节点
def insertInside(self, index, val):
# 头部插入（index == 1）
if index == 1:
node = ListNode(val)
node.next = self.head
self.head = node
return
count = 0
cur = self.head
# 遍历链表，找到第 index - 1 个节点（即新节点的前驱节点）
while cur and count < index - 1:
cur = cur.next
count += 1
# 如果遍历到链表末尾还没找到前驱节点，说明 index 越界，插入失败
if not cur:
return 'Error'
node = ListNode(val)
# 尾部插入（index 指向最后一个节点的下一个位置）
if cur.next is None:
cur.next = node
else:
node.next = cur.next
cur.next = node「插入节点」操作需要将指针 curcurcur 从链表头部遍历到第 iii 个节点的前一个位置，平均时间复杂度为 O(n)O(n)O(n)，因此整体的时间复杂度为 O(n)O(n)O(n)。
2.6 改变节点将链表中第 iii 个节点的值修改为 valvalval：只需遍历到第 iii 个节点，然后直接修改该节点的值。具体步骤如下：
定义指针变量 curcurcur 指向链表头节点，并设置计数器 countcountcount，初始为 000。沿着 nextnextnext 指针遍历链表，每遍历一个节点，countcountcount 加 111。当 countcountcount 等于 indexindexindex 时，curcurcur 正好指向第 iii 个节点，停止遍历。直接将 curcurcur 的值设为 valvalval。「将链表中第 iii 个节点的值修改为 valvalval」 的实现代码如下：
# 改变元素：将链表中第 i 个元素值改为 val
def change(self, index, val):
# 初始化计数器 count 和指针 cur，cur 指向链表头节点
count = 0
cur = self.head
# 遍历链表，直到找到第 index 个节点
while cur and count < index:
count += 1
cur = cur.next
# 如果 cur 为空，说明 index 越界，返回错误
if not cur:
return 'Error'
# 修改第 index 个节点的值为 val
cur.val = val要将链表中第 iii 个节点的值修改为 valvalval，需要从链表头节点出发，遍历到第 iii 个节点，然后进行赋值操作。由于遍历链表的时间复杂度为 O(n)O(n)O(n)，因此该操作的整体时间复杂度为 O(n)O(n)O(n)。
2.7 删除元素删除元素：删除链表中第 iii 个节点。
具体步骤如下：
使用指针变量 curcurcur 遍历至第 i−1i - 1i−1 个节点（即待删除节点的前驱）。将 curcurcur 的 nextnextnext 指针指向第 iii 个节点的下一个节点，从而跳过并移除第 iii 个节点。删除元素「删除元素」 的实现代码如下：
# 链表删除元素
def removeInside(self, index):
# 初始化计数器 count 和指针 cur，cur 指向链表头节点
count = 0
cur = self.head
# 遍历链表，cur 移动到第 index - 1 个节点（即待删除节点的前驱）
while cur.next and count < index - 1:
count += 1
cur = cur.next
# 如果 cur 为空，说明 index 越界，返回错误
if not cur:
return 'Error'
# del_node 指向待删除的节点
del_node = cur.next
# 将 cur 的 next 指针指向 del_node 的下一个节点，实现删除
cur.next = del_node.next「删除元素」操作需要将指针 curcurcur 从链表头节点遍历至第 iii 个节点的前一个节点，因此其时间复杂度为 O(n)O(n)O(n)。
3. 总结3.1 链表特点链表是一种链式存储的线性表数据结构，具有以下核心特征：
存储方式：通过指针连接任意存储单元，物理存储非连续节点结构：每个节点包含数据域和指针域访问方式：只能顺序访问，不支持随机访问3.2 链表类型类型特点适用场景单链表每个节点只有一个后继指针基础链表操作双向链表每个节点有前驱和后继指针需要双向遍历循环链表尾节点指向头节点形成环循环访问场景3.3 基本操作复杂度操作时间复杂度空间复杂度说明查找O(n)O(n)O(n)O(1)O(1)O(1)需要遍历到目标位置插入O(n)O(n)O(n)O(1)O(1)O(1)找到插入位置后操作简单删除O(n)O(n)O(n)O(1)O(1)O(1)找到删除位置后操作简单修改O(n)O(n)O(n)O(1)O(1)O(1)需要遍历到目标位置3.4 链表 vs 数组特性链表数组存储方式链式存储，非连续顺序存储，连续随机访问不支持，O(n)O(n)O(n)支持，O(1)O(1)O(1)插入删除高效，O(1)O(1)O(1)（已知位置）需要移动元素，O(n)O(n)O(n)空间开销额外指针开销无额外开销内存分配动态分配静态分配3.5 应用场景频繁插入删除：链表在插入删除操作上比数组更高效动态内存管理：适合内存大小不确定的场景实现其他数据结构：栈、队列、哈希表等的基础算法优化：某些算法中链表结构能提供更好的性能练习题目0707. 设计链表
0206. 反转链表
0203. 移除链表元素
0328. 奇偶链表
0234. 回文链表
0138. 随机链表的复制
链表基础题目列表
参考资料【文章】链表理论基础 - 代码随想录【文章】什么是链表 - 漫画算法 - 小灰的算法之旅 - 力扣【文章】链表 - 数据结构与算法之美 - 极客时间【书籍】数据结构教程 第 2 版 - 唐发根 著【书籍】数据结构与算法 Python 语言描述 - 裘宗燕 著