链表是一种常用的数据结构，用于存储逻辑关系为“一对一”的数据。它通过指针链接次序来实现数据元素的逻辑顺序，不要求数据在内存中连续存储，各个元素可以分散存储在内存中。
定义及概念
链表由一系列节点组成，每个节点包含数据域和指针域，链表可分为单链表、双向链表、环形链表
- 数据域（data）：存储数据元素
- 指针域（next）：存储下一个节点的地址
单链表：每个节点只有一个指针，指向下一个节点；
双向链表：每个节点有两个指针，分别指向前一个节点和下一个节点；
- 缓存实现：在缓存系统中，双向链表可以用来实现一种先进先出（FIFO）的缓存策略。通过双向链表，可以方便地添加新条目并移除最老的条目，从而优化缓存的利用率；
- 路径跟踪：双向链表可以用来记录文件或目录的访问历史。通过双向链表，可以方便地回溯到之前的路径，这对于调试和历史记录管理非常有用；
- 图的邻接表表示：在图的表示中，双向链表可以用来存储图的邻接表。每个节点通过双向链表连接其相邻节点，这样可以方便地访问图中任意节点的所有邻居，适用于需要频繁访问图中节点及其邻居的应用，如图的遍历和搜索算法；
- 哈希桶的冲突解决：在哈希表中处理哈希冲突时，双向链表可以用作冲突解决机制。当多个键映射到同一个哈希桶时，可以将它们链接在一个双向链表中，以便高效地处理和查找冲突项；
环形链表：尾部节点的指针指向头结点（也可指向第一个节点），形成一个环；
- 约瑟夫问题（Josephus Problem）：这是一个经典的数学问题，描述了一群人围坐在一圈，每次数到某个数字的人出列，直到只剩下最后一个人。单向环形链表可以很好地模拟这个过程，通过每次删除指定位置的节点来解决问题。
- 环形缓冲区：单向环形链表可用于实现环形缓冲区，如音频、视频等数据的输入和输出。数据可以循环写入和读取，提高数据处理效率。
- 循环队列：单向环形链表还可用于实现循环队列，适用于操作系统中的任务调度、缓冲区管理等场景。循环队列可以有效地管理有限的资源，实现高效的任务调度和数据处理。
优点及缺点
优点：
1. 动态大小：链表的大小可在运行时动态改变，不用预先初始化链表的大小；
2. 插入、删除效率高：插入或删除元素只需更新相邻节点的指针，时间复杂度为O(1)，而数组可能需要O(n)
3. 非连续存储：数据元素不必连续存储，可有效的利用内存空间缺点：
1. 访问效率低：访问特定节点需要从头开始遍历链表，时间复杂度为O(n)
2. 空间开销大：每个节点需要额外存储额外的指针域，增加了空间开销
使用场景
- 动态数据集：当数据集不确定大小时，链表可以随时添加或删除元素；
- 频繁插入、删除：在频繁操作插入和删除动作时，链表比数组效率更高；
- 内存碎片处理：在内存碎片较多的环境中，链表可以更高效的使用内存；
代码：
- 单链表
/**
* 单链表Demo
* 1. 以节点的形式存储
* 2. 每个节点的都包含 data域；next域(指向下一节点)
* 3. 每个节点在内存中不一定是连续存储
* 4. 有带头结点的链表 和 不带头节点的链表，根据需求来确定使用方式
*/
public class SingleLinkedListDemo {
//带头节点的链表，初始化头节点
private final TNode head = new TNode(0,"花名（列）");
public static void main(String[] args) {
TNode node1 = new TNode(1,"玫瑰花");
TNode node2 = new TNode(2,"牡丹花");
TNode node3 = new TNode(3,"梅花");
TNode node4 = new TNode(4,"桂花");
SingleLinkedListDemo demo = new SingleLinkedListDemo();
System.out.println("添加后结果：");
demo.add(node1);
demo.add(node2);
demo.add(node3);
demo.add(node4);
demo.list();
System.out.println("更新后结果：");
TNode updateNode = new TNode(3,"樱花");
demo.update(updateNode);
demo.list();
System.out.println("删除后结果：");
demo.remove(2);
demo.remove(1);
demo.remove(4);
demo.remove(5);
demo.list();
}
/**
* 添加节点
* @param node
*/
public void add(TNode node){
TNode temp = head; //临时节点
//循环当前节点信息
while (true){
if(temp.next == null){
break;
}
temp = temp.next; //移动至下一个节点
}
temp.next = node;
}
/**
* 更新节点
* @param node
*/
public void update(TNode node){
TNode temp = head.next;
if(temp == null){
System.out.println("链表数据不存在，无法更新");
return ;
}
//找到对应节点的索引，替换数据
while (true){
if(temp.index == node.index){
//找到相同索引数据，更新该节点text内容
temp.text = node.text;
break;
}
temp = temp.next;
}
}
/**
* 删除节点
* @param index
*/
public void remove(int index){
if(head.next == null){
System.out.println("链表数据不存在，无法删除");
return ;
}
TNode temp = head.next;
TNode lastNode = head;
while (true){
if(temp == null){
System.out.printf("不存在【%d】节点无法删除\n", index);
break;
}
if(temp.index == index){
//找到对应索引数据，将上一个节点的 next 指向当前节点的next
lastNode.next = temp.next;
break;
}
lastNode = temp; //上一个节点指针指向当前节点
temp = temp.next;//下一节点指针指向当前节点
}
}
/**
* 显示节点数据
*/
public void list(){
//循环显示链表数据
if(head.next == null){
System.out.println("数据链表为空");
return;
}
TNode temp = head;
while (true){
if(temp == null){
break;
}
System.out.println(temp.toString());
temp = temp.next;
}
}
}
/**
* 节点样例
*/
class TNode{
public int index; // 索引
public String text; //文本
public TNode next; //下一节点
//构造方法
public TNode(int index, String text) {
this.index = index;
this.text = text;
}
@Override
public String toString(){
return this.index + " | " + this.text;
}
}
- 双向链表
/**
* 双向链表Demo
* 1. 以节点的形式存储
* 2. 每个节点的都包含 data域；nextNode域(指向下一个节点) preNode域（指向下一个节点）
* 3. 每个节点在内存中不一定是连续存储
* 4. 双向链表可以向前或向后查找数据，并且可以实现自删除
*/
public class DoubleLinkedListDemo {
//带头节点的链表，初始化头节点
private final TDNode head = new TDNode(0,"花名（列）");
public static void main(String[] args) {
TDNode node1 = new TDNode(3,"玫瑰花");
TDNode node2 = new TDNode(1,"牡丹花");
TDNode node3 = new TDNode(4,"梅花");
TDNode node4 = new TDNode(2,"桂花");
DoubleLinkedListDemo demo = new DoubleLinkedListDemo();
System.out.println("添加后结果：");
demo.add(node1);
demo.add(node2);
demo.add(node3);
demo.add(node4);
demo.list();
System.out.println("更新后结果：");
TDNode updateNode = new TDNode(3,"樱花");
demo.update(updateNode);
demo.list();
System.out.println("删除后结果：");
demo.remove(2);
demo.remove(4);
demo.remove(5);
demo.list();
}
/**
* 添加节点（动态根据index排序进行插入动作）
* @param node
*/
public void add(TDNode node){
TDNode temp = head; //临时节点
//循环当前节点信息
while (true){
// node.index 等于 temp.index 则 提示该节点与存在，无法插入该节点；
if(node.index == temp.index){
System.out.printf("当前index【%d】已经存在节点 \n", node.index);
break;
}
TDNode tempNextNode = temp.nextNode;
if(tempNextNode == null){
//如果下个节点为空，则直接链接到链表尾部
temp.nextNode = node;
node.preNode = temp;
break;
}
//寻找插入节点的位置,
if(temp.index < node.index && node.index < tempNextNode.index){
//设置node前后节点
node.preNode = temp;
node.nextNode = tempNextNode;
//更新前后节点的指针
temp.nextNode = node;
tempNextNode.preNode = node;
break;
}
temp = temp.nextNode;
}
}
/**
* 更新节点
* @param node
*/
public void update(TDNode node){
TDNode temp = head.nextNode;
if(temp == null){
System.out.println("链表数据不存在，无法更新");
return ;
}
//找到对应节点的索引，替换数据
while (true){
if(temp.index == node.index){
//找到相同索引数据，更新该节点text内容
temp.text = node.text;
break;
}
temp = temp.nextNode;
}
}
/**
* 删除节点
* @param index
*/
public void remove(int index){
if(head.nextNode == null){
System.out.println("链表数据不存在，无法删除");
return ;
}
TDNode temp = head.nextNode;
while (true){
if(temp == null){
System.out.printf("不存在【%d】节点无法删除\n", index);
break;
}
TDNode tempNextNode = temp.nextNode;
if(temp.index == index){
//找到对应索引数据，将上temp.preNode.nextNode 指向 temp.nextNode, temp.nextNode.preNode 指向 temp.preNode
temp.preNode.nextNode = temp.nextNode;
if(tempNextNode != null){
temp.nextNode.preNode = temp.preNode;
}
break;
}
temp = temp.nextNode;//下一节点指针指向当前节点
}
}
/**
* 显示节点数据
*/
public void list(){
//循环显示链表数据
if(head.nextNode == null){
System.out.println("数据链表为空");
return;
}
TDNode temp = head;
while (true){
if(temp == null){
break;
}
System.out.println(temp.toString());
temp = temp.nextNode;
}
}
}
/**
* 节点样例
*/
class TDNode{
public int index; // 索引
public String text; //文本
public TDNode nextNode; //下一个节点
public TDNode preNode; //上一个节点
//构造方法
public TDNode(int index, String text) {
this.index = index;
this.text = text;
}
@Override
public String toString(){
int next = 0,pre = 0;
if(this.nextNode != null){
next = this.nextNode.index;
}
if(this.preNode != null){
pre = this.preNode.index;
}
return this.index + " | " + this.text + " | " +pre+"-" +next ;
}
}
- 环形链表（约瑟夫问题）
/**
* 环形链表Demo （无head节点）
* 1. 以节点的形式存储
* 2. 单向环形链表是指在单链表的基础上，最后一个节点的指针域指向链表的第一个节点，从而构成一个闭合的环。
* 3. 每个节点包含一个数据域和一个指针域。数据域用于存储数据，指针域用于指向下一个节点。在单向环形链表中，最后一个节点的指针域指向第一个节点，形成环状结构。
* 环形链表解决约瑟夫问题
*/
public class JosephuLinkedListDemo {
//链表初始节点
private static Child first = new Child(-1);
//带头节点的链表，初始化头节点
public static void main(String[] args) {
JosephuLinkedListDemo demo = new JosephuLinkedListDemo();
int childNum = 10; //节点数量
System.out.println("初始化环形链表：");
for (int i = 1; i <= childNum; i++) {
demo.addChild(new Child(i));
}
demo.showChildLinkedList();
demo.countChild(2 ,3 , childNum);
}
/**
* 添加节点
* @param node
*/
public void addChild(Child node){
if(first.no == -1){
//初始节点 -1 表示链表为空，设置first节点为当前node
first = node;
node.next = first; // 一个节点，指向自己完成闭环
return;
}
//寻找链表末尾节点，插入新节点
Child temp = first; //临时节点，进行环形链表遍历使用
while (true){
if(temp.next.no == first.no){
//找到末尾节点，临时节点的下一个节点no 与first.no相等
temp.next = node; //改变临时节点的 next节点
node.next = first; //改变新增节点的 next节点（完成闭环）
break;
}
temp = temp.next;
}
}
/**
* 显示环形节点数据
*/
public void showChildLinkedList(){
//循环显示链表数据
if(first.no == -1){
System.out.println("数据链表为空");
return;
}
Child temp = first;
while (true){
System.out.println("第【"+temp.no+"】节点" );
if(temp.next.no == first.no){
break;
}
temp = temp.next;
}
}
/**
* 数节点逻辑，约定 childNum 个节点， 从startNo节点开始，从1开始数，数到num的那个节点出列；
* 它的下一个节点继续从1开始数，数到num的那个节点出列，以此类推；
* 打印：编号的出列顺序
* @param startNo 数节点其实位置
* @param num 每次数N个位置
* @param childNum 总节点数量
*/
public void countChild(int startNo, int num, int childNum){
//判断节点数必须大于 1
if(childNum <= 1){
System.out.println("节点数量不正确");
return;
}
//判断从哪个节点开始数
Child helper = first; //临时节点，遍历使用
//移动辅助指针至尾部
while (true){
if(helper.next.no == first.no){
break;
}
helper = helper.next;
}
//将first、helper节点指针移动至开始位置
for(int i = 0; i < startNo - 1; i++){
first = first.next;
helper = helper.next;
}
// 开始数节点，进行节点出列
while (true){
if(helper.no == first.no){
//仅剩一个节点，任务结束
System.out.printf("\n 节点【%d】未出列", first.no);
break;
}
// 出列逻辑，移动辅助指针和first指针
for(int i = 0; i < num-1; i++){
first = first.next;
helper = helper.next;
}
//移动完成，当前cruChild就是需要出列的节点
System.out.printf("【%d】出列 ", first.no);
//修改当前引用
first = first.next;
helper.next = first;
}
}
}
/**
* 小孩节点样例
*/
class Child{
public int no; // 编号
public Child next; //下一个节点
//构造方法
public Child(int no) {
this.no = no;
}
}
网友评论