一. 几个概念

0x01 链表

  链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表是以结点的方式存储的，是链式存储。结点可以在运行时动态生成。链表是有序的列表，但其在内存中的存储是非连续、非顺序的。

0x02 结点

  在链表数据结构中，我们把一个数据元素的存储映像称为结点（Node）。而一个结点包含存储数据元素的两部分信息：数据域（Data）和指针域(Next)。

0x03 数据域、指针域

数据域：存储数据元素信息的域；
指针域：存储直接后继位置的域，指向下一个结点。

0x04 直接前驱元素和直接后继元素

• 对于线性存储结构，假设线性表记为 ( 1 , 2 , . . . , n − 1 , n , n + 1... ) (1,2,...,n-1,n,n+1...) (1,2,...,n−1,n,n+1...)
  数据元素 n n n的直接前驱元素： n − 1 n-1 n−1
  数据元素 n n n的直接后继元素： n + 1 n+1 n+1
• 对于链表存储结构，如下图所示：
  

head.next表示为头结点head的后继结点；而head则为head.next的前驱结点。

0x05 链表分带头结点的链表和没有头结点的链表

• 首先，无论链表是否为空，头指针均不为空；即链表一旦被创建，则头指针便指向了它，头指针是链表的必要元素。头指针存放的是链表第一个结点的地址。
• 对于包含头结点的单链表，头指针存放的是头结点的存放地址，而头结点也包含数据域（data）和指针域(next)，但头结点的数据域一般不存储任何信息，头结点的指针域包含的是首结点的地址。
• 对于不包含头结点的单链表，头指针存放的就是首节点的地址。
• 首节点：是存放链表中第一个有效元素的结点。
• 头结点是为了操作的统一和方便而引出的，放在第一个元素结点之前。有了头结点则在首节点前增加、删除元素就和其他结点的操作统一了。头结点不一定是链表必需要素。

二. 单链表结构与顺序存储结构的优缺点

1.存储分配方式

• 顺序存储结构用一段连续存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

2.时间性能

• 查找
  – 顺序存储结构o(1)
  – 单链表o(n)
• 插入和删除
  – 顺序存储结构需要平均移动表长一半的元素，时间复杂度o(n)
  – 单链表在找到位置的指针后，插入和删除时间复杂度仅为o(1)

2.空间性能

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要预分配存储空间，只要有就可以分配，元素个数也不受限制

三. 代码实现

package com.atCodeSun.linkedlist03;

/**
 * @author codeSun
 * @create 2021-07-26 10:47
 */

/*
    单链表实现水浒英雄排行管理
 */

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //4.测试
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        //创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //加入人物
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);

        //按编号加入人物
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero3);

        singleLinkedList.list();

        //测试修改结点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.updata(newHeroNode);
        System.out.println("修改一个结点后的链表");

        //显示
        singleLinkedList.list();

        //删除一个结点
        singleLinkedList.del(1);
        System.out.println("删除一个结点后的链表");
        singleLinkedList.list();

    }
}


//2.定义SingleLinkedList管理英雄
class SingleLinkedList{
    //2.1先初始化一个头结点，头结点不要动，头结点不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    //2.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;
    }


    //5.方式二 在添加英雄时，根据排名将英雄插入到指定位置（如果有这个排名，则添加失败，并给出提示）
    public void addByOrder(HeroNode heroNode){
        //通过辅助指针来遍历寻找添加位置
        HeroNode temp = head;
        boolean flag = false; //标志添加的编号是否存在，默认为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;
        }
    }

    //6.修改结点的信息，根据编号来修改，即编号不能改
    public void updata(HeroNode newHeroNode){
        //判断是否空
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        //根据编号no找到需要修改的结点
        HeroNode temp = head.next;
        boolean flag = false; //表示是否找到该结点
        while(true){
            if(temp == null){ //遍历结束判断
                break;
            }
            if (temp.no == newHeroNode.no) { //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //修改
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else{
            //没有找到
            System.out.printf("没有找到编号为%d的结点，不能修改\n", newHeroNode.no);
        }
    }

    //7.删除结点
    public void del(int no){
        HeroNode temp = head;
        boolean flag = false; //标志是否找到待删除的结点
        while (true) {
            if(temp.next == 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);
        }
    }

    //3.显示链表（遍历）
    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;
        }
    }
}

//1.定义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;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName +
                '}';
    }
}