java单链表；双向链表；双向循环链表—

一、链表(Linked List)介绍

链表是有序的列表，但是它在内存中是存储如下

链表是以节点的方式来存储,是链式存储
每个节点包含 data 域， next 域：指向下一个节点.
如图：发现链表的各个节点不一定是连续存储.
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

二、单链表介绍

单链表(带头结点) 逻辑结构示意图如下

三、单链表的应用实例

使用带head头的单向链表实现 –水浒英雄排行榜管理

完成对英雄人物的增删改查操作

3.1、节点的定义

1、定义HeroNode ，每个HeroNode 对象就是一个节点

class HeroNode {public int no;public String name;public String nickname;public HeroNode next; //指向下一个节点//构造器public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}//为了显示方法，我们重新toString@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}}

2、定义SingleLinkedList 管理我们的英雄

class SingleLinkedList {//先初始化一个头节点, 头节点不要动, 不存放具体的数据private HeroNode head = new HeroNode(0, "", "");//返回头节点public HeroNode getHead() {return head;}
}

3.2、显示链表

通过一个辅助变量遍历，帮助遍历整个链表

//显示链表[遍历]
public void list() {//判断链表是否为空if(head.next == null) {System.out.println("链表为空");return;}//因为头节点，不能动，因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while(true) {//判断是否到链表最后if(temp == null) {break;}//输出节点的信息System.out.println(temp);//将temp后移， 一定小心temp = temp.next;}
}

3.3、增

3.3.1、第一种方法在添加英雄时，直接添加到链表的尾部

1. 先创建一个head 头节点，作用就是表示单链表的头
2. 后面我们每添加一个节点，就直接加入到链表的最后

//添加节点到单向链表
//思路，当不考虑编号顺序时
//1. 找到当前链表的最后节点
//2. 将最后这个节点的next 指向 新的节点
public void add(HeroNode heroNode) {//因为head节点不能动，因此我们需要一个辅助遍历 tempHeroNode temp = head;//遍历链表，找到最后while(true) {//找到链表的最后if(temp.next == null) {//break;}//如果没有找到最后, 将将temp后移temp = temp.next;}//当退出while循环时，temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next = heroNode;
}

3.3.2、第二种方式在添加英雄时，根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示)

1. 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定
2. 新的节点.next = temp.next
3. 将temp.next = 新的节点

//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//(如果有这个排名，则添加失败，并给出提示)
public void addByOrder(HeroNode heroNode) {//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了HeroNode temp = head;boolean flag = false; // flag标志添加的编号是否存在，默认为falsewhile(true) {if(temp.next == null) {//说明temp已经在链表的最后break; //} if(temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入break;} else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在flag = true; //说明编号存在break;}temp = temp.next; //后移，遍历当前链表}//判断flag 的值if(flag) { //不能添加，说明编号存在System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);} else {//插入到链表中, temp的后面heroNode.next = temp.next;temp.next = heroNode;}
}

3.4、删

1. 我们先找到需要删除的这个节点的前一个节点 temp
2. temp.next = temp.next.next
3. 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

//删除节点
//思路
//1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
//2. 说明我们在比较时，是temp.next.no 和  需要删除的节点的no比较
public void del(int no) {HeroNode temp = head;boolean flag = false; // 标志是否找到待删除节点的while(true) {if(temp.next == null) { //已经到链表的最后break;}if(temp.next.no == no) {//找到的待删除节点的前一个节点tempflag = true;break;}temp = temp.next; //temp后移，遍历}//判断flagif(flag) { //找到//可以删除temp.next = temp.next.next;}else {System.out.printf("要删除的 %d 节点不存在\n", no);}
}

3.5、改

//修改节点的信息, 根据no编号来修改，即no编号不能改.
//说明
//1. 根据 newHeroNode 的 no 来修改即可
public void update(HeroNode newHeroNode) {//判断是否空if(head.next == null) {System.out.println("链表为空~");return;}//找到需要修改的节点, 根据no编号//定义一个辅助变量HeroNode temp = head.next;boolean flag = false; //表示是否找到该节点while(true) {if (temp == null) {break; //已经遍历完链表}if(temp.no == newHeroNode.no) {//找到flag = true;break;}temp = temp.next;}//根据flag 判断是否找到要修改的节点if(flag) {temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;} else { //没有找到System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);}
}

四、双向链表应用实例

