链表介绍

链表是有序的列表，但是它在内存中是存储如下：
image.png
小结:
1)链表是以节点的方式来存储,是链式存储
2)每个节点包含data 域， next 域：指向下一个节点.
3)如图：发现链表的各个节点不一定是连续存储.
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单向链表逻辑结构

单链表(带头结点) 逻辑结构示意图如下
image.png

单向链表应用实例

使用带head头的单向链表实现：
水浒英雄排行榜管理完成对英雄人物的增删改查操作，

无序添加

  1. 第一种方法在添加英雄时，直接添加到链表的尾部

思路分析示意图：
image.png
代码实现：

  1. package com.atguigu.linkedlist;
  3. public class SingleLinkedListDemo {
  5.     public static void main(String[] args) {
  6.         // 创建节点
  7.         HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
  8.         HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
  9.         HeroNode heroNode3 = new HeroNode(3, "林冲", "豹子头");
  11.         // 创建单向链表
  12.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  14.         // 加入
  15.         singleLinkedList.add(heroNode1);
  16.         singleLinkedList.add(heroNode2);
  17.         singleLinkedList.add(heroNode3);
  19.         // 显示
  20.         singleLinkedList.showList();
  21.     }
  23. }
  25. // 定义类，管理英雄
  26. class SingleLinkedList {
  27.     // 先初始化一个头节点，头节点不要动，不存放具体数据
  28.     private HeroNode head = new HeroNode(0, "", "");
  30.     // 添加节点到单链表
  31.     // 当不考虑编号排序时：1.找到当前链表的最后节点 2.将最后这个节点的next指向新的节点
  32.     public void add(HeroNode heroNode) {
  33.         // 因为head节点不能动，因此我们需要一个辅助遍历temp
  34.         HeroNode temp = head;
  35.         // 遍历链表找到最后
  36.         while (true) {
  37.             // 找到链表的最后
  38.             if (temp.next == null) {
  39.                 break;
  40.             }
  41.             // 如果没有找到,temp后移
  42.             temp = temp.next;
  43.         }
  44.         // 当退出while循环时，temp就指向了链表的最后
  45.         // 将最后这个节点的next指向新的节点
  46.         temp.next = heroNode;
  47.     }
  49.     // 显示链表【遍历】
  50.     public void showList() {
  51.         // 判断链表是否为空
  52.         if (head.next == null) {
  53.             System.out.println("链表为空");
  54.             return;
  55.         }
  56.         // 头节点不能动，因此需要一个辅助变量来遍历
  57.         HeroNode temp = head.next;
  58.         while (true) {
  59.             // 判断链表是否到最后
  60.             if (temp == null) {
  61.                 break;
  62.             }
  63.             // 输出节点信息
  64.             System.out.println(temp);
  65.             // 将temp后移
  66.             temp = temp.next;
  67.         }
  68.     }
  70. }
  72. class HeroNode {
  73.     public int no;// 编号
  74.     public String name;// 姓名
  75.     public String nickname;// 昵称
  76.     public HeroNode next;// 指向下一个域，节点
  78.     // 构造器
  79.     public HeroNode(int hNo, String hName, String hNickname) {
  80.         this.no = hNo;
  81.         this.name = hName;
  82.         this.nickname = hNickname;
  83.     }
  85.     // 为了显示方便，重写toString方法
  86.     @Override
  87.     public String toString() {
  88.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  89.     }
  91. }

有序添加

2.第二种方式在添加英雄时，根据排名将英雄插入到指定位置
image.png
代码实现：

  2.     // 根据排名插入到指定的位置
  3.     // 若有这个排名，则添加失败，并给出提示
  4.     public void addByOrder(HeroNode heroNode) {
  5.         // 通过一个辅助指针帮助找到添加的位置
  6.         // 因为单链表的原因，我们找的temp是位于添加位置的前一个节点，否则插入失败
  7.         HeroNode temp = head;
  8.         boolean flag = false;// flag标志加的编号是否存在，默认为false
  9.         while (true) {
  10.             if (temp.next == null) {// 找到最后跳出循环
  11.                 break;
  12.             }
  13.             if (temp.next.no > heroNode.no) {// 位置找到，就在temp的后面
  14.                 break;
  15.             } else if (temp.next.no == heroNode.no) {// 说明添加的hero编号已经存在
  16.                 flag = true;
  17.                 break;
  18.             }
  19.             temp = temp.next;// 后移，继续遍历
  20.         }
  21.         if (flag) {
  22.             System.out.printf("准备插入的英雄编号%d已经存在，不能加入\n", heroNode.no);
  23.         } else {
  24.             // 插入到链表中，temp的后面
  25.             heroNode.next = temp.next;
  26.             temp.next = heroNode;
  27.         }
  28.     }

修改

3.英雄人物的修改

  1. // 修改节点信息，根据no修改
  2.     public void update(HeroNode newheHeroNode) {
  3.         // 判断是否为空
  4.         if (head.next == null) {
  5.             System.out.println("链表为空");
  6.             return;
  7.         }
  8.         // 找到需要修改的节点，根据no编号
  9.         HeroNode temp = head.next;
  10.         boolean flag = false;
  11.         while (true) {
  12.             if (temp == null) {
  13.                 break;
  14.             }
  15.             if (temp.no == newheHeroNode.no) {
  16.                 flag = true;
  17.                 break;
  18.             }
  19.             temp = temp.next;// 节点后移
  20.         }
  21.         if (flag) {
  22.             temp.name = newheHeroNode.name;
  23.             temp.nickname = newheHeroNode.nickname;
  24.         } else {
  25.             System.out.printf("没有找到编号为%d的节点，不能修改\n", newheHeroNode.no);
  26.         }
  27.     }

删除

image.png
代码实现：

  1. // 删除节点
  2.     // head不能动，需要一个temp辅助节点，找到待删除节点的前一个节点
  3.     // 说明我们在比较的是，temp,next.no 和需要删除节点的no
  4.     public void delete(int no) {
  5.         HeroNode temp = head;
  6.         boolean flag = false;
  7.         while (true) {
  8.             if (temp.next == null) {
  9.                 break;
  10.             }
  11.             if (temp.next.no == no) {// 找到删除的节点
  12.                 flag = true;
  13.                 break;
  14.             }
  15.             temp = temp.next;// temp后移
  16.         }
  17.         if (flag) {
  18.             temp.next = temp.next.next;
  19.         } else {
  20.             System.out.printf("要删除的%d节点不存在\n", no);
  21.         }
  23.     }