Java数据结构与算法

Java数据结构与算法

day02-链表

文章目录

• • • day02-链表
    • • • 单链表介绍和内存布局
      • 单链表创建和遍历的分析实现
      • 遍历过程
      • 单链表节点的修改
      • 单链表节点的删除和小结
    • 双向链表增删改查分析图解及实现
    • 环形链表介绍和约瑟夫问题
    • 约瑟夫问题分析图解和实现

单链表介绍和内存布局

• 链表是有序的列表，但是内存中是实际存储结构如下：
  
  小结:

1.链表是以节点的方式来存储,是链式存储(即各个节点之间并不一定是连续存储的，而是相互指向的);
2.每个节点包含 data 域:存放数据的域， next 域：指向下一个节点;
3.如图：发现链表的各个节点不一定是连续存储;
4.链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定.

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

单链表创建和遍历的分析实现

• 例子

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

1)完成对英雄人物的增删改查操作， 注: 删除和修改,查找可以考虑学员独立完成，也可带学员完成

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

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

单链表的创建示意图(添加), 显示单向链表的分析

class HeroNode {int no;String name;String nickName;HeroNode next;
}

添加（创建）过程

• 先创建一个head 头节点， 作用就是表示单链表的头;
  
• 之后每添加一个节点，就直接加入到 -> 链表的最后。

遍历过程

• 通过一个辅助变量(临时变量temp)遍历，帮助遍历整个链表。

判断是否链表是否是最后一个节点，看next域是否为空null

单链表按顺序插入节点

• 需要按照编号的顺序添加
• 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定；

• 新的节点.next =

• 将 = 新的节点

代码实现:

