数据结构04——单链表

链表基本介绍

单链表

应用实例

实现代码

package list; import java.beans.beancontext.BeanContext; import java.time.temporal.Temporal; /** * @program: DataStructures * description: * @author: Mr.Zhang * @create: 2020-28-06_20:28 **/ public class SingleListDemo { public static void main(String[] args) { // 测试 // 1. 首先添加四个节点,普通方法 SingleList singleList = new SingleList(); // singleList.addLink(new HeroLink(2, "宋江", "及时雨")); // singleList.addLink(new HeroLink(1, "鲁智深", "花和尚")); // singleList.addLink(new HeroLink(4, "林冲", "豹子头")); // singleList.addLink(new HeroLink(3, "柴进", "小旋风")); // 首先添加四个节点,顺序插入方法 singleList.addLinkByOrder(new HeroLink(2, "宋江", "及时雨")); singleList.addLinkByOrder(new HeroLink(1, "鲁智深", "花和尚")); singleList.addLinkByOrder(new HeroLink(4, "林冲", "豹子头")); singleList.addLinkByOrder(new HeroLink(3, "柴进", "小旋风")); // singleList.addLinkByOrder(new HeroLink(3, "柴进", "小旋风")); // 2. 打印单链表 singleList.showList(); // 修改元素测验 // singleList.updateLink(new HeroLink(2, "宋江", "及时雨-----")); // 打印修改后的链表 // singleList.showList(); // 删除最后一个元素 // singleList.delLastLink(); // singleList.delLastLink(); // singleList.delLastLink(); // singleList.delLastLink(); // singleList.delLastLink(); // // 再打印 // singleList.showList(); // 测试根据id删除节点 singleList.delLinkById(12); // singleList.delLinkById(1); // singleList.delLinkById(3); // singleList.delLinkById(4); // 打印 System.out.println("删除后："); singleList.showList(); } } // 单链表类 class SingleList { // 头节点 private HeroLink head = new HeroLink(0, "", ""); // 添加节点 public void addLink(HeroLink heroLink) { HeroLink temp = head; // 遍历直到找到最后一个节点，然后把最后一个节点的next指向新添加节点 while (true) { // 如果next为空，则说明是temp指向了最后一个节点，则指向新节点 if (temp.next == null) { temp.next = heroLink; break; } // temp后移 temp = temp.next; } } // 第二种添加节点的方式，通过排名来添加 public void addLinkByOrder(HeroLink heroLink) { // 指针 HeroLink temp = head; boolean flag = false; // 用于判断是否有编号重复的元素插入 while (true) { // 1. 判断是否添加过元素，若没有，则跳出 if (temp.next == null) { // 没有添加过元素 break; } // 2. 判断新的元素的id是否等于temp.next的id，若等于，则跳出循环，同时置flag为true if (heroLink.id == temp.next.id) { flag = true; break; } // 3. 判断新的元素的id是否小于temp.next的id，若小于，则找到位置，跳出循环 if (heroLink.id < temp.next.id) { break; } // 不满足上述条件，说明没有找到合适的位置 // 指针temp后移 temp = temp.next; } if (flag) { // 说明id重复 System.out.println("id号重复，不能插入此元素" + heroLink.id); }else { // 对元素进行插入操作 // 1. 新元素指向temp.next heroLink.next = temp.next; // 2. temp指向新元素 temp.next = heroLink; } } // 修改链表的内容，注意编号不能修改 public void updateLink(HeroLink heroLink) { boolean flag = false; // 用于判断是否找到了所要修改的元素 // 判断是否有元素 if (head.next == null) { // 没有元素 return; } // 获得指针 HeroLink temp = head.next; while (true) { if (temp.next == null) { // 遍历完成，没有找到元素 break; } // 判断是否找到了所要修改的元素 if (heroLink.id == temp.next.id) { // 找到了，置flag为true，跳出循环 flag = true; break; } // 指针后移 temp = temp.next; } if (flag) { // 找到元素，进行修改, 只修改昵称 temp.nickName = heroLink.nickName; }else { System.out.println("没有查到要修改的元素！！！"); } } // 显示列表内容 public void showList() { HeroLink temp = head; // 首先判断单链表是否为空 if (temp.next == null) { System.out.println("单链表为空"); return; } // 遍历直到找到最后一个节点，然后把最后一个节点的next指向新添加节点 while (true) { // 如果next为空，则说明是temp指向了最后一个节点, 退出循环 if (temp.next == null) { break; } // 否则temp指向下一个节点 temp = temp.next; System.out.println(temp); } } // 删除单链表的最后一个节点 public void delLastLink() { HeroLink temp = head; if (temp.next == null) { System.out.println("无元素可以删除，链表为空！！！"); return; } while (true) { if (temp.next.next == null) { temp.next = null; break; } temp = temp.next; } } // 删除指定编号的节点 public void delLinkById(int id) { // 1. 判断此链表是否为空 if (head.next == null) { System.out.println("此链表为空。。"); return; } // 2. 查找此编号，根据flag决定状态，是否查找到 boolean flag = false; HeroLink temp = head; // 指向第一个元素 while (true) { // 判断是否到达最后一个节点 if (temp.next == null) { // 遍历结束，没找到 break; } // 到这因为肯定有至少一个元素 if (temp.next.id == id) { // 找到了 flag = true; break; } temp = temp.next; } // 3. 根据flag决定是否删除元素 if (flag) { // 找到了元素，进行删除 // if (temp.next.next == null) { // // 此种是删除最后一个元素 // temp.next = null; // }else // // 否则就是删除中间元素 temp.next = temp.next.next; }else System.out.println("没找到此元素：" + id); } } // 英雄类，也就是节点类 class HeroLink { public int id; public String name; public String nickName; public HeroLink next; // 构造函数，初始化 public HeroLink(int id, String name, String nickName) { this.id = id; this.name = name; this.nickName = nickName; } // 打印 @Override public String toString() { return "HeroLink{" + "id=" + id + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }