在 Devin 中试用 DeepWiki 处理私有仓库
DeepWiki

TheAlgorithms/Java

菜单

列表实现

相关源文件

本页面记录了存储库中实现的各种链表数据结构。它涵盖了基本的单向链表及其循环变体，以及反转、旋转和排序链表等专用操作。有关堆、缓存或树等其他数据结构，请参阅 数据结构。

列表实现概览

该存储库提供了健壮的链表数据结构实现，主要关注单向链表及其上可执行的各种操作。这些实现既是教育示例，也是处理链接数据结构的实用工具。

来源: src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java src/main/java/com/thealgorithms/datastructures/lists/CircleLinkedList.java src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedListNode.java

核心列表数据结构

单向链表

SinglyLinkedList 类实现了基本的单向链表，其中每个节点包含一个值和指向序列中下一个节点的引用。该实现包括标准的列表操作以及专用算法。

SinglyLinkedList 实现的关键特性

  • 节点结构：每个节点存储一个整数值和指向下一个节点的引用
  • 基本操作：用于列表操作的插入、删除和搜索操作
  • 高级算法：循环检测、查找中间元素和列表反转
  • 可迭代接口：实现了 Java 的 Iterable 接口，以支持增强的 for 循环

该实现提供了以下方法

操作方法描述
插入insertHead(int)在开头插入元素
insert(int)在末尾插入元素
insertNth(int, int)在特定位置插入
删除deleteHead()删除第一个元素
delete()删除最后一个元素
deleteNth(int)从特定位置删除
搜索search(int)检查列表中是否存在某个值
实用工具middle()查找列表的中间节点
detectLoop()检查列表是否包含循环
reverseListIter(SinglyLinkedListNode)迭代反转列表
reverseListRec(SinglyLinkedListNode)递归反转列表

来源: src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedListNode.java

循环链表

CircleLinkedList 类实现了循环单向链表，其中最后一个节点指向第一个节点，形成一个圆。此实现使用虚拟头节点来简化操作。

CircleLinkedList 实现的关键特性

  • 循环结构：最后一个节点指向头部，形成连续循环
  • 虚拟头部：使用具有空值的虚拟头部节点来简化实现
  • 泛型实现：可处理任何对象类型，而不仅仅是整数
  • 基本操作：支持追加元素和从特定位置移除

该类提供了以下方法

方法描述
getSize()返回列表中元素的数量
append(E value)将新元素添加到列表末尾
remove(int pos)移除并返回指定位置的元素
toString()返回列表的字符串表示形式

来源: src/main/java/com/thealgorithms/datastructures/lists/CircleLinkedList.java

列表操作和算法

反转操作

反转链表

SinglyLinkedList 类提供了两种反转链表的方法

  1. 迭代方法 (reverseListIter): 使用三指针技术通过改变 next 指针的方向来反转列表。
  2. 递归方法 (reverseListRec): 通过递归地反转从第二个节点开始的子列表，然后调整第一个节点的指针来反转列表。

反转 K 组

ReverseKGroup 类提供了在 K 大小的组中反转链表节点的功能

算法

  1. 计算链表长度
  2. 反转 K 个节点的每个组
  3. 如果剩余节点少于 K 个，则保持不变
  4. 时间复杂度: O(n)，空间复杂度: O(1)

来源: src/main/java/com/thealgorithms/datastructures/lists/ReverseKGroup.java

旋转操作

RotateSinglyLinkedLists 类提供了将单向链表向右旋转 K 个位置的功能

旋转算法

  1. 对于空列表或 K=0，返回列表不变
  2. 计算列表长度
  3. 通过连接最后一个节点到头部来使列表成为循环列表
  4. 前进 (len-K)%len 个位置以找到新的尾部
  5. 将下一个节点设置为新头部并断开循环
  6. 时间复杂度: O(n)，空间复杂度: O(1)

来源: src/main/java/com/thealgorithms/datastructures/lists/RotateSinglyLinkedLists.java

列表排序算法

链表快速排序

QuickSortLinkedList 类实现了单向链表的快速排序算法

链表快速排序算法

  1. 选择第一个元素作为枢轴
  2. 将列表划分为小于枢轴的元素和大于等于枢轴的元素
  3. 递归地对两个分区进行排序
  4. 将排序后的分区合并到枢轴周围
  5. 时间复杂度: 平均 O(n log n)，最坏 O(n²)

来源: src/main/java/com/thealgorithms/datastructures/lists/QuickSortLinkedList.java

合并排序列表

MergeSortedSinglyLinkedList 类提供了将两个已排序的链表合并成一个已排序列表的功能

合并算法

  1. 创建一个新列表来存储合并结果
  2. 比较两个列表的头部，并将较小的值添加到结果中
  3. 前进取值列表中的指针
  4. 继续直到其中一个列表为空，然后附加剩余的列表
  5. 时间复杂度: O(n+m)，其中 n 和 m 是两个列表的长度

来源: src/main/java/com/thealgorithms/datastructures/lists/MergeSortedSinglyLinkedList.java

递归列表操作

SearchSinglyLinkedListRecursion 类继承自 SinglyLinkedList 以实现递归搜索算法

递归搜索算法

  1. 检查当前节点的键值是否等于搜索键
  2. 如果是，则返回 true
  3. 如果不是并且还有更多节点，则递归搜索列表的其余部分
  4. 如果没有更多节点，则返回 false
  5. 时间复杂度: O(n)，空间复杂度: O(n)（因为递归调用栈）

来源: src/main/java/com/thealgorithms/datastructures/lists/SearchSinglyLinkedListRecursion.java

递归计数

CountSinglyLinkedListRecursion 类继承自 SinglyLinkedList 以实现递归计数算法

递归计数算法

  1. 如果当前节点为空，则返回 0
  2. 否则，返回 1 加上列表中其余部分的计数
  3. 时间复杂度: O(n)，空间复杂度: O(n)（因为递归调用栈）

来源: src/main/java/com/thealgorithms/datastructures/lists/CountSinglyLinkedListRecursion.java

性能特征

各种列表操作在实现中的时间和空间复杂度

操作时间复杂度空间复杂度
按索引访问O(n)O(1)
搜索O(n)O(1)
在开头插入O(1)O(1)
在末尾插入O(n)O(1)
在指定位置插入O(n)O(1)
从开头删除O(1)O(1)
从末尾删除O(n)O(1)
从位置删除O(n)O(1)
反转列表O(n)O(1)
检测循环O(n)O(1)
查找中间O(n)O(1)
旋转列表O(n)O(1)
快速排序O(n log n) 平均, O(n²) 最坏O(log n)
合并已排序列表O(n+m)O(1)

来源: src/main/java/com/thealgorithms/datastructures/lists/SinglyLinkedList.java src/main/java/com/thealgorithms/datastructures/lists/ReverseKGroup.java src/main/java/com/thealgorithms/datastructures/lists/RotateSinglyLinkedLists.java src/main/java/com/thealgorithms/datastructures/lists/QuickSortLinkedList.java src/main/java/com/thealgorithms/datastructures/lists/MergeSortedSinglyLinkedList.java

使用示例

基本的单向链表操作

来源: src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java402-432

检测链表中的循环

来源: src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java35-51

反转链表

来源： src/test/java/com/thealgorithms/datastructures/lists/SinglyLinkedListTest.java107-143

旋转链表

来源： src/test/java/com/thealgorithms/datastructures/lists/RotateSinglyLinkedListsTest.java61-64

在链表上使用快速排序

来源： src/test/java/com/thealgorithms/datastructures/lists/QuickSortLinkedListTest.java77-93