数据结构（Java）学习笔记——知识点：单链表、双向链表、约瑟夫问题

数据结构（Java）学习笔记——知识点：单链表、双向链表、约瑟夫问题

数据结构（Java）学习笔记——知识点：单链表、双向链表、约瑟夫问题

• 四、单链表
• • 1、单链表基本概述
  • 2、单链表实例
  • • 目标需求
    • 具体思路
    • 代码实现
    • 运行结果
    • 继续完善（添加节点的修改功能）
    • • 主函数测试代码
      • 修改方法体代码
      • 运行结果
    • 继续完善（添加节点的删除功能）
    • • 具体思路
      • 主函数测试代码
      • 删除方法体代码
      • 运行结果
  • 3、常见面试题
  • • 1）求单链表中有效节点的个数
    • 2）查找单链表中倒数第k个节点（新浪）
    • 3）单链表的反转（腾讯）
    • 4）从头到尾打印单链表（百度）
    • • ａ、反向遍历
      • ｂ、Stack 栈
    • 5）合并两个有序的链表，合并之后依然有序。（课后作业）
• 五、双向链表
• • 1、双向链表概述
  • 2、双向链表实例
  • • 代码实现
    • 运行结果
• 六、Josephu问题（约瑟夫问题）(循环链表)
• • 1、Josephu问题概述
  • 2、Josephu问题示意图
  • 3、Josephu问题代码书写
  • • 添加操作的思路
    • 添加操作的代码实现
    • 继续完善出队的操作
    • 继续完善出队的代码
    • 运行结果

四、单链表

1、单链表基本概述

 1）链表是以节点的方式进行存储的。
　2）链表的每个节点包括 data 域、next 域，next 域指向下一个节点。
　3）链表的存储在内存上是不一定连续的。
　4）链表分为两个不同的种类：带头结点的和不带投节点的。

 单链表的逻辑结构图

2、单链表实例

目标需求

 使用带有头节点的单向链表实现——水浒英雄排行榜管理：
　1）完成对英雄的增删改查操作。
　2）实现添加英雄时从尾部添加。
　3）实现添加英雄时根据英雄排名插入到指定位置。

具体思路

 1）从尾部添加!

2）根据排名，从指定位置添加，如果已经存在提示错误信息
　

代码实现

 1）从尾部添加

