链表是有序的列表，它在内存中的实际结构如下
小结：
- 链表是以节点的方式来存储，是链式存储。
- 每个节点包含 data 域，next 域指向下一个节点。
- 如图：发现链表的各个节点不一定是连续存放.
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定。
- 单链表(带头节点)逻辑结构示意图如下
单链表的应用实例
- 使用带head头的
单项链表实现，水浒英雄排行榜管理
需求：
- 完成对英雄人物的增删改查操作
- 第一种方法在添加英雄时，直接添加到链表的尾部（不考虑排序）
- 第二种方式在添加英雄时，根据排名将英雄插入到指定位置（如果有这个排名，则添加失败，并给出提示）
直接添加到链表的尾部（不考虑排序）
思路分析：
添加：
- 先创建一个head头节点，作用就是表示单链表的头
- 后面我们每添加一个节点，就直接加入到链表的最后
遍历：
- 通过一个辅助变量帮助遍历整个链表。
代码实现：
定义节点
//定义 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; } //为了显示方便，我们重写toString方法 @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickName='" + nickName + '\'' + '}'; } }
定义链表来存放管理我们的英雄
//定义SingleLinkedList 管理我们的英雄 class SingleLinkedList{ //先初始化一个头节点，头节点不要动，不存放具体的数据 private HeroNode head =new HeroNode(0,"",""); /** * 添加节点到单向链表 * 思路: 当不考虑编号顺序时 * 1.找到当前链表的最后节点 * 2.将最后这个节点的next指向新的节点 */ public void add(HeroNode heroNode){ //因为head节点不能动，因此我们需要一个辅助变量 temp HeroNode temp = head; //遍历链表找到最后 while (true){ //找到链表的最后 if (temp.next == null){ break; } //如果没有找到最后，将temp后移 temp = temp.next; } //当退出while循环时，temp就指向了链表的最后,将最后这个节点的next 指向新的节点 temp.next = heroNode; } /** * 显示链表[遍历] */ 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 = temp.next; } } }
初始化并测试
public static void main(String[] args) { //创建节点 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); HeroNode hero4 = new HeroNode(4, "鲁智深", "花和尚"); HeroNode hero5 = new HeroNode(5, "杨志", "青面兽"); HeroNode hero6 = new HeroNode(6, "林冲", "豹子头"); //创建链表 SingleLinkedList singleLinkedList =new SingleLinkedList(); singleLinkedList.add(hero1); singleLinkedList.add(hero2); singleLinkedList.add(hero3); singleLinkedList.add(hero4); singleLinkedList.add(hero5); singleLinkedList.add(hero6); //显示 singleLinkedList.list(); }
根据排名将英雄插入到指定位置
（按照编号的顺序添加）思路分析：
- 首先找到新添加的节点的位置，是通过辅助变量(指针)，通过遍历来搞定
- 新的节点.next = temp.next
- 将 temp.next = 新的节点
代码实现：
在 SingleLinkedList 类中重新定义一个增加方法
public void addByOrder(HeroNode heroNode){ //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置，因为是单链表，因此我们找的temp是位于 添加位置的前一个节点，否则插入不了。 HeroNode temp = head; boolean flag = false; //flag表示添加的编号是否存在，默认为false while (true){ if (temp.next == null){ //说明temp已经在链表的最后 break; } if (temp.next.no > heroNode.no){ //位置找到，就在temp的后面插入 break; }else if (temp.next.no == heroNode.no){ //说明希望添加的heroNode的编号已经存在 flag =true; //说明编号存在 break; } temp = temp.next; //后移,遍历当前链表 } //判断flag的值 if (flag){ //不能添加，说明编号存在 System.out.printf("准备插入的英雄的编号%d 已经存在了,不能加入\n",heroNode.no); }else { //插入到链表中，temp的后面 heroNode.next = temp.next; temp.next = heroNode; } }
初始化并测试 注意：这里不按照顺序插入，我们看结果是否会自动排序
public static void main(String[] args) { //创建节点 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); HeroNode hero4 = new HeroNode(4, "鲁智深", "花和尚"); HeroNode hero5 = new HeroNode(5, "杨志", "青面兽"); HeroNode hero6 = new HeroNode(6, "林冲", "豹子头"); //创建链表 SingleLinkedList singleLinkedList =new SingleLinkedList(); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero5); singleLinkedList.addByOrder(hero6); //显示 singleLinkedList.list(); }
测试 2 加入重复的节点
public static void main(String[] args) { //创建节点 HeroNode hero1 = new HeroNode(1, "宋江", "及时雨"); HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟"); HeroNode hero3 = new HeroNode(3, "吴用", "智多星"); HeroNode hero4 = new HeroNode(4, "鲁智深", "花和尚"); HeroNode hero5 = new HeroNode(5, "杨志", "青面兽"); HeroNode hero6 = new HeroNode(6, "林冲", "豹子头"); //创建链表 SingleLinkedList singleLinkedList =new SingleLinkedList(); singleLinkedList.addByOrder(hero3); singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero4); singleLinkedList.addByOrder(hero5); singleLinkedList.addByOrder(hero6); //重复节点 singleLinkedList.addByOrder(hero1); //显示 singleLinkedList.list(); }