/*
此代码已优化
*/
public class SingleLinkedListDemo {public static void main(String[] args) {//进行测试//先创建节点HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");HeroNode hero3 = new HeroNode(3, "吴用", "智多星");HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");//创建要给链表SingleLinkedList singleLinkedList = new SingleLinkedList();//加入singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);//显示singleLinkedList.list();}
}//定义SingleLinkedList来管理我们的英雄
class SingleLinkedList {//先初始化一个头节点,头节点不要动,不存放具体的数据private HeroNode head = new HeroNode(0, " ", " ");//添加节点到单向链表//思路，当不考虑编号顺序时//1.找到当前链表的最后节点//2.将最后这个节点的next 指向新的节点public void add(HeroNode heroNode){//因为head节点不能动,因此我们需要一个辅助遍历 tempHeroNode temp = head;//遍历链表,找到最后的节点while (true){//找到链表的最后if ( == null){break;}//如果最后没有找到,就将temp后移temp = ;}//当退出while循环时，temp就指向了链表的最后 = heroNode;}//第二种方式在添加英雄时，根据排名将英雄插入到指定位置//(如果有这个排名，则添加失败，并给出提示)public void addByOrder(HeroNode heroNode){//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表，因此我们找的temp 是位于 添加位置的前一个节点，否则插入不了HeroNode temp = head;boolean flag = false;//标指添加的编号是否存在，默认为falsewhile (true){if ( == null){//说明temp已经在链表的最后break;//不管找到还是没找到都break;}if ( > ){//位置找到，就在temp的后面插入break;}else if ( == ){//说明希望添加的heroNode的编号已经存在了flag = true;//说明编号存在break;}temp = ;//后移,遍历当前链表}//判断flag 的值if (flag){//不能添加，说明编号存在System.out.println("准备插入的英雄的编号" +  + "已经存在,不能加入");}else {//插入到链表,temp的后边 = ; = heroNode;}}//显示链表[遍历]public void list(){//先判断链表是否为空if ( == null){System.out.println("链表为空");return;}//因为头节点不能动,因此我们需要一个辅助变量来遍历HeroNode temp = ;while (true){//判断是否到链表最后if (temp == null){break;}//输出节点的信息System.out.println(temp);//将temp后移，一定要小心，不然是死循环,输出完一个后移输出下一个。temp = ;}}
}//先定义一个HeroNode，每个HeroNode对象 就是一个节点
class HeroNode{public int no;public String nickname;public String name;public HeroNode next;//指向下一个节点//构造器public HeroNode(int no,String name,String nickname){ = no;this.name = name;this.nickname = nickname;}//为了显示方便，我们重写toString@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", nickname='" + nickname + ''' +", name='" + name + ''' +'}';}
}

单链表节点的修改

public class SingleLinkedListDemo {public static void main(String[] args) {//进行测试//先创建节点HeroNode hero1 = new HeroNode(1, "艾福杰尼", "DM");HeroNode hero2 = new HeroNode(2, "黄旭", "OB");HeroNode hero3 = new HeroNode(3, "刘聪", "key.L");HeroNode hero4 = new HeroNode(4, "派克特", "pact");HeroNode hero5 = new HeroNode(5, "王以太", "3ho");HeroNode hero6 = new HeroNode(6, "李佳隆", "jelloReal");//创建要给链表SingleLinkedList singleLinkedList = new SingleLinkedList();//加入singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero5);singleLinkedList.addByOrder(hero6);//显示singleLinkedList.list();//创建修改节点的代码HeroNode newHeroNode = new HeroNode(6, "马思唯", "MSW");singleLinkedList.update(newHeroNode);//显示singleLinkedList.list();}
}//定义SingleLinkedList来管理我们的英雄
class SingleLinkedList {//先初始化一个头节点,头节点不要动,不存放具体的数据private HeroNode head = new HeroNode(0, " ", " ");//添加节点到单向链表//思路，当不考虑编号顺序时//1.找到当前链表的最后节点//2.将最后这个节点的next 指向新的节点public void add(HeroNode heroNode){//因为head节点不能动,因此我们需要一个辅助遍历 tempHeroNode temp = head;//遍历链表,找到最后的节点while (true){//找到链表的最后if ( == null){break;}//如果最后没有找到,就将temp后移temp = ;}//当退出while循环时，temp就指向了链表的最后 = heroNode;}//第二种方式在添加英雄时，根据排名将英雄插入到指定位置//(如果有这个排名，则添加失败，并给出提示)public void addByOrder(HeroNode heroNode){//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表，因此我们找的temp 是位于 添加位置的前一个节点，否则插入不了HeroNode temp = head;boolean flag = false;//标指添加的编号是否存在，默认为falsewhile (true){if ( == null){//说明temp已经在链表的最后break;//不管找到还是没找到都break;}if ( > ){//位置找到，就在temp的后面插入break;}else if ( == ){//说明希望添加的heroNode的编号已经存在了flag = true;//说明编号存在break;}temp = ;//后移,遍历当前链表}//判断flag 的值if (flag){//不能添加，说明编号存在System.out.println("准备插入的英雄的编号" +  + "已经存在,不能加入");}else {//插入到链表,temp的后边 = ; = heroNode;}}//修改节点的信息,根据no编号来修改,即no编号不能改,如果no改了就相当于添加//说明//1.根据 newHeroNode 的no来修改即可public void update(HeroNode newHeroNode){//判断是否为空if ( == null){System.out.println("链表为空，无节点");return;}//找到需要修改的节点,根据no编号//定义一个辅助变量HeroNode temp = ;boolean flag = false;//表示是否找到该节点while (true){if (temp == null){break;//已经遍历完毕,到链表的最后}if ( == ){//找到了,就是当前我们要修改的节点flag = true;break;}temp = ;}//根据flag 判断是否找到要修改的节点if (flag){//找到了temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;}else { //没有找到这个节点System.out.println("没有找到编号=" +  + "的节点,不能修改。");}}//显示链表[遍历]public void list(){//先判断链表是否为空if ( == null){System.out.println("链表为空");return;}//因为头节点不能动,因此我们需要一个辅助变量来遍历HeroNode temp = ;while (true){//判断是否到链表最后if (temp == null){break;}//输出节点的信息System.out.println(temp);//将temp后移，一定要小心，不然是死循环,输出完一个后移输出下一个。temp = ;}}
}//先定义一个HeroNode，每个HeroNode对象 就是一个节点
class HeroNode{public int no;public String nickname;public String name;public HeroNode next;//指向下一个节点//构造器public HeroNode(int no,String name,String nickname){ = no;this.name = name;this.nickname = nickname;}//为了显示方便，我们重写toString@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", nickname='" + nickname + ''' +", name='" + name + ''' +'}';}
}

单链表节点的删除和小结

从单链表中删除一个节点的思路图解

• 我们先找到 需要删除的这个节点的前一个节点 temp
  
< =

• 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

代码实现:

public class SingleLinkedListDemo {public static void main(String[] args) {//进行测试//先创建节点HeroNode hero1 = new HeroNode(1, "艾福杰尼", "DM");HeroNode hero2 = new HeroNode(2, "黄旭", "OB");HeroNode hero3 = new HeroNode(3, "刘聪", "key.L");HeroNode hero4 = new HeroNode(4, "派克特", "pact");HeroNode hero5 = new HeroNode(5, "王以太", "3ho");HeroNode hero6 = new HeroNode(6, "李佳隆", "jelloReal");//创建要给链表SingleLinkedList singleLinkedList = new SingleLinkedList();//加入singleLinkedList.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero6);singleLinkedList.addByOrder(hero5);singleLinkedList.addByOrder(hero3);//修改前显示//singleLinkedList.list();//创建修改节点的代码HeroNode newHeroNode = new HeroNode(6, "马思唯", "MSW");singleLinkedList.update(newHeroNode);//显示singleLinkedList.list();//删除一个节点//最有可能出问题的是第一个节点和最后一个节点singleLinkedList.del(1);singleLinkedList.del(6);singleLinkedList.del(3);singleLinkedList.list();}
}//定义SingleLinkedList来管理我们的英雄
class SingleLinkedList {//先初始化一个头节点,头节点不要动,不存放具体的数据private HeroNode head = new HeroNode(0, " ", " ");//添加节点到单向链表//思路，当不考虑编号顺序时//1.找到当前链表的最后节点//2.将最后这个节点的next 指向新的节点public void add(HeroNode heroNode){//因为head节点不能动,因此我们需要一个辅助遍历 tempHeroNode temp = head;//遍历链表,找到最后的节点while (true){//找到链表的最后if ( == null){break;}//如果最后没有找到,就将temp后移temp = ;}//当退出while循环时，temp就指向了链表的最后 = heroNode;}//第二种方式在添加英雄时，根据排名将英雄插入到指定位置//(如果有这个排名，则添加失败，并给出提示)public void addByOrder(HeroNode heroNode){//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置//因为单链表，因此我们找的temp 是位于 添加位置的前一个节点，否则插入不了HeroNode temp = head;boolean flag = false;//标指添加的编号是否存在，默认为falsewhile (true){if ( == null){//说明temp已经在链表的最后break;//不管找到还是没找到都break;}if ( > ){//位置找到，就在temp的后面插入break;}else if ( == ){//说明希望添加的heroNode的编号已经存在了flag = true;//说明编号存在break;}temp = ;//后移,遍历当前链表}//判断flag 的值if (flag){//不能添加，说明编号存在System.out.println("准备插入的英雄的编号" +  + "已经存在,不能加入");}else {//插入到链表,temp的后边 = ; = heroNode;}}//修改节点的信息,根据no编号来修改,即no编号不能改,如果no改了就相当于添加//说明//1.根据 newHeroNode 的no来修改即可public void update(HeroNode newHeroNode){//判断是否为空if ( == null){System.out.println("链表为空，无节点");return;}//找到需要修改的节点,根据no编号//定义一个辅助变量HeroNode temp = ;boolean flag = false;//表示是否找到该节点while (true){if (temp == null){break;//已经遍历完毕,到链表的最后}if ( == ){//找到了,就是当前我们要修改的节点flag = true;break;}temp = ;}//根据flag 判断是否找到要修改的节点if (flag){//找到了temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;}else { //没有找到这个节点System.out.println("没有找到编号=" +  + "的节点,不能修改。");}}//删除节点//思路//1.head节点不能动,因此需要一个temp辅助节点找到待删除节点的前一个节点//2.说明,我们在比较时,是 和 需要删除的节点no比较public void del(int no){HeroNode temp = head;boolean flag = false;// 标志是否找到待删除节点/*如果上一个节点指向了下下一个节点,那么没有被值的节点就变成一个垃圾,被JVM回收被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收*/while (true){if ( == null){//已经到链表的最后//遍历到最后了,遍历空了break;}if ( == no){//找到待删除节点的前一个节点tempflag = true;break;}temp = ;//temp后移,遍历}//判断flagif (flag){//找到//可以删除 = ;}else {System.out.println("要删除的节点:" + no + "不存在");}}//显示链表[遍历]public void list(){//先判断链表是否为空if ( == null){System.out.println("链表为空");return;}//因为头节点不能动,因此我们需要一个辅助变量来遍历HeroNode temp = ;while (true){//判断是否到链表最后if (temp == null){break;}//输出节点的信息System.out.println(temp);//将temp后移，一定要小心，不然是死循环,输出完一个后移输出下一个。temp = ;}}
}//先定义一个HeroNode，每个HeroNode对象 就是一个节点
class HeroNode{public int no;public String nickname;public String name;public HeroNode next;//指向下一个节点//构造器public HeroNode(int no,String name,String nickname){ = no;this.name = name;this.nickname = nickname;}//为了显示方便，我们重写toString@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", nickname='" + nickname + ''' +", name='" + name + ''' +'}';}
}

单链表面试题[新浪面试题[百度面试题][腾讯面试题]单链表面试题及代码

双向链表增删改查分析图解及实现

使用带head头的双向链表实现 –水浒英雄排行榜管理单向链表的缺点分析:

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

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

示意图如下:

代码实现:

public class DoubleLinkedListDemo {public static void main(String[] args) {}}
//创建一个双向链表的类
class DoubleLinkedList {//先初始化一个头节点,头节点不要动,不存放具体的数据private HeroNodez head = new HeroNodez(0, "", "");//返回头节点public HeroNodez getHead() {return head;}/*public DoubleLinkedList(HeroNodez head) {this.head = head;}*///遍历双向链表的方法//显示链表[遍历]public void list () {//先判断链表是否为空if ( == null) {System.out.println("链表为空");return;}//因为头节点不能动,因此我们需要一个辅助变量来遍历
//        HeroNodez temp = ;HeroNodez temp = ;while (true) {//判断是否到链表最后if (temp == null) {break;}//输出节点的信息System.out.println(temp);//将temp后移，一定要小心，不然是死循环,输出完一个后移输出下一个。temp = ;}}//添加一个节点到双向链表的最后public void add(HeroNodez heroNode){//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置HeroNodez temp = head;boolean flag = false;//遍历节点找到最后while (true){//找到链表的最后if ( == null){break;}temp = ;}//退出while循环,temp就指向了链表的最后//形成一个双向链表 = heroNode;heroNode.pre = temp;}//修改一个节点的内容,可以看到双向链表的节点内容修改和前面的单向链表一样//只是节点类型改成了HeroNodezpublic void update(HeroNodez newHeroNode) {//判断是否为空if ( == null) {System.out.println("链表为空，无节点");return;}//找到需要修改的节点,根据no编号//定义一个辅助变量HeroNodez temp = ;boolean flag = false;//表示是否找到该节点while (true) {if (temp == null) {break;//已经遍历完毕,到链表的最后}if ( == ) {//找到了,就是当前我们要修改的节点flag = true;break;}temp = ;}//根据flag 判断是否找到要修改的节点if (flag) {//找到了temp.name = newHeroNode.name;temp.nickname = newHeroNode.nickname;} else { //没有找到这个节点System.out.println("没有找到编号=" +  + "的节点,不能修改。");}}//从双向链表中删除一个节点//说明//1对于双向链表,我们可以直接找到要删除的这个节点//2找到后,自我删除即可public void del(int no) {//判断当前链表是否为空if ( == null){//空链表System.out.println("链表为空,无法删除");}HeroNodez temp = ;//辅助节点(只针)boolean flag = false;// 标志是否找到待删除节点while (true) {if (temp == null){//已经找到链表最后的节点break;}if ( == no){flag = true;break;}temp = ;}if (flag){ = ;//如果是最后一个节点,就不需要指向下面这句话,否则会出现空指针异常if ( != null){temp.pre = pre;}else {System.out.println("你要删除编号为:" + no + "的节点不存在");}}}
}
class HeroNodez {public int no;public String nickname;public String name;public HeroNodez next;//指向下一个节点,默认为nullpublic HeroNodez pre;//指向前一个节点,默认为null//构造器public HeroNodez(int no, String name, String nickname) {super(); = no;this.name = name;this.nickname = nickname;}public HeroNodez() {}//为了显示方便，我们重写toString@Overridepublic String toString() {return "HeroNodez{" +"no=" + no +", nickname='" + nickname + ''' +", name='" + name + ''' +'}';}
}

环形链表介绍和约瑟夫问题

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

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

示意图说明如下

约瑟夫问题分析图解和实现

构建一个单向的环形链表思路

先创建第一个节点, 让 first 指向该节点，并形成环形

后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可.

遍历环形链表

先让一个辅助指针(变量) curBoy，指向first节点

然后通过一个while循环遍历 该环形链表即可 == first 结束

代码实现:

public class Josepfu {public static void main(String[] args) {//测试一把看看构建环形链表,和遍历是否可以指向CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();circleSingleLinkedList.addBoy(5);//加入5个小孩节点circleSingleLinkedList.showBoy();}
}
class CircleSingleLinkedList{//创建一个first节点,当前没有编号,先不要赋值private Boy first = null;//添加小孩节点,构建成一个环形的链表public void addBoy(int nums){//nums 做一个数据校验if(nums < 1){System.out.println("nums的值不正确");return;}Boy curBoy = null;//辅助指针,帮助构建环形链表//使用for来创建我们的环形链表for (int i = 1; i <= nums; i++) {//根据编号,创建小孩节点Boy boy = new Boy(i);//如果是第一个小孩if (i == 1){first = boy;first.setNext(first);curBoy = first;}else {curBoy.setNext(boy);//构建第一条线boy.setNext(first);//构建循环线curBoy = boy;//curBoy指向新添加的节点}}}//遍历当前的环形链表public void showBoy(){//判断链表是否为空if (first == null){System.out.println("没有小孩");return;}//因为first不能动,因此需要一个辅助指针完成遍历Boy curBoy = first;while (true){System.out.println("小孩的编号:" + No());if (Next() == first){//说明已经遍历完毕,下一个已经指向头节点break;}curBoy = Next();//curBoy后移}}
}
//创建一个Boy类,表示一个节点
class Boy{private int no;//编号private Boy next;//指向下一个节点,默认nullpublic Boy(int no){ = no;}public int getNo() {return no;}public void setNo(int no) { = no;}public Boy getNext() {return next;}public void setNext(Boy next) { = next;}
}

根据用户的输入，生成一个人物出圈的顺序

n = 5, 即有5个人

k = 1, 从第一个人开始报数

m = 2, 数2下

需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点. 补充： 人物报数前，先让 first 和 helper
移动 k - 1次

当人物报数时，让first 和 helper 指针同时 的移动 m - 1 次

这时就可以将first 指向的人物节点 出圈
first = first .next

< = first

原来first 指向的节点就没有任何引用，就会被回收

代码实现:

public class Josepfu {public static void main(String[] args) {//测试一把看看构建环形链表,和遍历是否可以指向CircleSingleLinkedList circ = new CircleSingleLinkedList();circ.addBoy(5);//加入5个小孩节点circ.showBoy();untBoy(1, 2, 5);}
}//创建一个环形的单向链表
class CircleSingleLinkedList{//创建一个first节点,当前没有编号,先不要赋值private Boy first = null;//添加小孩节点,构建成一个环形的链表public void addBoy(int nums){//nums 做一个数据校验if(nums < 1){System.out.println("nums的值不正确");return;}Boy curBoy = null;//辅助指针,帮助构建环形链表//使用for来创建我们的环形链表for (int i = 1; i <= nums; i++) {//根据编号,创建小孩节点Boy boy = new Boy(i);//如果是第一个小孩if (i == 1){first = boy;first.setNext(first);curBoy = first;}else {curBoy.setNext(boy);//构建第一条线boy.setNext(first);//构建循环线curBoy = boy;//curBoy指向新添加的节点}}}//约瑟夫问题实现public void countBoy(int k,int m,int nums){if (first == null || k<1 || k > nums){System.out.println("数据输入有误,请重新输入");return;}Boy helper = first;while(true) {if (Next() == first) {break;//现在helper已经是最后一个节点}helper = Next();}//人物报数前先让first和helper移动k-1次for (int j = 0; j < k - 1; j++) {first = Next();helper = Next();}//当人物报数时,让first和helper指针同时移动m-1次//通过循环,圈中只剩下一个节点while (true){if (helper == first){break;}for (int j = 0; j < m - 1; j++) {first = Next();helper = Next();}System.out.println("编号为:" + No() + "的学生出局");first = Next();helper.setNext(first);}System.out.println("最后剩的小孩编号为:" + No());}//遍历当前的环形链表public void showBoy(){//判断链表是否为空if (first == null){System.out.println("没有小孩");return;}//因为first不能动,因此需要一个辅助指针完成遍历Boy curBoy = first;while (true){System.out.println("小孩的编号:" + No());if (Next() == first){//说明已经遍历完毕,下一个已经指向头节点break;}curBoy = Next();//curBoy后移}}
}//创建一个Boy类,表示一个节点
class Boy{private int no;//编号private Boy next;//指向下一个节点,默认nullpublic Boy(int no){ = no;}public int getNo() {return no;}public void setNo(int no) { = no;}public Boy getNext() {return next;}public void setNext(Boy next) { = next;}
}