package com.database.linkedList;public class SingleLinkedListDemo {public static void main(String[] args) {//手动插入数据SingleLinkedList singleLinkedList = new SingleLinkedList();singleLinkedList.add(new HeroNode(1,"宋江","及时雨"));singleLinkedList.add(new HeroNode(2,"卢俊义","玉麒麟"));singleLinkedList.add(new HeroNode(3,"吴用","智多星"));singleLinkedList.add(new HeroNode(4,"林冲","豹子头"));singleLinkedList.add(new HeroNode(5,"鲁智深","花和尚"));//查询链表singleLinkedList.list();}
}//定义SingleLinkedList,来管理英雄
class SingleLinkedList {//初始化一个头节点，头节点就不动了,不存放数据private HeroNode head = new HeroNode(0,"","");//添加节点到单链表//思路：不考虑编号的顺序时//1、找到当前链表的最后一个节点//2、将最后的节点的next指向新的节点public void add(HeroNode node) {//遍历链表,寻找最后一个节点HeroNode temp = head;//先定义一个变量指向头节点while(true){//如果节点的next域指向为空，那么终止循环 == null){break;}temp = ;//如果没找到最后，就移动到下一个位置。} = node;//将最后一个节点的next域指向新插入的这个节点。}//显示链表public void list() {//判断链表是否为空 == null){System.out.println("链表为空");return;}//遍历链表HeroNode temp = ;//定义一个变量指向头节点while(true){//如果节点的next域指向为空，那么终止循环if(temp == null){break;}System.out.println(temp);//自动调用toString方法temp = ;//向后移动}}
}//创建一个HeroNode，每个HeroNode就是一个节点
class HeroNode {public int no;//英雄编号public String name;//英雄名字public String nickname;//英雄昵称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 +", name='" + name + ''' +", nickname='" + nickname + ''' +'}';}
}

 2）根据排名，从指定位置添加，如果已经存在提示错误信息
  变量定义变更

		//第二种方式插入数据singleLinkedList.addByOrder(new HeroNode(1,"宋江","及时雨"));singleLinkedList.addByOrder(new HeroNode(4,"林冲","豹子头"));singleLinkedList.addByOrder(new HeroNode(3,"吴用","智多星"));singleLinkedList.addByOrder(new HeroNode(2,"卢俊义","玉麒麟"));singleLinkedList.addByOrder(new HeroNode(5,"鲁智深","花和尚"));singleLinkedList.addByOrder(new HeroNode(2,"卢俊义","玉麒麟"));//查询链表singleLinkedList.list();

  add方法变更

	//第二种添加方式,将英雄添加到指定位置public void addByOrder(HeroNode node){//遍历链表,寻找要添加位置的前一个节点HeroNode temp = head;//先定义一个变量指向头节点boolean flag = false;//定义一个标志，用来表示节点是否已经存在while(true){//如果节点的next域指向为空，那么终止循环 == null) {break;}//如果下一个节点的编号大于新节点的编号，那么就停止循环，直接插入数据o > ){break;} else if ( == ) {//如果编号已经存在，那么也要终止循环flag = true;break;}temp = ;//如果以上三个步骤都不满足，就移动到下一个位置。}if (flag == true){System.out.println("插入节点失败!" + temp + ",该节点已经存在了");}else{ = ; = node;System.out.println("插入节点成功！");}}

运行结果

 1）从尾部添加

 2）根据排名，从指定位置添加，如果已经存在提示错误信息

继续完善（添加节点的修改功能）

 添加修改节点的功能

主函数测试代码

	//修改一个数据singleLinkedList.update(new HeroNode(4,"林冲","豹子头111"));//查询链表singleLinkedList.list();

修改方法体代码

//修改节点信息，根据no来进行修改public void update(HeroNode newnode) {HeroNode temp = head;//先定义一个变量指向头节点boolean flag = false;//定义一个标志，用来表示节点是否已经存在//判断链表是否为空 == null){System.out.println("链表为空");return;}//遍历链表,找到要修改的那个节点编号while(true){//当循环到结尾的时候跳出循环 == null){break;} == ){flag = true;//查找到了这个节点break;}temp = ;//指针后移}if (flag == true){temp.name = newnode.name;temp.nickname = newnode.nickname;System.out.println("修改节点成功！");}else{System.out.println("未查找到该节点！");}}

运行结果

继续完善（添加节点的删除功能）

 添加根据节点编号来删除节点的功能

具体思路

主函数测试代码

//删除一个数据singleLinkedList.delete(2);singleLinkedList.delete(3);//查询链表singleLinkedList.list();

删除方法体代码

//删除节点，根据no来删除public void delete(int no){HeroNode temp = head;//先定义一个变量指向头节点boolean flag = false;//定义一个标志，用来表示节点是否已经存在//判断链表是否为空 == null){System.out.println("链表为空");return;}while(true){//当循环到结尾的时候跳出循环 == null){break;}//查找到匹配的no号o == no){flag = true;break;}temp = ;}if(flag == true){System.out.println("找到了要删除的节点！"); = ;}else{System.out.println("未查找到该节点！");}}

运行结果

3、常见面试题

1）求单链表中有效节点的个数

 这个就十分的简单了，在遍历节点的过程中，定义一个变量去接受遍历的节点的个数就行了，就是要注意一点，不能包含头节点，头节点不是有效节点。直接上代码：

//统计有效节点的个数public void getHeroNodeNumber(){HeroNode temp = head;//定义一个变量指向头节点int count = 0;while(true){//当循环到结尾的时候跳出循环 == null){break;}temp = ;//指针后移count++;}System.out.println("有效节点数为：" + count);}

2）查找单链表中倒数第k个节点（新浪）

 这个开始上难度了。要先遍历一遍链表，用 count 统计一下一共有多少个节点。之后再用 count - k 来找到倒数第k个节点的 no 值，输出该节点即可。

 	//查找链表中倒数第k个节点的信息public HeroNode getHeroNodeFromLast(int k){HeroNode temp = head;//定义一个变量指向头节点int count = 0;while(true){//当循环到结尾的时候跳出循环 == null){temp = head;break;}temp = ;//指针后移count++;}for(int i = 0; i <= count - k ; i++){temp = ;}return temp;}

3）单链表的反转（腾讯）

 这个题稍微又上了点难度，但是深度思考一下就能想到，再定义一个链表啊，这样从老链表的前面开始取到节点，再主意放到新链表的头节点后面。这样再按照顺序输出就是倒序了。

 主函数调用

//单链表反转输出System.out.println("反转后的链表为：");Head());singleLinkedList.list();

 方法体

	//单链表的反转public static void reserveList(HeroNode head){HeroNode cur = ;HeroNode next = null;HeroNode reserveHead = new HeroNode(0,"","");while(cur != null){next = ; = ; = cur;cur = next;} = ;}

4）从头到尾打印单链表（百度）

 要求使用两种方式。

ａ、反向遍历

 先把链表反转，再按照顺序遍历，这样会破坏链表结构，不推荐使用。

ｂ、Stack 栈

 这个就非常巧妙了，利用栈这个数据结构，将各个节点压栈，然后利用栈的先进后出的特点，就实现了逆序打印。

	//压入栈Stack<HeroNode> stack = new Stack();stack.add(new HeroNode(1,"宋江","及时雨"));stack.add(new HeroNode(4,"林冲","豹子头"));stack.add(new HeroNode(3,"吴用","智多星"));stack.add(new HeroNode(2,"卢俊义","玉麒麟"));stack.add(new HeroNode(5,"鲁智深","花和尚"));System.out.println("使用出栈的方式，输出数据！");while(stack.size() > 0){System.out.println(stack.pop());}

5）合并两个有序的链表，合并之后依然有序。（课后作业）

五、双向链表

1、双向链表概述

 单链表只能按照一个方向查找，而双向链表可以向前或向后查找。
 单链表不能自我删除，需要中间变量，而双向链表可以自我删除。
 双向链表多了一个指向前一个节点的 pre

 双向链表各种思路

2、双向链表实例

 将单链表中，英雄排行的例子，改成双向链表实现。

代码实现

package com.database.linkedList;public class DoubleLinkedListDemo {public static void main(String[] args) {DoubleLinkedList doubleLinkedList = new DoubleLinkedList();doubleLinkedList.addNode(new HeroNode_Double(1,"宋江","及时雨"));doubleLinkedList.addNode(new HeroNode_Double(2,"卢俊义","玉麒麟"));doubleLinkedList.addNode(new HeroNode_Double(3,"吴用","智多星"));doubleLinkedList.addNode(new HeroNode_Double(4,"林冲","豹子头"));doubleLinkedList.addNode(new HeroNode_Double(5,"鲁智深","花和尚"));System.out.println("初始链表：");//输出查看一下doubleLinkedList.list();System.out.println("删除后的链表：");doubleLinkedList.deleteNode(3);//输出查看一下doubleLinkedList.list();System.out.println("修改后的链表：");doubleLinkedList.updateNode(new HeroNode_Double(4,"林冲","豹子头aaa"));//输出查看一下doubleLinkedList.list();}
}class DoubleLinkedList {HeroNode_Double head = new HeroNode_Double(0,"","");public void addNode(HeroNode_Double node){HeroNode_Double temp = head;while(true){ == null){ = node;node.pre = temp;System.out.println("插入节点成功！");break;}temp = ;}}public void deleteNode(int no){HeroNode_Double temp = head;boolean flag = false; == null){System.out.println("链表为空！");}while(true){ == null){break;} == no){flag = true;break;}temp = ;}if(flag){ = ; != null){pre = temp.pre;//如果是最后一个节点，会出现空指针异常，所以要加上一个if判断}System.out.println("链表删除成功！");}else{System.out.println("要删除的节点不存在！");}}public void updateNode(HeroNode_Double newnode){HeroNode_Double temp = head;//先定义一个变量指向头节点boolean flag = false;//定义一个标志，用来表示节点是否已经存在//判断链表是否为空 == null){System.out.println("链表为空");return;}while(true){//当循环到结尾的时候跳出循环 == null){break;} == ){flag = true;//查找到了这个节点break;}temp = ;//指针后移}if (flag == true){temp.name = newnode.name;temp.nickname = newnode.nickname;System.out.println("修改节点成功！");}else{System.out.println("未查找到该节点！");}}public void list(){HeroNode_Double temp = ;while(true){ == null){break;}System.out.println(temp);temp = ;}}
}class HeroNode_Double {public int no;public String name;public String nickname;public HeroNode_Double next;//下一个节点public HeroNode_Double pre;//上一个节点//构造方法public HeroNode_Double(int no, String name, String nickname){ = no;this.name = name;this.nickname = nickname;}//为显示方便，重写toString方法@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + ''' +", nickname='" + nickname + ''' +'}';}
}

 值得注意的是，在删除操作的时候，也就是在执行