使用带head头的双向链表实现 –水浒英雄排行榜

完成对英雄人物的增删改查操作

管理单向链表的缺点分析:

1）单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

2）单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点(认真体会).

3）示意图帮助理解删除

4.1、节点的定义

1、定义HeroNode2 ，每个HeroNode 对象就是一个节点

class HeroNode2 {public int no;public String name;public String nickname;public HeroNode2 next; // 指向下一个节点, 默认为nullpublic HeroNode2 pre; // 指向前一个节点, 默认为null// 构造器public HeroNode2(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}// 为了显示方法，我们重新toString@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";}}

2、创建一个双向链表的类

class DoubleLinkedList {// 先初始化一个头节点, 头节点不要动, 不存放具体的数据private HeroNode2 head = new HeroNode2(0, "", "");// 返回头节点public HeroNode2 getHead() {return head;}
}}

4.2、显示链表

// 遍历双向链表的方法
// 显示链表[遍历]
public void list() {// 判断链表是否为空if (head.next == null) {System.out.println("链表为空");return;}// 因为头节点，不能动，因此我们需要一个辅助变量来遍历HeroNode2 temp = head.next;while (true) {// 判断是否到链表最后if (temp == null) {break;}// 输出节点的信息System.out.println(temp);// 将temp后移， 一定小心temp = temp.next;}
}

4.3、增

// 添加一个节点到双向链表的最后.
public void add(HeroNode2 heroNode) {// 因为head节点不能动，因此我们需要一个辅助遍历 tempHeroNode2 temp = head;// 遍历链表，找到最后while (true) {// 找到链表的最后if (temp.next == null) {//break;}// 如果没有找到最后, 将将temp后移temp = temp.next;}// 当退出while循环时，temp就指向了链表的最后// 形成一个双向链表temp.next = heroNode;heroNode.pre = temp;
}

4.4、删

// 从双向链表中删除一个节点,
// 说明
// 1 对于双向链表，我们可以直接找到要删除的这个节点
// 2 找到后，自我删除即可
public void del(int no) {// 判断当前链表是否为空if (head.next == null) {// 空链表System.out.println("链表为空，无法删除");return;}HeroNode2 temp = head.next; // 辅助变量(指针)boolean flag = false; // 标志是否找到待删除节点的while (true) {if (temp == null) { // 已经到链表的最后break;}if (temp.no == no) {// 找到的待删除节点的前一个节点tempflag = true;break;}temp = temp.next; // temp后移，遍历}// 判断flagif (flag) { // 找到// 可以删除// temp.next = temp.next.next;[单向链表]temp.pre.next = temp.next;// 这里我们的代码有问题?// 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针if (temp.next != null) {temp.next.pre = temp.pre;}} else {System.out.printf("要删除的 %d 节点不存在\n", no);}
}

4.5、改

// 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
// 只是 节点类型改成 HeroNode2
public void update(HeroNode2 newHeroNode) {// 判断是否空if (head.next == null) {System.out.println("链表为空~");return;}// 找到需要修改的节点, 根据no编号// 定义一个辅助变量HeroNode2 temp = head.next;boolean flag = false; // 表示是否找到该节点while (true) {if (temp == null) {break; // 已经遍历完链表}if (temp.no == newHeroNode.no) {// 找到flag = true;break;}temp = temp.next;}// 根据flag 判断是否找到要修改的节点if (flag) {temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;} else { // 没有找到System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);}
}

3.6、主函数测试

public class DoubleLinkedListDemo {public static void main(String[] args) {// 测试System.out.println("双向链表的测试");// 先创建节点HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");// 创建一个双向链表DoubleLinkedList doubleLinkedList = new DoubleLinkedList();doubleLinkedList.add(hero1);doubleLinkedList.add(hero2);doubleLinkedList.add(hero3);doubleLinkedList.add(hero4);doubleLinkedList.list();		// 修改HeroNode2 newHeroNode = new HeroNode2(4, "公孙胜", "入云龙");doubleLinkedList.update(newHeroNode);System.out.println("修改后的链表情况");doubleLinkedList.list();		// 删除doubleLinkedList.del(3);System.out.println("删除后的链表情况~~");doubleLinkedList.list();						}
}

五、单向环形链表应用场景

Josephu(约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

链接-->.......待完成（预计2024/8/2完成）

六、力扣链表相关题目

链接-->.......待完成