Java数据结构与算法-java数据结构与算法（一）https://developer.aliyun.com/article/1469487
链表
链表(Linked List)介绍 :
链表是有序的列表，但是它在内存中是存储如下
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含 data 域， next 域：指向下一个节点.
- 如图：发现链表的各个节点不一定是连续存储.
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
单向链表
单向链表存储节点思路图
单链表的应用实例
使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作
我们都知道 水浒传里有108位英雄吧
我们这里随便举例四个，我们想用链表的方式把他们放入我们的英雄榜里（单向链表）
新增，修改，删除的思路
添加英雄:
根据排名将英雄插入到指定位置(如果有这个排名，则添加失败，并给出提示) 思路的分析示意图:
修改节点功能
古时候，有武功的人士逗喜欢为了排名去争斗，所以我们制作英雄榜需要有更换排名的功能
排名是固定的，他的下一名也是固定的 我们要修改的只有当前占有排名的人和昵称即可
- 先找到该节点，通过遍历，
- temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname
删除节点
这个功能呢可以理解为，有英雄不想争夺排名了，退休回家种田耕地享受生活了，我们需要把不需要位置的英雄占有的位置腾出来。
单向链表的增删改查
/** * @projectName: DataStructure * @package: com.hyc.DataStructure.LinkedList * @className: LinkedlistDemo * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/17 16:24 * @version: 1.0 */ public class LinkedlistDemo { public static void main(String[] args) { // 设置一些英雄对象 HeroNode heroNode = new HeroNode(1, "宋江", "及时雨"); HeroNode heroNode1 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode heroNode2 = new HeroNode(3, "吴用", "智多星"); HeroNode heroNode3 = new HeroNode(4, "林冲", "豹子头"); // 声明单向链表 SingleLinkedlist linkedlist = new SingleLinkedlist(); //加入我们的英雄节点 //linkedlist.add(heroNode); //linkedlist.add(heroNode1); //linkedlist.add(heroNode2); //linkedlist.add(heroNode3); //加入按照编号 linkedlist.addByOrder(heroNode); linkedlist.addByOrder(heroNode3); linkedlist.addByOrder(heroNode2); linkedlist.addByOrder(heroNode1); //输出节点信息 linkedlist.List(); System.out.println("更新数据后"); linkedlist.updateNode(new HeroNode(1, "冷环渊", "编码大师")); //输出节点信息 linkedlist.List(); System.out.println("删除数据后输出"); linkedlist.DeleteNode(1); linkedlist.List(); } } class SingleLinkedlist { //创建一个头结点 HeroNode head = new HeroNode(0, "", ""); //加入链表 public void add(HeroNode node) { //头节点不能动 这里我们用一个临时指针来记录 HeroNode temp = head; //遍历链表 while (true) { //遍历为空就代表找了最后一个节点 //不为空就后移一位继续找 if (temp.next == null) { break; } //没有找到最后就后移 temp temp = temp.next; } //跳出while证明找到了最后的节点，将我们的新节点加入到最后的节点的next即可 temp.next = node; } //添加节点 第二种方法 public void addByOrder(HeroNode node) { /* * 因为头结点不能动，我们通过指针来记录头节点来帮助找到添加的位置 *因为是单链表我们找的是 Temp是位于添加位置的前一个节点，否则插入不了 * */ //创建一个临时变量 HeroNode temp = head; //用来标识 英雄是否存在 默认为不存在（false） boolean flag = false; while (true) { //找到最后为空的位置 if (temp.next == null) { break; } //如果temp的下一个no 大于 我们加入的节点，就往temp加入 if (temp.next.No > node.No) { break; } //如果下一个节点等于 加入节点的No 那么就代表已经存在了节点 else if (temp.next.No == node.No) { //将flag 修改为 true 代表已经存在 flag = true; break; } //如果上面的都没达成就代表当前节点位置不对，向后继续遍历 temp = temp.next; } // 判断 flag的值 if (flag) { //如果为 true 代表节点已经存在 System.out.printf("当前节点%d已经存在了，不能加入\n", node.No); } else { // 如果为false 那代表符合插入条件并且不存在与当前链表 node.next = temp.next; temp.next = node; } } //修改节点信息 public void updateNode(HeroNode newHeroNode) { if (head.next == null) { System.out.println("链表是空的"); } //这里是头节点不能修改，我用 temp 来指向头结点 HeroNode temp = head.next; // 是否找到了no的标识 boolean flag = false; while (true) { //找到最后一个 if (temp == null) { break; } if (temp.No == newHeroNode.No) { //如果等于 那么代表可以修改 flag = true; break; } temp = temp.next; } if (flag) { // true 修改信息 temp.NickName = newHeroNode.NickName; temp.Name = newHeroNode.Name; } else { System.out.printf("没有找到 %d 这个节点", newHeroNode.No); } } //删除节点信息 public void DeleteNode(int no) { HeroNode temp = head; // 用来标注 是不是可以删除 boolean flag = false; while (true) { if (temp.next == null) { break; } if (temp.next.No == no) { flag = true; break; } temp = temp.next; } //根据flag 删除Node if (flag) { //找到的话就删除，这里我们只需要指向空 GC会回收 temp.next = temp.next.next; } else { System.out.printf("要删除的 %d 没有找到", no); } } //遍历链表 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.next; } } } /** * 编写 水浒传英雄 节点 * 用于存放每个英雄的属性 * */ class HeroNode { //排名 public int No; // 姓名 public String Name; //昵称 public String NickName; // 下一个是哪位好汉 public HeroNode next; public HeroNode(int hNo, String hName, String hNickName) { this.No = hNo; this.Name = hName; this.NickName = hNickName; } //方便输出语句输出 @Override public String toString() { return "HeroNode{" + "No=" + No + ", Name='" + Name + '\'' + ", NickName='" + NickName + '\'' + '}'; } }
链表使用效果
总结
我们这次制作了属于自己的英雄榜（单向链表）,我们收货了什么呢？
- 节点之间联系的思路
- 逐渐适应数据结构的一些思想
- 动手实操实现的习惯
单向链表各大厂面试题
新浪
/** * @author 冷环渊 Doomwatcher * @context: * 新浪链表面试题 查找链表中的第k个节点 * 思路： * 1.编写一个方法，接收head 节点，同时接收一个index * 2，index表示的是倒数第index 个节点 * 3. 先把链表从头到尾遍历 得到链表的总长度 getlength * 4。得到Size之后 我们从链表的第一个开始遍历（Size-index）个，就可以得到 * 5. 如果找到了 则返回该节点否则返回null * @date: 2021/12/18 15:12 * @param head * @param index * @return: com.hyc.DataStructure.LinkedList.HeroNode */ public static HeroNode getLastIndexNode(HeroNode head, int index) { // 如果除去头节点之后没有新的节点就代表链表是空的，返回空对象 if (head.next == null) { return null; } // 获取到链表的长度 int Size = SingleLinkedlist.getlength(head); //声明一个零时变量指向第一个有效的节点 HeroNode cur = head.next; //假设 我们的例子是一共有三个有效节点 3 这里我们index 为 2 那么3-2 = 1 找到了倒数第二个的节点 for (int i = 0; i < Size - index; i++) { cur = cur.next; } //找到节点之后我们直接返回即可 return cur; }
腾讯
/** * @author 冷环渊 Doomwatcher * @context: 腾讯面试题 反转链表 * 思路: * 1.先定义一个节点 reverseHead = new HeroNode(); * 2.从头遍历原来的链表，每次遍历一个节点就将其取出并且放到信的链表的最前端， * 3.原来的链表head.next = reverseHead.Next * @date: 2021/12/18 15:38 * @param head * @return: void */ public static void reverseList(HeroNode head) { if (head.next == null || head.next.next == null) { return; } //需要新的一个空的头 HeroNode reverseHead = new HeroNode(0, "", ""); // 获得第一个有效的节点 HeroNode cur = head.next; //指向[cur]的下一个的节点 HeroNode next = null; while (cur != null) { //保存当前的节点的下一个位置 有用 next = cur.next; // 将cur的下一个指向 新的链表的最前端 cur.next = reverseHead.next; //将新链表的最前端为cur reverseHead.next = cur; //cur 继续向后遍历 cur = next; } head.next = reverseHead.next; }
百度
/** * @author 冷环渊 Doomwatcher * @context: 百度面试题， 在不破坏链表结构的情况下 反向输出链表 * 这里我们利用 一个 即将学到的 数据结构叫 栈 * 栈结构的特点就是 先进后出 * 将链表的节点按顺序遍历压入栈 * 利用栈先进后出的特质，就可以保证性能的情况下输出不改变结构的倒序链表 * @date: 2021/12/19 13:48 * @param * @return: void */ public static void showreverseList(HeroNode node) { if (node.next == null) { return; } Stack<HeroNode> stack = new Stack<>(); HeroNode cur = node.next; while (cur != null) { stack.push(cur); cur = cur.next; } while (stack.size() > 0) { System.out.println(stack.pop()); } }
课后练习
/** * @author 冷环渊 Doomwatcher * @context: 合并两个链表 并且有序 * @date: 2021/12/19 14:15 * @param list1 * @param list2 * @return: com.hyc.DataStructure.LinkedList.SingleLinkedlist */ public static HeroNode mergeList(HeroNode list1, HeroNode list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } HeroNode head = new HeroNode(0, "", ""); HeroNode temp = head; while (list1 != null && list2 != null) { if (list1.No < list2.No) { temp.next = list1; list1 = list1.next; } else { temp.next = list2; list2 = list2.next; } temp = temp.next; } if (list1 == null) { temp.next = list2; } if (list2 == null) { temp.next = list1; } return head.next; }
双向链表
双向链表应用实例,双向链表的操作分析和实现
管理单向链表的缺点分析:
- 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
- 向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
- 分析了双向链表如何完成遍历，添加，修改和删除的思路
双向链表实现思路
分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现
- 遍历 方和 单链表一样，只是可以向前，也可以向后查找
- 添加 (默认添加到双向链表的最后)
- (1) 先找到双向链表的最后这个节点
- (2) temp.next = newHeroNode
- newHeroNode.pre = temp;
- 修改 思路和 原来的单向链表一样. 4) 删除
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如 temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
实现链表节点
/** * 双向链表要用的节点 * */ class ListNode { //排名 public int No; // 姓名 public String Name; //昵称 public String NickName; // 下一个节点 public ListNode next; //上一个节点 public ListNode pre; public ListNode(int hNo, String hName, String hNickName) { this.No = hNo; this.Name = hName; this.NickName = hNickName; } //方便输出语句输出 @Override public String toString() { return "HeroNode{" + "No=" + No + ", Name='" + Name + '\'' + ", NickName='" + NickName + '\'' + '}'; } }
双向链表实现
class DoubleLinkedList { //创建一个头结点 ListNode head = new ListNode(0, "", ""); public ListNode getHead() { return head; } public void setHead(ListNode head) { this.head = head; } //遍历链表 public void List() { if (head.next == null) { System.out.println("链表为空"); return; } //头节点不能动 这里我们用一个临时指针来记录 ListNode temp = head.next; while (true) { //遍历为空就代表找了最后一个节点 if (temp == null) { break; } //输出节点 System.out.println(temp); //后移一位 temp = temp.next; } } //加入双向链表 public void add(ListNode node) { //头节点不能动 这里我们用一个临时指针来记录 ListNode temp = head; //遍历链表 while (true) { //遍历为空就代表找了最后一个节点 //不为空就后移一位继续找 if (temp.next == null) { break; } //没有找到最后就后移 temp temp = temp.next; } //指向下一个节点 temp.next = node; //指向上一个节点 node.pre = temp; } //修改双向链表，和单向链表基本一致不需要过多的修改 //修改节点信息 public void updateNode(ListNode newlistnode) { if (head.next == null) { System.out.println("链表是空的"); } //这里是头节点不能修改，我用 temp 来指向头结点 ListNode temp = head.next; // 是否找到了no的标识 boolean flag = false; while (true) { //找到最后一个 if (temp == null) { break; } if (temp.No == newlistnode.No) { //如果等于 那么代表可以修改 flag = true; break; } temp = temp.next; } if (flag) { // true 修改信息 temp.NickName = newlistnode.NickName; temp.Name = newlistnode.Name; } else { System.out.printf("没有找到 %d 这个节点", newlistnode.No); } } /* * 双向链表删除 * 对于双向链表来说就不需要找到上一个节点来删除了， * 可以找到自己删除 * */ public void DeleteNode(int no) { if (head.next == null) { System.out.println("链表为空 不需要删除"); return; } ListNode temp = head.next; // 用来标注 是不是可以删除 boolean flag = false; while (true) { if (temp == null) { break; } if (temp.next.No == no) { flag = true; break; } temp = temp.next; } //根据flag 删除Node if (flag) { //找到的话就删除，这里我们只需要指向空 GC会回收 //temp.next = temp.next.next; 原先的单向链表删除现在在双向链表里就不好使了 /*将当前节点的上一个节点的下一个指向 指向当前节点的下一个节点 相当于向前指向的next 直接跨过当前的节点指向下一个节点*/ temp.pre.next = temp.next; /*将当前节点的下一个节点的上一个指向 指向当前节点的上一个节点，相当于向前的pre 直接快过当前的节点指向上一个 * 如果当前节点是最后一节点，就不执行后面这个将下一个节点的指向更改，不然会出现空指针 * */ if (temp.next != null) { temp.next.pre = temp.pre; } /*这两步 坐完相当于 此时的当前节点已经没有了指向 会被回收*/ } else { System.out.printf("要删除的 %d 没有找到", no); } } }
总结
双向链表在之前的基础上：
- 对比单向链表 双向链表可以自己删除，
- 双线链表正反遍历更加的容易
环形链表
认识单向环形链表
这里我们以单向环形链表为例子
就是我们最后一个节点的next域指向头结点，形成闭环
引用场景以及问题
Josephu(约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由
此产生一个出队编号的序列。
思路提示：
提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结 点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直 到最后一个结点从链表中删除算法结束。
Josephu 问题解题思路
认识约瑟夫问题，以及我们想要实现的场景，
- 编写实现 单向环形链表
- 约瑟夫问题的要求 根据区间报数 报数的小孩出列
- coding 出我们需要的需求
实现单向循环链表
思路
大体上和我们的单向链表有雷同的地方，区别在于：
- 我们需要在创建链表的时候将尾结点的最后一个指向头结点，这也就意味着我们需要有至少两个指针来记录头尾节点。
- 遍历的方式也要有些许的变化，结束循环的条件从
head.next = null改变成CurBoy.next(指向尾部节点的指针) = first;最后为头节点的时候遍历为第二个
我们简单的先创建一个实现链表需要的节点对象
约瑟夫问题环形链表的节点
//环形链表 约瑟夫问题 节点 class Boy { private int No; private Boy Next; public Boy(int no) { this.No = no; } public int getNo() { return No; } public void setNo(int no) { No = no; } public Boy getNext() { return Next; } public void setNext(Boy next) { Next = next; } }
创建环形链表对象实现生成链表和遍历链表，以及解决约瑟夫问题的方（具体的实现思路见代码注释）
// 环形单向链表 class CircleSingleLinkeList { Boy first = null; /** * @author 冷环渊 Doomwatcher * @context: 一个环形链表 参数是这个链表有多少节点 * @date: 2021/12/21 15:47 * @param nums * @return: void */ public void CreateListNode(int nums) { if (nums < 1) { System.out.println("无法开始游戏，因为链表小于最小的游戏节点数量"); return; } // 创建一个 辅助之间用于遍历和指向节点 Boy curBoy = null; 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; } } } public void showListBoy() { if (first == null) { System.out.println("链表为空，不能遍历"); return; } // frist 节点不能移动 我们创建一个指针 Boy curboy = first; while (true) { System.out.printf("小孩的编号是： %d \n", curboy.getNo()); // 说明已经遍历完毕 if (curboy.getNext() == first) { break; } //后移 curboy curboy = curboy.getNext(); } } /** * @author 冷环渊 Doomwatcher * @context: 这里我们以小孩做游戏来解决约瑟夫问题， * @date: 2021/12/22 21:16 * @param nums 一共有多少个小孩 * @param start 从那个小孩开始报数 * @param index 每隔几个小孩报数一次 * @return: void */ public void JosephuFunc(int nums, int start, int index) { if (first == null || start < 1 || start > nums) { System.out.println("参数不对，请重新输入参数"); return; } Boy helper = first; //将 helper遍历到最后一个节点 while (true) { if (helper.getNext() == first) { break; } helper = helper.getNext(); } // 小孩子 报数之前，要遍历指针到从start开始的小孩的节点 for (int i = 0; i < start - 1; i++) { first = first.getNext(); helper = helper.getNext(); } //当小孩报数的时候 让 first和helper 同时移动m-1次 然后出圈 //这里循环操作 知道圈中的一个节点 while (true) { //说明列表只有一个节点 if (helper == first) { break; } //循环之后将 指针后移 for (int i = 0; i < index - 1; i++) { first = first.getNext(); helper = helper.getNext(); } // 这个时候 first选中的节点就是要出圈的小孩 System.out.printf("小孩 %d 出圈\n", first.getNo()); //出圈操作 first = first.getNext(); helper.setNext(first); } System.out.printf("最后剩下的小孩 %d \n", first.getNo()); } }
实现结果
Java数据结构与算法-java数据结构与算法（三）https://developer.aliyun.com/article/1469491
