链表

1 链表

链表是一种物理存储单元上非连续 
    
    
    、非顺序的存储结构    
    
    
，数据元素的逻辑顺序是通过链表中的指针链接实现的    
    
    
。

2 单链表

商品结点类 package com.acti.linkedList; /** * author hongyeci * date 20220722 * version 1.0 * remark 单链表--商品类 */ public class GoodsNode { private int goodsId; private String goodsName; private double goodsPrice; private GoodsNode next; public GoodsNode() { } public GoodsNode(int goodsId, String goodsName, double goodsPrice) { this.goodsId = goodsId; this.goodsName = goodsName; this.goodsPrice = goodsPrice; } public int getGoodsId() { return goodsId; } public void setGoodsId(int goodsId) { this.goodsId = goodsId; } public String getGoodsName() { return goodsName; } public void setGoodsName(String goodsName) { this.goodsName = goodsName; } public double getGoodsPrice() { return goodsPrice; } public void setGoodsPrice(double goodsPrice) { this.goodsPrice = goodsPrice; } public GoodsNode getNext() { return next; } public void setNext(GoodsNode next) { this.next = next; } @Override public String toString() { return "GoodsNode{" + "goodsId=" + goodsId + ", goodsName=" + goodsName + \ + ", goodsPrice=" + goodsPrice + ", next=" + next + }; } } 带有头结点的单链表 package com.acti.linkedList; /** * author hongyeci * date 20220722 * version 1.0 * remark 带有头结点的单链表 */ public class SingleLinkedList { private GoodsNode node = new GoodsNode(0,"头结点",0.0); /** * 增加结点-添加到末尾结点 * @param goodsNode 商品结点 */ public void addNode(GoodsNode goodsNode){ GoodsNode temp = node; while(true){ if (temp.getNext() == null){ break; } temp=temp.getNext(); } temp.setNext(goodsNode); } /** * 指定位置插入值 * 按照商品id值顺序插入到链表中 * @param goodsNode */ public void insertNode(GoodsNode goodsNode){ GoodsNode temp = node; boolean flag = false; while(true){ if (temp.getNext() == null){ break; } if (temp.getNext().getGoodsId()>goodsNode.getGoodsId()){ break; }else if (temp.getNext().getGoodsId() == goodsNode.getGoodsId()){ flag = true; break; } temp=temp.getNext(); } if (flag){ throw new RuntimeException("不能插入重复的商品..."); }else { goodsNode.setNext(temp.getNext()); temp.setNext(goodsNode); } } /** * 修改指定结点data域信息 * @param goodsNode */ public void updateNode(GoodsNode goodsNode){ GoodsNode temp = node; if (temp.getNext() == null){ throw new RuntimeException("该链表为空链表  


     


     


    ，不能进行修改操作..."); } boolean flag = false; while (true){ //1 直到最后一个结点 if (temp.getNext()==null){ break; } //2 找到指定结点 if (temp.getNext().getGoodsId()==goodsNode.getGoodsId()){ flag = true; break; } temp = temp.getNext(); } if (flag){ //修改指定结点data域数据 temp.getNext().setGoodsName(goodsNode.getGoodsName()); temp.getNext().setGoodsPrice(goodsNode.getGoodsPrice()); }else { throw new RuntimeException("未找到指定结点..."); } } /** * 删除指定结点 * 根据结点ID删除指定结点 * @param goodsId */ public void deleteNode(int goodsId){ //判断链表是否为空 if (node.getNext() == null){ throw new RuntimeException("该链表为空链表


 




 




 


，不能进行删除操作..."); } GoodsNode temp = node; //头结点 boolean flag = false; //是否做删除操作标识 //遍历链表结点 获取指定结点 while (true){ //遍历至最后一个结点 退出遍历 if (temp.getNext()==null){ break; } //找到指定结点 if (temp.getNext().getGoodsId()==goodsId){ flag = true; break; } temp = temp.getNext(); } if (flag){ //删除操作 temp.setNext(temp.getNext().getNext()); }else { throw new RuntimeException("未找到指定删除结点..."); } } /** * 获取当前单链表的结点个数 * @return */ public int lengthNode(){ int length = 0; GoodsNode temp = node.getNext(); while (temp!=null){ length++; temp = temp.getNext(); } return length; } /** * 查看链表元素 */ public void listNode(){ if (node.getNext()==null){ System.out.println("空链表..."); }else { GoodsNode temp = node; while (true){ if (temp.getNext()==null){ break; } temp = temp.getNext(); System.out.println(temp); } } } }

3 双链表

图书结点类 package com.acti.linkedList; /** * author hongyeci * date 20220725 * version 1.0 * remark 双链表--图书类 */ public class BooksNode { private int id; private String name; private double price; private BooksNode pre; //双链表前驱结点 private BooksNode next; //双链表后继结点 public BooksNode() { } public BooksNode(int id, String name, double price) { this.id = id; this.name = name; this.price = price; } public int getId() { return id; } public void setId(int id) { this.id = id; } public String getName() { return name; } public void setName(String name) { this.name = name; } public double getPrice() { return price; } public void setPrice(double price) { this.price = price; } public BooksNode getPre() { return pre; } public void setPre(BooksNode pre) { this.pre = pre; } public BooksNode getNext() { return next; } public void setNext(BooksNode next) { this.next = next; } @Override public String toString() { return "BooksNode{" + "id=" + id + ", name=" + name + \ + ", price=" + price + }; } } 带有头结点的双链表 package com.acti.linkedList; /** * author hongyeci * date 20220725 * version 1.0 * remark 带有头结点的双链表 */ public class DoubleLinkedList { private BooksNode head = new BooksNode(0,"头结点",0.0); /** * 增加结点-添加到末尾结点 * @param booksNode 图书结点 */ public void addNode(BooksNode booksNode){ BooksNode temp = head; while(true){ if (temp.getNext() == null){ break; } temp=temp.getNext(); } temp.setNext(booksNode); booksNode.setPre(temp); } /** * 指定位置插入值 * 按照商品id值顺序插入到链表中 * @param booksNode */ public void insertNode(BooksNode booksNode){ BooksNode temp = head; boolean flag = false; while(true){ if (temp.getNext() == null){ break; } if (temp.getNext().getId()>booksNode.getId()){ break; }else if (temp.getId() == booksNode.getId()){ flag = true; break; } temp=temp.getNext(); } if (flag){ throw new RuntimeException("不能插入重复的商品..."); }else { if (temp.getNext()==null){ temp.setNext(booksNode); booksNode.setPre(temp); }else { //1
     


     


     


、当前结点的后继结点后继节点前驱指向新结点 temp.getNext().setPre(booksNode); //2 




 




 




、新结点后继结点指向当前结点后继结点 booksNode.setNext(temp.getNext()); //3 

   

   

   、新结点前驱结点指向当前结点 booksNode.setPre(temp); //4
     

     

     

、当前结点后继结点指向新结点 temp.setNext(booksNode); } } } /** * 修改指定结点data域信息 * @param booksNode */ public void updateNode(BooksNode booksNode){ BooksNode temp = head; if (temp.getNext() == null){ throw new RuntimeException("该双向链表为空链表   

   

   

，不能进行修改操作..."); } boolean flag = false; while (true){ //1 直到最后一个结点 if (temp.getNext()==null){ break; } //2 找到指定结点 if (temp.getId()==booksNode.getId()){ flag = true; break; } temp = temp.getNext(); } if (flag){ //修改指定结点data域数据 temp.setName(booksNode.getName()); temp.setPrice(booksNode.getPrice()); }else { throw new RuntimeException("未找到指定结点..."); } } /** * 删除指定结点 * 根据结点ID删除指定结点 * @param id */ public void deleteNode(int id){ BooksNode temp = head; //头结点 //判断链表是否为空 if (temp.getNext() == null){ throw new RuntimeException("该链表为空链表   

     

     

   ，不能进行删除操作..."); } boolean flag = false; //是否做删除操作标识 //遍历链表结点 获取指定结点 while (true){ //遍历至最后一个结点 退出遍历 if (temp.getNext()==null){ break; } //找到指定结点 if (temp.getId()==id){ flag = true; break; } temp = temp.getNext(); } if (flag){ //1  




  




  




、当前结点前驱结点的后继指向当前结点的后继结点 temp.getPre().setNext(temp.getNext()); //2 


  


  


  、当前结点的后继结点前驱指向当前结点的前驱结点 if (temp.getNext()!=null){ temp.getNext().setPre(temp.getPre()); } }else { throw new RuntimeException("未找到指定删除结点..."); } } /** * 获取当前单链表的结点个数 * @return */ public int lengthNode(){ int length = 0; BooksNode temp = head.getNext(); while (temp!=null){ length++; temp = temp.getNext(); } return length; } /** * 查看链表元素 */ public void listNode(){ if (head.getNext()==null){ System.out.println("空链表..."); }else { BooksNode temp = head; while (true){ if (temp.getNext()==null){ break; } temp = temp.getNext(); System.out.println(temp); } } } }

4 单向环形链表-约瑟夫环

设编号为1,2,...,n的n个人围坐成一圈



  




  




  

，约定编号为k(1=

节点类 package com.structure.linkedList; /** * author hongyeci * date 20220829 * version 1.0 * remark 单向环形链表--结点类 */ public class BoyNode { //结点编号 private int boyNo; //指向下一个结点 private BoyNode next; public BoyNode(int boyNo) { this.boyNo = boyNo; } public int getBoyNo() { return boyNo; } public void setBoyNo(int boyNo) { this.boyNo = boyNo; } public BoyNode getNext() { return next; } public void setNext(BoyNode next) { this.next = next; } } 单向循环链表-约瑟夫环 package com.structure.linkedList; /** * author hongyeci * date 20220830 * version 1.0 * remark 单向环形链表--约瑟夫环 */ public class CircleSingleLinkedList { private BoyNode firstNode = new BoyNode(-1); /** * 定义单向环形链表 * @param nums 结点个数 */ public void initCircleSingleLinkedList(int nums){ if (nums<1){ System.out.println("结点个数不能小于1"); return; } //定义辅助结点  


  


  


，新进的结点赋给辅助结点 BoyNode temp = null; for (int i=1;i<=nums;i++){ BoyNode newBoy = new BoyNode(i); if (i == 1){ //首结点时 firstNode = newBoy; firstNode.setNext(firstNode); temp = firstNode; }else { temp.setNext(newBoy); newBoy.setNext(firstNode); temp=newBoy; } } } /** * 遍历输出循环链表--链表结点的编号 */ public void showCircleList(){ if (firstNode == null){ System.out.println("该链表为空.."); return; } BoyNode node = firstNode; while (true){ System.out.printf("当前结点编号为：%d\n",node.getBoyNo()); //遍历到最后一个结点时    
     
     
  ，退出 if (node.getNext()==firstNode){ break; } node = node.getNext(); } } /** * 约瑟夫环问题： * 设编号为1,2,...,n的n个人围坐成一圈




   




   




   
，约定编号为k(1=<k<=n)的人开始从1报数 



 



 



，数到m的人出列                ， * 他的下一位又从1开始报数




    




    




    ，数到m的人出列















，依此类推               ，直到所有人都出列为止 



     



     



     ，由此产生一个出队编号的序列  


     


     


    。 * @param startNo 开始结点 * @param count 间隔结点数 * @param nums 单向循环链表中结点个数 */ public void handle(int startNo,int count,int nums){ if(startNo>nums || startNo<1 || firstNode==null){ System.out.println("参数错误.."); return; } //定义辅助结点















，指向最后一个结点 BoyNode lastNode = firstNode; while (true){ if (lastNode.getNext() == firstNode){ //找到最后结点时退出 break; } lastNode = lastNode.getNext(); } //确定编号为startNo的结点移动次数startNo-1 找到firstNode
     
     
     
、lastNode for(int i=0;i<startNo-1;i++){ firstNode = firstNode.getNext(); lastNode = lastNode.getNext(); } //开始数数    
    
    
，数到count的结点出列 while (true){ if (lastNode == firstNode){ //单项循环链表中只剩一个结点时 出列 System.out.printf("最后一个结点%d出列\n",firstNode.getBoyNo()); break; } //数数 // firstNode.setBoyNo(firstNode.getBoyNo()+(count-1)); // lastNode.setBoyNo(lastNode.getBoyNo()+(count-1)); for (int i=0;i<count-1;i++){ firstNode = firstNode.getNext(); lastNode = lastNode.getNext(); } //出列 System.out.printf("结点%d出列\n",firstNode.getBoyNo()); //构成循环链表 firstNode = firstNode.getNext(); lastNode.setNext(firstNode); } } }