前面我们简单的分别对稀疏数组和队列以及环形对列做了详细的讲解，也通过实际的案列进行了分析，接下来我们来看看链表中的单链表，实现我们来看下单链表的基本特性。
单链表介绍
链表是一张有序的列表，我们可以看看它在内存中实际的存储特性如图：
单链表实际存储特性.png
上述是单链表在内存中的实际存储位置，我们简答的来分析下该图中链表的特性：
- 首先head代表头节点，注意：这里它只代表该链表的头实际上不做数据的存储，可以看到的它指向内存的150地址。
- 在仔细一看150地址处存有data为a1的数据，这其中data域就是表示当前节点保存的数据，也就是图中的a1.
-
接着看，我们会发现a1的指针是指向了110的内存地址处，图中110地址处是存有节点数据为a2的节点，依次内推，这就是链表在内存中实际保存数据的位置，可能我们在平时中看到的单链表是如下图这种：
单链表的逻辑结构图.png
通过我们对链表在内存中的位置简单的分析，其中上图中单链表是它的逻辑结构图，也就是我们平时见到的，简单的分析我们来总结下链表的特点;
链表总结
- 链表是以节点的方式来存储的
- 其中每个节点都有一个data域，和next域：用来指向下一个节点
- 最后我们发现链表实际的存储不一定是连续的
上述就是我们通过图来得到的总结，接下来我们通过实际的利用用代码的来写出来
单链表的实际应用
案例
我们利用带head的单链表来实现对梁山好汉英雄人物的增删以及修改操作：
- 在不考虑对英雄的添加顺序时,我们直接加到链表的尾部即可
- 当需要考虑对英雄的添加时，根据他们的排名进行添加到指定的位置
我们先来实现方式一的添加操作
不考虑顺序的思路分析
-
首先我们来看如图：
单链表添加分析图.png
按照图中的分析，我们首先是需要创建一个节点(HeroNode),至于该节点到底有什么属性，图中描述的很详细了，这也是我们在前面分析得到的结果
由于是不考虑是添加时的顺序，那么我们直接加后面就可以了，来看代码实现：
代码实现
- 节点的创建
//1.定义一个HeroNode节点，每一个HeroNode对象就是一个节点
class HeroNode{
public int no; //英雄节点的编号
public String name;
public String nickName; //英雄的别名
public HeroNode next;//指向下一个节点
public HeroNode(int hNo,String hName,String hNickName){
this.no = hNo;
this.name = hName;
this.nickName = hNickName;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
- 接着我们来实现添加的操作，代码如下：
//2.定义SingleLinkList来管理我们的hero
class SingleLinkList{
//1.先初始化一个头结点，不存储具体的数据，只是作为我们链表的头部
private HeroNode head = new HeroNode(0,"","");
//2.添加节点到单向链表中
//思路：当我们不考虑编号(no)的顺序时
//2.1.首先找到当前链表的最后一个节点
//2.2.将最后一个节点的next指向新的节点即可
public void add(HeroNode heroNode){
//1.定义一个临时的变量(主要的目的是因为我们的头节点是不能动的，通过这个辅助指针来进行相关的操作)
HeroNode temp = head; //temp指向了head节点
//2.遍历链表，找到最后一个
while (true){
if (temp.next == null){ //表明是最后一个了
break;
}
//如果没有找到，将temp后移
temp = temp.next;
}
//3.当退出while时表名是最后一个节点了,指向新的节点即可
temp.next = heroNode;
}
上述就是不考虑顺序时的添加操作，代码简单注释很详细，我们来看打印链表的代码：
//显示链表（通过一个辅助变量，因为head不能动）
public void show(){
//1.首先判断链表是否为null
if (head.next ==null){
System.out.println("链表为null");
return;
}
//因为头结点不能动，需要一个辅助指针来遍历
HeroNode temp = head.next; //说明至少有一个节点
while (true){
//判断是否到了链表的最后
if (temp ==null){
break;
}
//打印节点信息
System.out.println(temp);
//将指针后移，遍历下一个节点信息
temp = temp.next;
}
}
这就是打印的操作，需要注意的一点是，打印节点信息时一定要执行 temp = temp.next操作，不然就是一个死循环。
来测试一把，代码如下：
public class SingleLinkListCase {
public static void main(String[] args) {
//创建节点
HeroNode node1 = new HeroNode(1,"宋江","及时雨");
HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
HeroNode node3 = new HeroNode(3,"吴用","智多星");
HeroNode node4 = new HeroNode(4,"林冲","豹子头");
//创建链表，并添加
SingleLinkList singleLinkList = new SingleLinkList();
singleLinkList.add(node1);
singleLinkList.add(node2);
singleLinkList.add(node3);
singleLinkList.add(node4);
singleLinkList.show();
结果如图所示：
测试结果图.png
上述就是在不考虑顺序时的代码以及结果，接下来我们来看下当考虑添加的顺序时
按照顺序添加思路分析
来看一张图：
顺序添加分析图.png
- 首先考虑到我们的head是不能动的，因此我们需要借助辅助的变量temp来遍历我们的链表帮我们找到需要添加的位置
- 如图中所示，将节点2插入到节点1的后面：
- 我们只需要将节点1的next指向待添加的这个节点即可
- 之前节点1是指向节点4，此时需要修改为节点1的next== 新节点的next(也就是图中的节点4)，这样就完成了添加操作
代码实现
//方式二添加：按照编号的顺序来添加
public void addOrderByNo(HeroNode heroNode){
//因为头结点不能动，因此还需要一个辅助指针来遍历帮助我们找到添加的位置
//由于是单链表，因此我们找的temp的位置位于添加位置的前一个节点，否则是添加不了的
HeroNode temp = head; //指向我们的head节点的指针
boolean flag = false; //flag标识添加的编号是否已经存在，默认是不存在的
while (true){
if (temp.next == null){ //表明已经是链表的末尾
break;
}
if (temp.next.no > heroNode.no){ //说明当前的位置的已经找到了，应该添加在temp的后面即可
break;
} else if (temp.next.no == heroNode.no){ //编号相等，说明已经存在该节点
flag = true;
break;
}
//指针往后移动，直到找到(遍历当前的链表)
temp = temp.next;
}
//判断flag的值，为true不能添加
if (flag){
System.out.printf("英雄编号%d存在，无法添加\n",heroNode.no);
}else {
heroNode.next = temp.next; //让新节点指向temp的下一个节点
temp.next = heroNode;
}
}
看着代码和注释再加上图中的分析，不难，我们来测试一把，代码如下：
//测试按照顺序添加
singleLinkList.addOrderByNo(node1);
singleLinkList.addOrderByNo(node4);
singleLinkList.addOrderByNo(node2);
singleLinkList.addOrderByNo(node3);
//显示链表
singleLinkList.show();
结果如图：
按照顺序添加的结果图.png
我们从结果中看到，是可以的，接下来我们来看看它的修改操作
修改操作思路分析
修改操作，我们通过编号去找，找到了直接替换即可，直接看代码：
//3.修改指定的链表节点
public void update(HeroNode newHeroNode){
//判断是否为null
if (head.next == null){
System.out.println("链表为null");
return;
}
//找到需要修改的节点位置，根据编号去找
//定义一个辅助变量
HeroNode temp = head;
boolean flag = false; //flag用来表示是否找到该节点
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);
}
}
- 测试代码如下：
//测试修改
HeroNode newHeroNode = new HeroNode(1,"宋江1","及时雨1");
singleLinkList.update(newHeroNode);
结果如图：
修改操作.png
通过结果可知我们的修改操作是可以的，分析代码中的注释写的很详细，接着我们来看删除操作
删除操作思路分析
删除思路分析图.png
如图中的操作一样我们删除节点4，首先需要找到的是要删除节点的前一个节点也就是图中的节点1，接着只需要将节点1的next指向节点7就可以，那么节点四的引用会被垃圾回收机制回收，注意：所有的操作基于辅助变量(temp)来完成，接下来我们看代码的实现
//4.删除节点
//通过比较编号来删除
//还是head不能动，需要我们来定义一个辅助变量来帮我们找到需要删除的节点的前一个位置
public void delete(int no){
//1.定义辅助变量
HeroNode temp = head; //先让他指向head节点
boolean flag = false; //是否找打要删除节点的前一个
while (true){
if (temp.next == null){ //说明已经遍历到最后一个节点了
break;
}
if (temp.next.no == no){ //说明找到待删除节点的前一个temp
flag = true;
break;
}
temp = temp.next; //后移遍历链表
}
//通过flag来判断是否找到
if (flag){
temp.next = temp.next.next;
}else {
System.out.printf("要删除的 %d 节点不存在\n",no);
}
}
- 测试代码：
System.out.println("删除后============================");
singleLinkList.delete(1);
singleLinkList.show();
-结果如图所示：
删除结果图.png
上述就是链表的基本操作，就到这里了....
网友评论