单链表
通过链表来管理需要创建 每一个节点对象和一个单链表对象来管理我们的数据
image-20210808131958325
1. 小结上图
链表是以节点的方式来存储,是链式存储
每个节点包含 data 域， next 域：指向下一个节点.
如图：发现链表的各个节点不一定是连续存储.
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
image-20210808132048510
2. 单链表的应用实例
使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作
2.1 第一种方法在添加英雄时，直接添加到链表的尾部
image-20210808132202256
2.2 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
如果有这个排名，则添加失败，并给出提示)
思路的分析示意图
image-20210808132320632
2.3 第三种修改节点功能
思路:
(1) 先找到该节点，通过遍历，
(2) temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname
2.4 第四种删除节点
image-20210808132457846
3. 代码
//创建一个单向链表对象 管理节点
class SingleLinkedList {
//初始化头节点
public HeroNode head = new HeroNode(0, "", "");
//增
//1. 直接添加到末尾
public void add(HeroNode heroNode) {
HeroNode temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
//最后一个节点的next域指向新添加的节点
temp.next = heroNode;
}
//2. 按照no顺序排列
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
boolean flag = false;
while (true) {
//1.遍历到末尾直接添加
if (temp.next == null) {
break;
}
//2.该节点以及存在
if (temp.next.no == heroNode.no) {
flag = true;
break;
}
//3.正常添加
if (temp.next.no > heroNode.no) {
break;
}
temp = temp.next;
}
if (flag) {
System.out.println("该节点以及存在!");
} else {
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//删
public void delete(int no) {
HeroNode temp = head;
while (true) {
//1.如果没有节点怎么办
if (temp.next == null) {
System.out.println("没有该节点!");
return;
}
//2.该链表是否为null
if (head.next == null) {
System.out.println("链表为null");
return;
}
if (temp.next.no == no) {
break;
}
temp = temp.next;
}
temp.next = temp.next.next;
}
//改
public void update(HeroNode heroNode) {
HeroNode temp = head;
boolean flag = false;
while (true) {
//1.该编号节点不存在
if (temp.next == null) {
break;
}
//2.该链表是否为null
if (head.next == null) {
System.out.println("链表为null");
return;
}
if (temp.next.no == heroNode.no) {
temp.next.nickName = heroNode.nickName;
temp.next.name = heroNode.name;
}
temp = temp.next;
}
}
//查
public void list() {
//头节点不能动,辅助遍量
HeroNode temp = head.next;
while (true) {
//遍历,直到null
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
//创建一个节点对象 包含data和next
class HeroNode {
//data
public int no;
public String name;
public String nickName;
//next 默认为NULL
public HeroNode next;
//构造函数
public HeroNode() {
}
public HeroNode(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
//toString
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
", next=" + next +
'}';
}
}
面试题
1. 求单链表中有效节点的个数
public static int getLength(HeroNode head) {
//链表为null
if (head.next == null) {
return 0;
}
//链表不为null
int length = 0;
HeroNode temp = head;
while (true) {
if (temp.next == null) {
break;
}
length++;
temp = temp.next;
}
return length;
}
2. 查找单链表中的倒数第 k 个结点
//查找链表第倒数第k个节点
public static HeroNode getNode(HeroNode head, int k) {
//首先链表为null
if (head.next == null) {
return null;
}
int length = getLength(head);
//倒数超出范围
if (k > length || k<=0) {
return null;
}
HeroNode temp = head.next;
for (int i = 0; i < length - k; i++) {
temp = temp.next;
}
return temp;
}
3. 单链表的反转
思路分析图解
image-20210810071032779
image-20210810071040096
//单链表的反转
public static void reverseList(HeroNode head) {
int length = getLength(head);
if (head.next == null || length == 1) {
return;
}
//替换
HeroNode temp = head.next;
HeroNode cur = null;
//初始化反转头节点
HeroNode reverseHead = new HeroNode(0, "", "");
while (true) {
if (temp == null) {
break;
}
cur = temp.next;
temp.next = reverseHead.next;
reverseHead.next = temp;
temp = cur;
}
//回归原位
head.next = reverseHead.next;
}
注意点:
- 定义一个reverseHead来帮助我们遍历生成新
- 注意我们在交换temp的时候temp.next会发生变化
- 所以我们通过cur来提前记录temp.next
双链表
1. 管理单向链表的缺点分析:
单向链表，查找的方向
只能是一个方向，而双向链表可以向前或者向后查找。单向链表不能
自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).分析了双向链表如何完成遍历，添加，修改和删除的思路
image-20210810152553382
2. 对上图的说明:
分析 双向链表的遍历，添加，修改，删除的操作思路 代码实现
1. 遍历
方和 单链表一样，只是可以向前，也可以向后查找
2. 添加
(默认添加到双向链表的最后)
(1) 先找到双向链表的最后这个节点
(2) temp.next = newHeroNode
(3) newHeroNode.pre = temp;
3. 修改
- 思路和 原来的单向链表一样.
4. 删除
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如 temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
3.代码
//添加元素到双向链表
public void add(HeroNode2 heroNode) {
HeroNode2 temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
//最后一个节点的next域指向新添加的节点
temp.next = heroNode;
heroNode.pre = temp;
}
//修改一个节点的内容
public void update(HeroNode2 heroNode) {
HeroNode2 temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
System.out.println("不存在");
flag = true;
break;
}
if (temp.no == heroNode.no) {
break;
}
temp = temp.next;
}
if (flag) {
System.out.println("不沉溺在");
} else {
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
}
}
//删
public void delete(int no) {
HeroNode2 temp = head.next;
while (true) {
//2.该链表是否为null
if (head.next == null) {
System.out.println("链表为null");
return;
}
//1.如果没有节点怎么办
if (temp.no == no && temp.next != null) {
temp.pre.next = temp.next;
temp.next.pre = temp.pre;
return;
}
if (temp.next == null){
temp.pre.next = null;
break;
}
temp = temp.next;
}
}
//遍历双向链表的方法
public void list() {
//头节点不能动,辅助遍量
HeroNode2 temp = head.next;
while (true) {
//遍历,直到null
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
