本篇博客是根据b站尚硅谷老师的数据结构教程,学习后写的学习笔记
部分概念和图片均来自视频,代码和截图均为自己动手,本篇博客的重点在自己编写的代码注释上
尚硅谷Java数据结构与java算法(Java数据结构与算法)
单链表
链表是有序的列表(Linked List),在内存中的存储方式如上图所示
(1)链表是以节点的方式来存储,是链式存储
(2)每个节点包含data域,next域。其中,data域用来保存当前节点要存储的数据,next域用来指向下一个节点
(3)链表的各个节点不一定是连续存储
(4)链表分为带头节点的链表和没有头节点的链表,根据实际的需求来确定
单链表(带头节点)逻辑结构示意图如下
这里看起来像是顺序连续存储,但实际上不是,下一个节点是什么,由next域来决定
单链表完整代码
节点类,用来创建一个新节点
//定义HeroNode,每个HeroNode对象就是一个节点
class 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;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
创建单链表
class SingleLinkedList{
//先初始化一个头节点,头节点不存放具体的数据,被初始化后就不要修改移动
private HeroNode head = new HeroNode(0,"","");
}
一个完整的单链表应该可以实现节点的增删改查,所以
接下来就是往这个单链表类里面加上添加节点,删除节点,修改节点,遍历输出等方法
将新节点添加到单链表尾部
//方式一:添加节点到单向链表
//思路,当不考虑编号顺序时,只需要找到当前链表的最后一个节点,然后让这个节点的next指向新的节点
public void add(HeroNode heroNode){
//通过一个辅助变量temp来遍历当前的链表,temp用来指向当前的节点
HeroNode temp = head;
//遍历链表找到最后一个节点
while(true){
if(temp.next == null){ //如果next为null,说明temp指向的当前节点是最后一个节点
break;
}
//如果next不为空,则temp指向 next指向的节点对象,从而达到temp后移的效果
temp = temp.next;
}
//通过break退出while循环的时候,temp就指向了链表的最后一个节点
//让这个节点的next指向需要新加入链表的heroNode对象
temp.next = heroNode;
}
将新节点按照编号插入到指定位置
//方式二:添加节点到单链表,根据编号no将节点插入到指定位置
//而不是像方式一那样全部添加到单链表的最后
public void addByNo(HeroNode heroNode){
//同样借助temp来遍历整个单链表,temp初始等于head,说明从head开始遍历
HeroNode temp = head;
//如果要插入的位置已经有了相同编号no的节点,则不插入
//flag为false说明没有重复节点,flag为true说明有重复编号no的节点
boolean flag = false;
/*
temp一开始指向的是头节点,然后往后面遍历,heroNode是要插入的新节点
拿heroNode的编号no 与 temp.next指向节点的编号no比较
1. temp.next == null,说明已经来到链表最后,此时就像方式一将节点插入到链表末尾
2. temp.next.no < heroNode.no,则temp继续往后面遍历
3. temp.next.no == heroNode.no,将false置为true,说明有重复节点
4. temp.next.no > heroNode.no,则当前temp.next的位置即为heroNode的正确位置
第1和4中情况都说明找到插入位置,应该结束while循环,完成新节点的插入
*/
while(true){
if(temp.next == null){
break;
}
if (temp.next.no > heroNode.no){
break;
}
else if(temp.next.no == heroNode.no){
flag = true;
break;
}
temp = temp.next; //让temp后移遍历整个链表
}
if(flag){
System.out.printf("准备插入的编号 %d 已经存在,插入失败\n",heroNode.no);
} else {
//将heroNode插入到temp的后面,即temp.next的位置
heroNode.next = temp.next;
temp.next = heroNode;
}
}
修改节点
//修改节点
public void update(HeroNode newHeroNode){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
}
//根据no编号找到需要修改的节点
//同样定义temp变量用来遍历链表
HeroNode temp = head.next;
//判断是否找到需要修改的节点,默认为false为找到,找到则为true
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);
}
}
删除节点
//删除节点
//temp指向需要删除节点的前一个节点
//比较时,是temp.next.no 和 需要删除节点的no 比较
public void del(int no){
HeroNode temp = head;
boolean flag = false; //用来标志是否找到了待删除节点
while(true){
if(temp.next == null){
//表示没有找到待删除节点,不修改flag,默认为false
break;
}
if(temp.next.no == no){
//只有这个情况才算是找到了待删除节点,把flag置为true
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.next = temp.next.next;
}else{
System.out.printf("需要删除的编号为 %d 的节点不存在\n",no);
}
}
显示全部节点
//显示链表
public void list(){
//先判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
}
//同样通过辅助变量temp来遍历整个链表
HeroNode temp = head.next;
while(true){
//判断链表是否到了最后
if(temp==null){
break;
}
//输出节点的信息
System.out.println(temp);
//temp后移,指向下一个节点
temp = temp.next;
}
}
main函数
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.addByNo(hero1);
singleLinkedList.addByNo(hero3);
singleLinkedList.addByNo(hero4);
singleLinkedList.addByNo(hero2);
//创建一个新节点
HeroNode newHeroNode = new HeroNode(2,"卢","玉");
singleLinkedList.update(newHeroNode);
singleLinkedList.del(4);
//显示链表
singleLinkedList.list();
}
最终结果为
双向链表
双向链表与单向链表不同,单向链表每个节点只有一个next用来指向下一个节点,而双向链表每个节点有一个pre用来指向上一个节点,有一个next用来指向下一个节点。
图片来源:http://c.biancheng.net/view/3342.html
双向链表代码
创建节点
//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode2{
public int no;
public String name;
public String nickname;
public HeroNode2 next; //指向下一个节点
public HeroNode2 pre; //指向前一个节点
public HeroNode2(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
创建一个双向链表
//创建一个双向链表
class DoubleLinkedList{
//创建一个头节点head
HeroNode2 head = new HeroNode2(0,"","");
//返回头节点
public HeroNode2 getHead(){
return head;
}
}
将新节点插入到双向链表的最后面
public void add(HeroNode2 heroNode){
//通过一个辅助变量temp来遍历当前的链表,temp用来指向当前的节点
HeroNode2 temp = head;
while(true){
if(temp.next == null){
break;
}
temp = temp.next;
}
//通过break退出while循环的时候,temp就指向了链表的最后一个节点
//将新增节点加入到双向链表的最后面
temp.next = heroNode;
heroNode.pre = temp;
}
按照编号将新节点插入到指定位置
//按照编号插入节点
public void addByNo(HeroNode2 heroNode){
HeroNode2 temp = head;
boolean flag1 = false;
boolean flag2 = false;
while(true){
if(temp.next == null){
flag2 = true;
break;
}
if(temp.next.no > heroNode.no){
break;
}
if(temp.next.no == heroNode.no){
flag1 = true;
break;
}
temp = temp.next;
}
if(flag1){
System.out.println("节点的no重复,插入失败");
}else{
if(!flag2){
temp.next.pre = heroNode;
heroNode.next = temp.next;
}
heroNode.pre = temp;
temp.next = heroNode;
}
}
修改节点
//修改节点,与单链表里面的修改方法一样,只是改了节点类型
public void update(HeroNode2 newHeroNode){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
}
HeroNode2 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);
}
}
删除节点
//从双向链表中删除一个节点
//对于双向链表,只需要找到待删除节点,然后自我删除即可
public void del(int no){
//判断当前链表是否为空
if(head.next == null){
System.out.println("当前链表为空,无法删除");
}
//不需要找前一个节点,因此temp可以从head.next节点开始遍历,而不是head节点
HeroNode2 temp = head.next;
boolean flag = false; //用来标志是否找到了待删除节点
while(true){
if(temp == null){
//表示没有找到待删除节点,不修改flag,默认为false
break;
}
if(temp.no == no){
//只有这个情况才算是找到了待删除节点,把flag置为true
flag = true;
break;
}
temp = temp.next;
}
if(flag){
//找到待删除节点,可以直接删除
temp.pre.next = temp.next;
//如果temp正好是最后一个节点,那么上一句话等同于temp.pre.next = null
//但是temp.next就是null,不能用null调用pre指针,因此需要加上一个判断
//当temp是最后一个节点时,就不用执行下面这句话了
if(temp.next != null){
temp.next.pre = temp.pre;
}
}else{
System.out.printf("需要删除的编号为 %d 的节点不存在\n",no);
}
}
显示全部节点
//显示链表
public void list(){
//先判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
}
//同样通过辅助变量temp来遍历整个链表
HeroNode2 temp = head.next;
while(true){
//判断链表是否到了最后
if(temp==null){
break;
}
//输出节点的信息
System.out.println(temp);
//temp后移,指向下一个节点
temp = temp.next;
}
}
main函数
public static void main(String[] args) {
//创建节点
HeroNode2 hero1 = new HeroNode2(1,"宋江","及时雨");
HeroNode2 hero2 = new HeroNode2(2,"卢俊义","玉麒麟");
HeroNode2 hero3 = new HeroNode2(3,"吴用","智多星");
HeroNode2 hero4 = new HeroNode2(4,"林冲","豹子头");
//创建一个双向链表
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
doubleLinkedList.addByNo(hero1);
doubleLinkedList.addByNo(hero4);
doubleLinkedList.addByNo(hero2);
doubleLinkedList.addByNo(hero3);
doubleLinkedList.list();
}
虽然插入顺序不同,但最终双向链表中节点是按照编号no的顺序从小到大排列的
加上修改和删除语句
//修改
HeroNode2 newHeroNode = new HeroNode2(4,"零充","没钱");
doubleLinkedList.update(newHeroNode);
//删除
doubleLinkedList.del(1);
doubleLinkedList.list();