语句时，如果删除到了只剩最后一个节点的时候&# 为 null，所以 pre 会爆空指针异常错误。此时需要用一个if语句，进行判断，判断要删除的节点是否为最后一个节点。
 
运行结果
 
 
六、Josephu问题（约瑟夫问题）(循环链表)
 
1、Josephu问题概述
 
 
2、Josephu问题示意图
 
 例：总共有5个人，数到2的人出队列，出队列后将该出队的节点的前后节点相连。并且从下一个节点开始，又从1开始数。以此类推，直到所有节点都出列。示意图如下：
 

 　
 　由此可知，出队的顺序为：2 -> 4 -> 1 -> 5 -> 3
 
3、Josephu问题代码书写
 
添加操作的思路
 
 
添加操作的代码实现
 
package com.database.linkedList;public class CircleLinkedListDemo {public static void main(String[] args) {circlelinkedlist circlelinkedlist = new circlelinkedlist();//添加数据(添加5个小孩节点)circlelinkedlist.addKids(5);System.out.println("一共有" + NodeNumber() + "个有效节点。");circlelinkedlist.list();}
}class circlelinkedlist {private kidNode first = new kidNode(0);public void addKids(int nums) {//如果插入的数据小于1则表示不能插入if(nums < 1){System.out.println("nums的值不正确！");return ;}kidNode curNode = null;//定义一个辅助指针//使用for循环来创建环形链表for(int i = 1; i <= nums; i++){//根据编号创建节点kidNode kidNode = new kidNode(i);//如果是第一个小孩if(i == 1){first =  = first;//指向自己curNode = first;//curNode也指向自己}else{ =  = first;curNode = kidNode;}}
}public void list(){kidNode curnode = first;while(true){ == first){break;}System.out.println(curnode);curnode = ;}System.out.println(curnode);}public int getNodeNumber(){kidNode curnode = first;int count = 0;while(true){ == first){break;}count++;curnode = ;}return ++count;}
}class kidNode{public int no;public kidNode next;public kidNode(int no){ = no;}public int getNo(){return no;}@Overridepublic String toString() {return "kidNode{" +"no=" + no +'}';}
}
 
继续完善出队的操作
 
 
继续完善出队的代码
 
/*** @Author: Cui* @Description:* @DateTime:  15:40* @Params: n:一共有多少人。k:从第几个人开始报数。m:一次数几下。* @Return */public void outKids(int n, int k, int m){//先定义一个辅助指针变量helper，事先指向环形链表的最后这个节点。kidNode helper = first;for(int i = 1; i < n; i++){helper = ;}while (true){//小孩开始报数的时候，先将helper和first移动k-1次。for(int i = 0; i < k-1; i++){first = ;helper = ;}//开始数数for(int i = 0; i < m-1; i++){first = ;helper = ;}//出队System.out. + "号小朋友出队!");first = ; = first;//设置一个终止循环的条件if ( == first){System.out. + "号小朋友出队!"); = null;break;}}}
 
运行结果