结构示意图.png
①链表示意结点的方式来存储，是链式存储；
②每个结点包含data域，next域指向下一个结点；
③如图，链表的每个结点不一定是连续存储；
④链表分带头结点和没有头结点的链表，根据实际需求来确定
head节头（头结点）：
①不放具体的数据；
②作用就是表示单链表的表头
代码实现如下：
package DataStructures; /* • 单链表 （按存储顺序进行存储） */ public class SingleLinkedListDemo { public static void main(String[] args) { HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "无用", "智多星"); SingleLinkedList singlelinkedlist = new SingleLinkedList(); singlelinkedlist.addOrderBy(hero1); singlelinkedlist.addOrderBy(hero3); singlelinkedlist.addOrderBy(hero2); singlelinkedlist.findNode(3); } }
class SingleLinkedList { // 定义一个头结点，头结点的作用，定位这个链表得初始位置 private HeroNode head = new HeroNode(0, "", ""); // 添加结点到链表当中 // 当不考虑编号顺序时 // 1.找到当前链表得最后结点 // 2.将最后这个结点得next指向新的结点 public void addNode(HeroNode heronode) { // 因为head结点不能动，我们需要一个辅助遍历temp HeroNode temp = head; // 遍历链表，找到最后 while (true) { // 找到最后链表 if (temp.next == null) { break; } else { // 如果没有找到最后，就temp后移 temp = temp.next; } } // 当退出循环后，temp就遍历到了链表得最后 temp.next = heronode; } public void listNode() { // 判断链表是否为空 if (head.next == null) { System.out.println("链表为空"); System.out.println("aaaaa"); return; } // 同理 因为头结点不能动，我们需要一个辅助变量来遍历 HeroNode temp = head.next; while (true) { // 判断是否到链表最后 if (temp == null) { break; } // 输出结点信息 System.out.println(temp); // 将temp后移,一定将temp后移 temp = temp.next; } } // 删除一个单链表结点 public void deleteNode(int no) { HeroNode temp = head; boolean flag = false; while (true) { if (temp == null) { break;// 遍历到最后没找到 } if (temp.next.no == no) { flag = true; break; } temp = temp.next; } if (flag) { temp.next = temp.next.next; } else { System.out.printf("删除的%d结点不存在\n", no); } } // 对单链表里面得结点进行修改 public void update(HeroNode newhero) { HeroNode temp = head; boolean flag = false; while (true) { if (temp == null) { break;// 已经遍历完链表 } if (temp.no == newhero.no) { // 找到 flag = true; break; } temp = temp.next;// 将结点后移 } // 根据flag判断是否找到要修改得结点 if (flag) { temp.name = newhero.name; temp.nickname = newhero.nickname; } else { System.out.printf("没有找到编号%d的结点，不能进行修改\n", newhero.no); } } // 查找结点 public void findNode(int no) { HeroNode temp = head; boolean flag = false; while (true) { if (temp == null) { break; } if (temp.no == no) { flag = true; break; } temp = temp.next; } if (flag) { System.out.println(temp); } else { System.out.printf("所查%d结点不存在\n", no); } } // 按照序号编号进行排列 public void addOrderBy(HeroNode hero) { // 因为头结点不能动，因此我们通过一个辅助变量来帮助我们找到添加得位置 // 因为是单链表，我们找的temp是位于添加结点得前一个位置，否则插入不了 HeroNode temp = head;// 定义一个便遍历得游标 boolean flag = false;// flag标志添加得编号是否存在，默认为false while (true) { if (temp.next == null) {// 说明已经是链表得最后了 break; } if (temp.next.no > hero.no) {// 位置找到，就在temp后面插入 break; } else if (temp.next.no == hero.no) { flag = true;// 说明编号已经找到 break; } temp = temp.next;// 进行后移，遍历当前链表 } if (flag) { System.out.printf("准备插入得编号%已经存在了,不能加入\n", hero.no); } else { // 插入到链表中，temp的后面 hero.next = temp.next;// 将当前得下一个结点赋值给传入得结点next temp.next = hero;// 将传入得结点赋值给找到结点得next } } }
//定义HeroNode 每个HeroNode对象就是一个结点 class HeroNode { public int no; public String name; public String nickname; public HeroNode next;// 用于指向下一个结点 public HeroNode(int no, String name, String nickname) { this.no = no; this.name = name; this.nickname = nickname; this.next = next; } @Override public String toString() { return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]"; } }
