【数据结构】—— 单链表的增删改查
方法重写
在学习之前先要了解什么是方法重写,简单来说,方法重写就是子类可继承父类中的方法,而不需要重新编写相同的方法,但有时子类并不想原封不动地继承父类的方法,而是想作一定的修改,这就需要采用方法的重写。方法重写又称方法覆盖。
重写条件
(1)必须是继承关系
(2)子类中的方法要和父类一样
(3)重写是发生在两个类中
重写好处
子类扩展了父类中的方法,让父类中的功能变得更加强大。
注意:如果子类想调用父类方法,直接在重写方法中使用 super 关键字重写父类中的方法,且方法的修饰符必须是公共的,私有方法不可以重写。
重写演示
编写一个父类Animal
public class Animal { //创建一个父类 Animal
public String name;//属性
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public void eat() {
System.out.println("喜欢……");
}
}
再编写一个子类Dog,并继承父类
public class Dog extends Animal{//子类 Dog 继承父类 Animal
@Override //方法重写的标记,看到此标记就代表方法重写现象
public void eat() {
//方法重写现象,在该类中eat方法和父类Animal中的eat方法的名称一样
super.eat();//调用父类的 eat 方法
System.out.println("吃骨头……");
}
}
编写Demo类进行演示
public class Demo {
public static void main(String[] args) {
Dog dog = new Dog();
dog.setName("哈士奇……");
System.out.println(dog.getName());
dog.eat();
}
}
查看输出结果
单链表
介绍
(1)链表是以节点的方式来存储的,是链式存储
(2)每个节点包含data域,next域:指向下一个节点
(3)如上图:发现链表的各个节点不一定是连续存储的
(4)链表分带头节点的链表和没有头节点的链表,根据实际需求来确定单链表(带头节点)
单链表的增删改查
创建HeroNode类,用来存放信息
//定义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;
}
//为了显示方法,这里重写 toString() 方法
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' + "}";
}
}
创建SingleLinkedList类,用来存放方法
按顺序插入到链表最后
(1)先创建一个 head头节点,作用就是表示单链表的头
(2)后面每添加一个节点,就直接加入到链表最后,也可以理解为每有一个新节点,我们就把最后一个节点的 next域 指向新节点
链表为空的条件:head.next == null(表示头节点的下一位为空)
链表最后的条件:temp.next == null (temp为辅助变量)
//先初始化一个头节点,头节点不要动,如果改动头节点那么就不好去找到链表最顶端的节点了
private HeroNode head = new HeroNode(0 , "" , "");
//头节点不存放具体的数据
public HeroNode getHead() {//返回头节点
return head;
}
//思路:
//1.找到当前链表的最后一个节点
//2.将最后这个节点的next域指向新的节点
public void add(HeroNode heroNode) {
//因为head头节点不能动,所以需要一个辅助变量temp
HeroNode temp = head;//将temp指向head
//遍历链表,找到链表最后
while(true) {
//当temp的域等于空时,说明temp找到了链表最后了
if(temp.next == null) {//找到最后了,结束程序
break;
}
//如果没有找到最后,就将temp 后移指向下一个数据
temp = temp.next;
}
//当退出了 while 循环时,那么 temp 就指向了链表的最后
temp.next = heroNode; //将最后这个节点的next域指向新的节点
}
按照编号的顺序添加
(1)首先找到新添加节点的位置,是通过辅助变量找到的
(2)添加方法:
1)新的节点.next = temp.next
2)temp.next = 新的节点
public void addByOrder(HeroNode heroNode) {
//因为头节点不能动,因此需要通过一个辅助指针(变量)来帮助找到添加的位置
//因为是单链表,所以辅助变量temp应该是位于添加位置的前一个节点,否则无法插入
HeroNode temp = head;
boolean flag = false;//flag标志添加的编号是否存在,默认为false
while(true) {
if(temp.next == null) {//说明temp已经到了链表最后
break;
}
if(temp.next.no > heroNode.no) {//位置找到,就在temp的后面插入
//如果temp.next.no > heroNode.no
//说明 heroNode 就应该插入到 temp 和 temp.next 之间
break;
}
if(temp.next.no == heroNode.no) {
//说明希望添加的heroNode的编号以及存在
flag = true;
break;
}
temp = temp.next;//如果三个条件都不符合就将 temp 后移,继续遍历
}
//判断flag的值
if(flag) {
//如果 flag == true。说明编号已存在,所以无法插入
System.out.printf("准备插入的编号%d已经存在,无法插入",heroNode.no);
} else {
//否则可以插入到链表中,temp 的后面
heroNode.next = temp.next;
temp.next = heroNode;
}
}
编写显示该链表的方法
//显示链表[遍历]
public void list() {
//先判断链表是否为空
if(head.next == null) { //说明了链表为空
System.out.println("链表为空");
return;
}
//如果链表不为空,且头节点不能动,因此需要一个辅助变量来遍历
HeroNode temp = head.next;
//因为已经判断了链表不为空,说明链表至少有一个数据,所以是 head.next(头节点指向的下一个数据)
while(true) {
//判断是否已经到了链表最后
if(temp == null) {
//遍历是到了链表最后,所以退出循环
break;
}
//如果不为空,则输出该节点的信息
System.out.println(temp);//已经重写了 toString()
//输出后需要将temp后移一位,因为输出该信息后需要让temp指向下一位,输出下一位的信息
temp = temp.next;//不后移就是一个死循环
}
}
修改节点信息
//修改节点的信息,根据no编号来修改,即no编号不能改
//根据newHeroNew 的 no 来进行修改即可
public void update(HeroNode newHeroNew) {
//判断是否为空
if(head.next == null) {
System.out.println("该链表为空");
return;
}
//找到需要更改的节点,根据no编号
//定义一个辅助变量
HeroNode temp = head.next;//temp 赋的值为头节点的下一个节点
boolean flag = false;//表示是否找到了该节点
while(true) {
if(temp == null) {
//说明链表已经遍历完成,因为temp 指向的是下一个节点(需要注意,和上面不同)
break;
}
if(temp.no > newHeroNew.no) {
//因为temp 指向的是下一个节点。
//所以就不需要 temp.next.no 了(需要注意,和上面不同)
//位置找到,就在temp后面进行添加
break;
}
if(temp.no == newHeroNew.no) {
//因为temp 指向的是下一个节点。所以就不需要 temp.next.no 了(需要注意,和上面不同)
//说明希望添加的编号已经存在
flag = true;
break;
}
temp = temp.next;//如果循环没有结束就一直进行遍历
}
//根据 flag 来进行判断是否找到了要修改的节点
if(flag) {//如果flag 为 true 说明就找到了要修改的节点
temp.name = newHeroNew.name;
temp.nickname = newHeroNew.nickname;
//注意:no 编号不可以修改
} else { //说明没有找到要修改的节点
System.out.printf("没有找到编号等于%d的节点\n",newHeroNew.no);
}
}
删除节点
(1)先找到需要删除的这个节点的前一个节点 temp
(2)temp.next = temp.next.next
(3)被删除的节点,将不会有其他引用指向,会被垃圾回收机制回收
/*
思路
1.head 节点不能动,因此我们需要一个 temp 辅助接点找到待删除的前一个节点
2.说明我们在比较时,是 temp.next.no 和需要删除的节点的 no 比较
*/
public void delete(int no) {
HeroNode temp = head;
boolean flag = false;//标志是否找到了待删除的节点
while(true) {
if(temp.next == null) {//已经到链表的最后了
break;
}
if(temp.next.no == no) {
//找到了待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next;//让 temp 后移,实现遍历
}
//判断 flag
if(flag) {
//如果flag位真,找到了要删除的节点,可以删除
temp.next = temp.next.next;//将temp的下下个节点赋给下个节点(删除temp的下个节点)
} else {
System.out.printf("要删除的%d节点不存在\n",no);
}
}
编写SingleLinkedListDemo类进行演示
public class SingleLinkedListDemo {
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.addByOrder(hero1);
// singleLinkedList.addByOrder(hero4);
// singleLinkedList.addByOrder(hero3);
// singleLinkedList.addByOrder(hero2);
//显示
singleLinkedList.list();
// 测试要修改节点的代码
// System.out.println("=====修改后的链表为=====");
// HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~~");
// singleLinkedList.update(newHeroNode);
//
// //显示
// singleLinkedList.list();
//删除一个节点
// System.out.println("=====删除后的链表为=====");
// singleLinkedList.delete(1);
// singleLinkedList.delete(4);
//
// //显示
// singleLinkedList.list();
// //显示该链表中有效节点的个数
// System.out.println("=====该链表中有效节点的个数是=====");
// System.out.println(getlength(singleLinkedList.getHead()));
//
// //测试一下看看是否得到了倒数第k个节点
// HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);
// System.out.println("res= " + res);
// //测试单链表的反转功能
// System.out.println("=====原来链表的情况=====");
// singleLinkedList.list();
// System.out.println("=====反转后的链表情况=====");
// reverseList(singleLinkedList.getHead());
// singleLinkedList.list();
}
}
- 点赞
- 收藏
- 关注作者
评论(0)