单链表
单链表（其一）
单向链表的创建和添加
背景
-
数据结构——单向链表
-
博主以b站尚硅谷Java数据结构与算法课进行学习
概念
- 链表：
- 链表以节点的方式进行存储
- 每个节点包含data域和next域
- next域指向下一节点
- 链表的各个节点不一点按顺序存储
- 链表分带头节点和没有带头节点的链表
问题
- 使用带head头的单向链表实现–水浒传排行榜管理
- 完成对人物的增删改查
- 第一种方法在添加人物时，直接添加到链表的尾部
- 第二种方法在添加人物时，根据排名将人物插入到指点位置（如果有这个排名则添加失败，并给出提示）
思路分析
-
相关数据
- int no，String name，String nickName ，HeroNode next
- head节点
- 不存放具体的数据
- 作用就是表示单链表头
- next–指向下个节点
- HeroNode节点
- 数据
- next域
-
不需要按照编号顺序添加（创建）
- 先创建一个head头节点，作用就是表示单链表的头
- 后面我们添加每一个节点，就直接加入到链表的最后
-
遍历
- 通过一个辅助遍历，帮助遍历整个链表
-
需要按照编号顺序添加
-
首先找到新添加节点的位置，通过**辅助变量(temp)**找到
-
新的节点. next = temp.next
-
将temp.next = 新的节点
-
步骤
-
定义一个HeroNode类，每个HeroNode对象就是一个节点
-
相关属性
- int no，String name，String nickname HeroNode next；
-
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class 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方法
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
-
-
定义一个SingleLinkedList类------管理我们的人物
-
第一种方法，直接添加数据到尾部
-
先初始化一个头节点，头节点不能动，不能存放数据
-
代码实现
1
private HeroNode head = new HeroNode(0,"","");
-
-
当不考虑编号顺序时，先找到当前链表的最后节点，将最后节点next指向新的节点，因为head头节点不能动，所以需要辅助便利temp遍历
-
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public void add(HeroNode heroNode){
//当不考虑编号顺序时
//先找到当前链表的最后节点
//将最后节点next指向新的节点
//因为head头节点不能动，所以需要辅助遍历temp
HeroNode temp = head;
//遍历链表找到最后
while(true){
//代表找到链表的最后
if(temp.next==null){
break;
}
//找不到就将temp后移，直至找到后退出循环
temp = temp.next;
}
//当退出循环时，temp指向链表的最后
//将这个节点的next指向新节点
temp.next = heroNode;
}
-
-
-
第二种方法，按照顺序添加人物插入链表
-
先初始化一个头节点，头节点不能动，不能存放数据
-
代码实现
1
private HeroNode head = new HeroNode(0,"","");
-
-
头节点不能动，所以我们需要一个辅助变量temp来寻找添加的位置，因为是单链表，我们找的temp是位于添加位置的前一个节点，否则插入不了
-
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public void addByOrder(HeroNode heroNode){
//头节点不能动，所以我们需要一个辅助变量来寻找添加的位置
//因为是单链表，我们找的temp是位于添加位置的前一个节点，否则插入不了
HeroNode temp = head;
boolean flag = false;//flag标志添加的符号是否存在，默认为false
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的值
if(flag){//不能添加，编号存在
System.out.println("存在"+heroNode.no);
}else{
//插入链表中，temp的后面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
-
-
-
显示链表List方法
-
先判断链表是否为空，同时需要辅助变量
-
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//显示链表
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.next;
}
}
-
-
-
主类SingLinkedListDemo：测试
-
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public class SingLinkedListDemo {
public static void main(String[] args) {
//测试
HeroNode heroNode1 = new HeroNode(1,"宋江","及时雨");
HeroNode heroNode2 = new HeroNode(2,"卢俊义","玉麒麟");
HeroNode heroNode3 = new HeroNode(3,"吴用","智多星");
HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");
//创建链表
SingleLinkedList singleLinkedList = new SingleLinkedList();
//第一种方法加入
/* singleLinkedList.add(heroNode1);
singleLinkedList.add(heroNode4);
singleLinkedList.add(heroNode3);
singleLinkedList.add(heroNode2);*/
//第二种方法加入，按照顺序加入
System.out.println("===================================");
singleLinkedList.addByOrder(heroNode1);
singleLinkedList.addByOrder(heroNode4);
singleLinkedList.addByOrder(heroNode3);
singleLinkedList.addByOrder(heroNode2);
singleLinkedList.list();
}
}
-
运行结果图
-
第一种方法
-
第二种方法
