3.数据结构与算法学习笔记(单链表的增删改查)
链表(Linked List) 链表是有序的列表
1. 链表分两种,带头节点的链表和没有带头节点的链表,根据实际需求来确定
2. 链表是以节点的方式来存储的,是链式存储
3. 每个节点包括data域,next域,指向下一个节点
4. 如图:发现链表的各个节点不一定是连续存放的
文章图片
? 在内存中的实际结构
文章图片
? 逻辑结构
单链表的应用实例: 使用带head头的单向链表实现–水浒英雄排行榜的管理
1. 完成对英雄人物的增删改查操作2. 第一种方法在添加英雄时,直接添加到链表的尾部3. 第二种方法在添加英雄时,根据排名将英雄插入到指定位置
(如果有这个排名,则添加失败,并且给出提示)
【3.数据结构与算法学习笔记(单链表的增删改查)】思路分析:
添加:
1.创建一个head头节点,表示单链表的头
2.每添加一个节点,就直接加入到链表的最后遍历
3.判断遍历结果,如果next为空,那么就跳出循环,把添加进去的数据设置成这个节点对象的next(新节点)
4.如果不为空,那么把next(新节点)的值设置给节点,继续遍历新节点
文章图片
package com.ry.linkedlist;
public class singleLinkendDemo {
public static void main(String[] args) {
//进行测试
//先创建一个节点
heroNode her01 = new heroNode(1, "宋江", "及时雨");
heroNode her02 = new heroNode(2, "卢俊义", "玉麒麟");
heroNode her03 = new heroNode(3, "吴用", "智多星");
heroNode her04 = new heroNode(4, "林冲", "豹子头");
//创建一个链表
glLinkedList list = new glLinkedList();
list.add(her01);
list.add(her02);
//list.add(her03);
//list.add(her04);
//显示
list.list();
}
}//定义管理类
class glLinkedList{
//实例化一个固定的头节点,要保证它不能动
privateheroNode herd= new heroNode(0,"","");
//添加节点到单向链表
/*
* 思路:当不考虑编号序列时候
* 1.找到当前链表的最后节点
* 2.最后将这个节点的next指向新的节点
* */public voidadd(heroNode heronode){heroNode temp=herd;
//遍历链表找到链表的最后
while(true){
//如果找到了链表的最后
if (temp.next==null){
break;
}
//如果没有找到最后,将temp后移
temp=temp.next;
}
//当退出while循环的时候,temp就指向了链表的最后
//最后将这个节点的next指向新的节点
temp.next=heronode;
}//显示链表【遍历】
public void list(){
//判断链表是否为空
if(herd.next==null){
System.out.println("链表为空");
return;
}
//因为头节点不能动,因此我们需要一个辅助变量来遍历
heroNode temp=herd.next;
while(true){
//判断是否到链表最后
if (temp==null){
break;
}
//输出节点的信息
System.out.println(temp);
//将temp后移
temp=temp.next;
}}}
//定义一个英雄对象类
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 + '\'' +
", next=" + next +
'}';
}
}
增: 查: 单链表按顺序来插入节点
需要按照编号的顺序添加1.首先找到新添加的节点的位置,是通过辅助变量(指针),通过遍历来搞定2.新的节点的.next=temp.next3.将temp.next=新的节点
public void addByOrder (heroNode heronode){
//因为头节点不能动,因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
//因为单链表,因为我们要找的temp是位于添加位置的前一个节点,否则插入不了
heroNode temp=herd;
boolean flag=false;
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;
}
if (flag){
System.out.println("要插入的节点"+heronode.no+"已经存在");
}else {
heronode.next=temp.next;
temp.next=heronode;
}
}
改: 单链表节点的修改,根据编号来修改即编号不能修改
public void update(heroNode newheronode){
//判断节点的next是否为空
if(herd.next==null){
System.out.println("链表为空");
return;
}
//如果不为空
//找到需要修改的节点,根据编号
//定义一个辅助变量
heroNode temp=herd.next;
boolean flag=false;
while(true){
if (temp==null){
break;
//已经遍历完列表了
}
if (temp.no==newheronode.no){
//找到了
flag=true;
break;
}
//如果当前节点未找到,把指针后移一位
temp=temp.next;
}
//根据flag判断是否找到要修改的节点
if(flag){
//根据已经找到节点返回的flag,把编号相同的节点的值name和nickname修改
temp.name=newheronode.name;
temp.nickname=newheronode.nickname;
}else{
System.out.println("没有找到编号"+newheronode.no+"不能修改");
}
}
删: 从单链表中删除一个节点的思路
1.我们先找到需要删除的这个节点的前一个节点temp
2.temp.next=temp.next.next
3.被删除的节点,将不会有其他引用指向,会被垃圾回收机制回收
//删除节点
//1.head不能动,因此我们需要一个temp辅助节点找到待删除的节点
//2.我们在比较时,是temp.next.no和需要删除的节点的no进行比较
public void del(int no){
heroNode temp=herd;
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.println("要删除的"+no+"节点不存在");
}
}
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- Docker应用:容器间通信与Mariadb数据库主从复制
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 第326天
- Shell-Bash变量与运算符
- 画解算法(1.|画解算法:1. 两数之和)
- 逻辑回归的理解与python示例
- Guava|Guava RateLimiter与限流算法
- 我和你之前距离
- CGI,FastCGI,PHP-CGI与PHP-FPM