数据结构与算法-单链表
Java高级系列文章前言
本文章涉及到数据结构与算法的知识，该知识属于Java高级阶段，通常为学习的二阶段，本系列文章涉及到的内容如下（橙色框选内容）：
本文章核心是教学视频，所以属于个人笔记，非商用。
文章结构
标识
本系列文章中记录的数据结构与算法都会多多少少用到一些Java的API，这些API只会一笔带过，主要还是看逻辑思路。
大标题
小标题
文本内容和图片内容... 70%/30%
图片说明（加重）
逻辑思路和次要说明
文本说明（普通文本）
主要说明和补充
内容结构
大标题
介绍
英文单词关键字陈列(有时会省略)
代码块...
思路引入
（概率出现小标题）
思路解析
（概率出现小标题）
源码
代码展示
图文说明
单链表
介绍
线性表中顺序存储的优缺点非常明显，优点是无序因为表中元素之间的逻辑关系而增加额外的存储空间，可以快速地取表中任一位置的元素。缺点是插入和删除操作需要移动大量元素，当线性表长度变化较大时，难以确定存储空间的容量，造成存储空间的“碎片”。
而链式存储则是让所有元素都不考虑是否相邻，哪里有位置就到哪里，让每个元素知道它下一个元素的位置在哪里即可，这样我们每次通过该元素的下一个元素位置就可以找到第二个元素（内存地址），依此类推…这样所有的元素我们就都可以通过遍历而找到。
英文单词关键字陈列
书写习惯：XxxYyyZzz（Java类驼峰语法）
格式：英文单词 -> 中文翻译 -> 空耳（个人习惯）
思路引入
链表是由一个一个的节点（Node）组成，该节点有data数据域和next指针域，我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素a…i的存储映像，称为节点（Node）。
对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个节点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个节点，其实就是商一个的后继指针指向的位置。最后一个指针是没有后继位置的，所以我们通常让最后一个节点的next指针设置为空，通常用NULL或^符号表示。
有时，我们为了更加方便地对链表进行操作，会在单链表的第一个节点前附设一个节点，称为头节点，头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头节点的指针域存储指向第一个节点的指针。也就是说如果有头节点，则头指针就在头结点的指针域里，表示第一个节点的内存地址！
下面用图片演示无头节点和有头节点和空链表的存储示意图。
无头节点的单链表
带有头节点的单链表
空链表
思路解析
有了上面的思路后，我们来看本文章的实现解析，该单链表我们采用英雄排名的设计思路，比如水浒传，我们此处设计了3个属性：no -> 英雄编号；name -> 英雄名字; nickName -> 外号/昵称。
- no：该属性是链表中实现顺序存储和修改删除的重要属性。
- name：属于数据域，没有特殊含义。
- nickName：属于数据域，没有特殊含义。
我们在节点类中定义一个本类实例，该实例代表下一个节点，该属性就相当于指针域，通过该属性进行遍历、添加和删除等等…
源码
代码展示
package linkedlist;
public class SingleLinkedListDemo {
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, "林冲", "豹子头");
//创建一个链表
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.list();
//测试修改节点的代码
HeroNode newHeroNode = new HeroNode(2,"修改节点","修改");
singleLinkedList.update(newHeroNode);
System.out.println("=====链表发生了修改！=====");
//显示一把
singleLinkedList.list();
//删除一个节点
singleLinkedList.del(1);
System.out.println("=====链表发生了删除！=====");
//显示一把
singleLinkedList.list();
}
}
//定义一个SingleLinkedList 管理我们的英雄人物
@SuppressWarnings({"all"})
class SingleLinkedList{
//先初始化一个头节点，头节点的数据域不存放数据，头指针指向头节点
private HeroNode head = new HeroNode(0,"","");
//添加节点到单向链表
//思路：当不考虑编号的顺序时
//1.找到当前链表的最后节点
//2.将最后节点的next域指向新的节点即可
public void add(HeroNode heroNode){
//因为头节点不能动（头结点是一个不存储数据的标记节点，也可以附加链表信息）
//因此我们需要一个辅助变量 -> temp
HeroNode temp = head;//有个临时节点指向了head
//遍历链表，找到最后
while(true){
//找到链表的最后了
if(temp.next == null){//说明已经找到最后了
break;
}
//如果没有找到最后，将temp后移为它的下一个节点，依次往后走
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
temp.next = heroNode;
}
//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//(如果有这个排名，则添加失败，并给出提示)
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;
}
}
//修改节点的信息，根据no编号来修改，即no编号不能改
//说明
//1.根据newHeroNode的no来修改即可
public void update(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;
}
//根据flag判断是否找到要修改的节点
if(flag){
temp.name = newHeroNode.name;
temp.nickname = newHeroNode.nickname;
}else{
System.out.printf("没有找到编号%d的节点，不能修改\n",newHeroNode.no);
}
}
//删除节点
//思路
//1.head不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
//2.说明：我们在比较时，是temp.next.no和需要删除的节点的no进行比较
public void del(int delNo){
HeroNode temp = head;
boolean flag = false;//标志是否找到待删除节点的前一个节点
while(true){
if(temp.next == null){//已到链表最后
break;
}
if(temp.next.no == delNo){
//找到了待删除节点的前一个节点 temp ，此时temp是要删除节点的前一个节点！
flag = true;
break;
}
temp = temp.next;//temp后移才能实现遍历
}
//判断flag
if(flag){//说明找到
//可以删除
temp.next = temp.next.next;//没有引用的temp.next会被垃圾回收机制回收
}else{
System.out.printf("要删除的 %d 节点不存在！\n",delNo);
}
}
//显示链表[遍历]
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);
//将next后移
temp = temp.next;
}
}
}
//定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode{
public int no;//编号，No
public String name;//名字
public String nickname;//昵称
public HeroNode next;//指向下一个节点
//构造器
public HeroNode(int heroNo,String heroName,String heroNickName){
this.no = heroNo;
this.name = heroName;
this.nickname = heroNickName;
}
//为了显示方便，我们重写toString()方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
图文说明
本程序分三块：节点类、链表类、main方法测试。
我们主要介绍链表类中的实现方法，节点类和main方法并不重要。
节点类
链表类
1.链表类的逻辑
2.无排序添加节点方法
3.根据no属性排序的添加节点方法
方法的逻辑是这样的，如果新插入的节点它的no在链表中遍历后与某一个节点的no一致，则判断为该链表中已存在该节点，就不添加新节点。否则根据no大小的排序进行添加，下面示例图演示了如果中间插入节点的流程图。
3.1节点指针域的逻辑
3.2方法实现
其实很简单，假设temp是自己不认识的小朋友，比自己no大的小朋友是自己的朋友，这个朋友叫宝马，自己就是新节点。
假设自己看到不认识的小朋友和朋友宝马拉着手，那么自己肯定要插入到中间来前者陌生人和朋友的手，那么你看到了朋友宝马，那么就要知道拉着宝马手的人是谁（temp.next.no>newNode.no）{ break}。这样你直接拉着陌生人拉着的手（你朋友宝马的手，让陌生人往左边移动先），然后再让陌生人拉着你的手（陌生人再拉住你的手）。这样子你就插入到中间了。
补充，如果while循环没有符合三个if就会进行temp = temp.next;这样的话就完成了一次节点后移，这样就可以遍历所有的节点，只有遍历完所有的节点才会触发temp.next==null的判断，所以循环一定不会死循环！
4.修改节点数据域的数据
该案例我们通过节点的no属性来定位节点，然后进行修改，我们仍然会定义一个boolean类型的flag，如果该属性是false则表明没有找到该no属性相同的节点，则直接提示没找到。
5.删除节点方法
6.显示单链表[遍历]
