链表
链表
介绍
链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表与数组不同，它的元素在内存中不是连续存储的。
链表的类型
- 单向链表：每个节点只包含一个指向下一个节点的指针。
- 双向链表：每个节点包含两个指针，分别指向前一个和下一个节点。
- 循环链表：最后一个节点的指针指向链表的第一个节点，形成一个闭环，根据节点类型，也会分为单向和双向。
节点类型
- 数据域：用来保存当前节点元素的数据。
- 指针域：用来保存下一个节点的位置地址，根据链表类型不同，指针域中包含的指针数量也不同。
链表的特点
- 动态大小：链表的大小可以在运行时动态改变。
- 非连续内存：链表的节点不需要在内存中连续存储。
- 插入和删除高效：在链表中的任意位置插入或删除节点，只需调整指针，无需移动其他元素。
实现代码
单链表节点定义
节点类中包含数据域和指针域两部分，分别用来保存数据和下一个节点的位置。
python
# 定义结点类，包含数据域和指针域
class ListNode:
def __init__(self, value=0, next=None):
# 数据域
self.value = value
# 指针域
self.next = next
java
public class ListNode {
int value; // 数据域
ListNode next; // 指针域
// 构造函数，初始化节点
public ListNode(int value) {
this.value = value;
this.next = null; // 默认指向 null
}
// 可选的构造函数，允许指定下一个节点
public ListNode(int value, ListNode next) {
this.value = value;
this.next = next; // 指向下一个节点
}
}
单向链表实现
链表类定义
在定义单向链表时，定义属性 head 用来保存链表头节点地址，方便后续链表操作。
python
class LinkedList:
# 创建链表，内容为空
def __init__(self):
self.head = None
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int value; // 节点值
Node next;
Node(int value) {
this.value = value;
this.next = null;
}
}
// 创建链表，内容为空
public LinkedList() {
this.head = null; // 初始化头节点为空
}
}
添加节点
向链表中添加节点有两种方式：
- 向链表尾部追加新节点：优点是容易理解，缺点是当链表中节点较多时，每次添加新节点比较耗时。
- 向链表头部插入新节点：优点是添加效率高，缺点是操作相对复杂。
python
# 在链表尾部追加新节点
# 缺点：链表中节点较多时，插入速度慢
def append(self, value):
"""尾部添加节点"""
# 如果链表为空，让head指向新节点
if not self.head:
self.head = ListNode(value)
else:
# 不为空，定义指针到链表头
current = self.head
# 移动到链表尾
while current.next:
current = current.next
# 将新节点连接到最后一个节点后
current.next = ListNode(value)
# 在链表头部添加新节点
def prepend(self, value):
"""头部添加节点"""
new_node = ListNode(value, self.head)
self.head = new_node
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int value; // 节点值
Node next;
Node(int value) {
this.value = value;
this.next = null;
}
}
// 尾部添加节点
public void append(int value) {
// 如果链表为空，让 head 指向新节点
if (this.head == null) {
this.head = new Node(value);
} else {
// 不为空，定义指针到链表头
Node current = this.head;
// 移动到链表尾
while (current.next != null) {
current = current.next;
}
// 将新节点连接到最后一个节点后
current.next = new Node(value);
}
}
// 头部添加节点
public void prepend(int value) {
Node newNode = new Node(value);
newNode.next = this.head; // 将新节点的下一个指针指向当前头节点
this.head = newNode; // 更新头节点
}
}
显示链表
将所有链表中节点元素值以字符串形式保存到列表中，然后以 -> 连接元素输出
python
# 显示链表
def display(self):
"""打印链表内容"""
values = []
current = self.head
while current:
# 将节点中的数据以字符串形式保存到列表中
values.append(str(current.value))
current = current.next
# 使用 '->' 连接列表中的数据
print(" -> ".join(values))
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int value; // 节点值
Node next;
Node(int value) {
this.value = value;
this.next = null;
}
}
// 打印链表内容
public void display() {
StringBuilder values = new StringBuilder(); // 使用 StringBuilder 来构建输出字符串
Node current = this.head;
while (current != null) {
// 将节点中的数据以字符串形式添加到 StringBuilder 中
values.append(current.value);
current = current.next;
if (current != null) { // 只有在当前节点不为 null 时才添加箭头
values.append(" -> ");
}
}
// 打印链表的内容
System.out.println(values.toString());
}
}
查找节点
遍历链表中的节点，如果节点值与查找值相同，返回当前节点，找不到返回 None。
python
# 查找节点
def find(self, value):
"""查找特定值的节点"""
current = self.head
while current:
if current.value == value:
return current
current = current.next
return None
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int value; // 节点值
Node next;
Node(int value) {
this.value = value;
this.next = null;
}
}
// 查找特定值的节点
public Node find(int value) {
Node current = this.head;
while (current != null) {
if (current.value == value) {
return current; // 找到节点，返回
}
current = current.next; // 移动到下一个节点
}
return null; // 未找到，返回 null
}
}
删除节点
python
# 删除指定值的节点
def delete(self, value):
"""删除特定值的节点"""
# 将指针指向链表头
current = self.head
# 设置跟随指针
prev = None
# 如果当前指针不为空且当前节点值不是删除值
while current and current.value != value:
# 移动指针到下一个结点
prev = current
current = current.next
# 如果跟随指针不为空，将跟随指针所在节点的指针域指向被删除节点指针域指向的节点，也就是删除节点
if prev:
# 非头节点删除情况
if current:
prev.next = current.next
else:
# 删除值不在列表中的情况
print(f"值为 {value} 的节点不存在")
return
else: # 如果要删除的是头节点
self.head = current.next
# 将删除节点从链表中断开并删除
current.next = None
del current
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int value; // 节点值
Node next;
Node(int value) {
this.value = value;
this.next = null;
}
}
// 删除特定值的节点
public void delete(int value) {
// 将指针指向链表头
Node current = this.head;
Node prev = null;
// 如果当前指针不为空且当前节点值不是删除值
while (current != null && current.value != value) {
// 移动指针到下一个结点
prev = current;
current = current.next;
}
// 如果跟随指针不为空，将跟随指针所在节点的指针域指向被删除节点指针域指向的节点
if (prev != null) {
// 非头节点删除情况
if (current != null) {
prev.next = current.next; // 跳过被删除的节点
} else {
// 删除值不在列表中的情况
System.out.println("值为 " + value + " 的节点不存在");
return;
}
} else { // 如果要删除的是头节点
this.head = current.next;
}
// 将删除节点从链表中断开并删除
if (current != null) {
current.next = null; // 断开与后续节点的连接
}
}
}
链表排序（了解）
此处实现的链表排序使用了冒泡排序的算法，在排序过程中，链表中所有节点的位置都没有变化，只是交换了节点中保存的数据。
还可以使用调整节点位置的方式对链表进行排序，比如使用头节点插入法。
python
# 排序链表
def sort(self):
"""对链表进行排序（冒泡排序）"""
# 如果为空直接返回
if self.head is None:
return
# 状态变量，如果排序后再执行，不会再次执行排序代码
sorted = False
while not sorted:
# 在每次外层循环开始时，将sorted设置为True，假设当前链表是已排序的。
sorted = True
# 设置当前节点为链表的头节点，开始遍历链表。
current = self.head
# 内层循环，只要当前节点的下一个节点存在，就继续遍历。
while current.next:
# 比较当前节点和下一个节点的值，如果当前节点的值大于下一个节点的值，说明需要交换。
if current.value > current.next.value:
# 交换当前节点和下一个节点的值。
current.value, current.next.value = current.next.value, current.value
# 由于发生了交换，说明链表当前不是已排序状态，将sorted设置为False。
sorted = False
# 将当前节点移动到下一个节点，继续内层循环的遍历。
current = current.next
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int value; // 节点值
Node next;
Node(int value) {
this.value = value;
this.next = null;
}
}
// 对链表进行排序（冒泡排序）
public void sort() {
// 如果链表为空，直接返回
if (this.head == null) {
return;
}
boolean sorted = false;
while (!sorted) {
// 在每次外层循环开始时，将 sorted 设置为 true，假设当前链表是已排序的
sorted = true;
Node current = this.head;
// 内层循环，只要当前节点的下一个节点存在，就继续遍历
while (current.next != null) {
// 比较当前节点和下一个节点的值，如果当前节点的值大于下一个节点的值，说明需要交换
if (current.value > current.next.value) {
// 交换当前节点和下一个节点的值
int temp = current.value;
current.value = current.next.value;
current.next.value = temp;
// 由于发生了交换，说明链表当前不是已排序状态，将 sorted 设置为 false
sorted = false;
}
// 将当前节点移动到下一个节点，继续内层循环的遍历
current = current.next;
}
}
}
}
链表逆序（了解）
链表逆序是将链表中所有节点顺序进行反转。
python
def reverse(self):
"""逆序链表"""
prev = None
current = self.head
# 循环直到链表尾部
while current:
# 保存 current.next 到 next_node，这样在修改 current.next 后不会丢失对下一个节点的引用
next_node = current.next
# 这一步是逆序的关键，它将当前节点的指针反向指向前一个节点。
current.next = prev
# 将当前节点作为下一个循环的前一个节点
prev = current
# 将 next_node 赋值给 current，继续遍历链表到下一个节点
current = next_node
# 循环结束，此时 prev 指向原链表的最后一个节点，也就是逆序后的第一个节点。
# 将 self.head 更新为 prev，完成链表的逆序
self.head = prev
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// 逆序链表
public void reverse() {
Node prev = null;
Node current = this.head;
// 循环直到链表尾部
while (current != null) {
// 保存 current.next 到 nextNode，确保在修改 current.next 后不会丢失对下一个节点的引用
Node nextNode = current.next;
// 将当前节点的指针反向指向前一个节点
current.next = prev;
// 将当前节点作为下一个循环的前一个节点
prev = current;
// 将 nextNode 赋值给 current，继续遍历链表到下一个节点
current = nextNode;
}
// 循环结束，此时 prev 指向原链表的最后一个节点，更新 head
this.head = prev;
}
}
判断链表中是否存在循环（了解）
链表中存在循环是指，本应在尾节点指针域保存 None 值，而实际保存链表中前面任意节点的地址，最终链表无法结束，形成循环。
但此循环并非一定是单向循环链表，循环存在的形式有可能类似 6 也有可能类似 0。
判断一个链表中是否存在循环，最经典的方法是使用快慢指针法。
python
# 使用快慢指针方法判断链表中是否有循环
def has_cycle(self):
"""判断链表是否有循环"""
# 将快慢指针都指向链表头
slow_pointer = self.head
fast_pointer = self.head
# 两个指针都不为 None，且 fast_pointer 的下一个节点也不为 None。
# 这个条件确保了在链表结束或检测到循环之前，循环将继续执行
# 如果有一个为空，说明链表有结束点
while slow_pointer and fast_pointer and fast_pointer.next:
# 移动慢指针，一次向后移动一个节点
slow_pointer = slow_pointer.next
# 移动快指针，一次向后移动两个节点
fast_pointer = fast_pointer.next.next
# 如果快慢指针相同，说明有循环
# 如果不存在循环的情况下，快指针会先结束，而存在循环时，快指针会套圈慢指针
if slow_pointer == fast_pointer:
return True
# 循环结束说明没有循环
return False
# 给链表添加循环,此方法只在测试链表中是否有循环时没用
def add_cycle(self):
current = self.head
while current.next:
current = current.next
# 让尾结点指针域指向自己，在尾节点上实现循环
current.next = current
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// 判断链表是否有循环
public boolean hasCycle() {
Node slowPointer = this.head;
Node fastPointer = this.head;
// 两个指针都不为 null，且 fastPointer 的下一个节点也不为 null
while (slowPointer != null && fastPointer != null && fastPointer.next != null) {
// 移动慢指针，一次向后移动一个节点
slowPointer = slowPointer.next;
// 移动快指针，一次向后移动两个节点
fastPointer = fastPointer.next.next;
// 如果快慢指针相同，说明有循环
if (slowPointer == fastPointer) {
return true;
}
}
// 循环结束说明没有循环
return false;
}
// 给链表添加循环，此方法只在测试链表中是否有循环时使用
public void addCycle() {
if (this.head == null) {
return; // 空链表无循环
}
Node current = this.head;
// 遍历到链表的最后一个节点
while (current.next != null) {
current = current.next;
}
// 让尾节点的指针指向自己，实现循环
current.next = current;
}
}
判断两个链表是否有交叉（了解）
两个链表本应是独立存在的，某些情况下，有可以两个链表中的某个节点共同指向了同一个节点的位置，形成交叉。
两个链表交叉不会出现 X 型交叉，只能形成 Y 型或 V 型交叉。
可以使用依次遍历节点的方式判断两个链表是否有交叉。
python
def intersection(self, other_list):
"""判断两个链表是否有交叉点"""
# 定义两个指针分别指向两个链表的头节点
current_a = self.head
# 如果两个指针都不为空则继续循环
while current_a:
current_b = other_list.head
while current_b:
# 如果两个指针相同，说明存在交叉点
if current_a == current_b:
return True
# 分别向后移动两个指针
current_b = current_b.next
current_a = current_a.next
# 循环结束，说明没有交叉点
return False
# 创建交叉节点方法,此方法在测试链表是否有交叉时调用
def add_intersection(self, other_list):
# 两个指针分别指向两个链表头
current_a = self.head
current_b = other_list.head
# 循环找到一个链表的结尾
while current_a.next and current_b.next:
current_a = current_a.next
current_b = current_b.next
# 如果B短，让B的尾节点指向A的节点
if current_a.next:
current_b.next = current_a
# 指向结束后，强制结束，否则会出现循环链表的问题，最后一个节点无限循环
return
# 如果A短，让B的尾节点指向B的节点
if current_b.next:
current_a.next = current_b
return
java
public class LinkedList {
Node head; // 链表头节点
// 链表节点内部类
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
// 判断两个链表是否有交叉点
public boolean intersection(LinkedList otherList) {
Node currentA = this.head;
while (currentA != null) {
Node currentB = otherList.head;
while (currentB != null) {
// 如果两个指针相同，说明存在交叉点
if (currentA == currentB) {
return true;
}
currentB = currentB.next;
}
currentA = currentA.next;
}
// 循环结束，说明没有交叉点
return false;
}
// 创建交叉节点方法，此方法在测试链表是否有交叉时调用
public void addIntersection(LinkedList otherList) {
Node currentA = this.head;
Node currentB = otherList.head;
// 循环找到一个链表的结尾
while (currentA.next != null && currentB.next != null) {
currentA = currentA.next;
currentB = currentB.next;
}
// 如果A长，让B的尾节点指向A的节点
if (currentA.next != null) {
currentB.next = currentA;
return;
}
// 如果B长，让A的尾节点指向B的节点
if (currentB.next != null) {
currentA.next = currentB;
}
}
}
应用场景
- 内存管理：链表可以动态分配内存，适用于内存使用需要非常灵活的情况。
- 实现栈和队列：链表是实现栈和队列的理想数据结构，因为它们可以在两端快速添加或删除元素。
- 数据结构的构建：链表可以作为其他复杂数据结构（如哈希表、图的邻接表）的基础。
- 算法实现：在某些算法中，链表提供了一种简单的方式来表示问题，如广度优先搜索（BFS）。
总结
链表是一种基本但强大的数据结构，它提供了不同于数组的灵活性和动态性。
理解链表的工作原理和实现方法对于解决许多编程问题至关重要。