Linked List 单向链表
Linked List
链表的理解
小结
- 链表是以节点的方式来储存的
- 每个节点包括 data域：存放数据，next域：指向下一个节点
- 如图：发现链表的各个节点不一定是连续储存的
- 链表分为带头节点的链表和没有头结点的链表，这样根据实际需求而定。
单向链表
添加
添加到最后
- 找到链表的最后一个节点[通过节点的
next == null] - 将最后这个节点的
next指向新的节点
//初始化一个头结点,里面什么都不放
HeroNode head = new HeroNode(0, "", "");
/**
* 向链表中添加一个节点
* 不考虑编号顺序
*/
public void add(HeroNode heroNode) {
//因为头节点是不能动的，使用中间变量temp来保存头节点
HeroNode temp = head;
//遍历节点，找到最后一个节点【通过最后一个节点next指向为 null】
while (true) {
if (temp.next == null) {
//找到最后一个节点
break;
}
//没有找到就将temp后移一个
temp = temp.next;
}
// 当循环退出的时候temp就指向节点的最后一个
temp.next = heroNode;
}
考虑编号顺序添加
-
找到新添加节点的位置，通过辅助变量(
temp)[遍历找到新节点的位置] -
新的节点.next = temp.next -
temp.next = 新的节点
/**
* 考虑排序编号添加
*
* @param heroNode
*/
public void addByOrder(HeroNode heroNode) {
//因为头节点是不能动的,使用辅助变量temp寻找位置
HeroNode temp = head;
//用来代表当前添加的节点的编号是否存在，默认false不存在
boolean 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) {
//需要添加的节点已经存在
flag = true;
break;
}
//三个条件不成立 temp后移
temp = temp.next;
}
if (flag) {
//不能添加，编号存在
System.out.printf("当前添加的英雄编号 %d 已经存在， 不能添加\n", heroNode.no);
} else {
//在temp后面进行添加
heroNode.next = temp.next;
temp.next = heroNode;
}
}
修改
- 使用
temp.no == newHeroNode.no判断是否为需要修改的节点
/**
* 更新节点
*
* @param newHeroNode
*/
public void update(HeroNode newHeroNode) {
if (head.next == null) {
System.out.println("当前链表为空");
return;
}
//因为头节点是不能动的，使用中间变量temp来保存头节点
HeroNode temp = head;
boolean flag = false; //用来表示链表中是否存在需要修改的节点
while (true) {
if (temp.next == null) {
break;
}
if (temp.no == newHeroNode.no) {
flag = true;
break;
}
temp = temp.next; //temp后移
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
} else {
System.out.printf("没有找到编号为：%d 节点", newHeroNode.no);
}
}
删除
- 找到需要删除的节点的前一个节点
temp temp.next = temp.next.next- 被删除的节点 将不会有其他引用指向，会被垃圾回收机制回收
/**
* 删除节点
*
* @param no
*/
public void del(int no) {
if (head.next == null) {
System.out.println("当前链表为空");
return;
}
//因为头节点是不能动的，使用中间变量temp来保存头节点
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);
}
}
dataStructures: gitee
dataStructures: github
