双向链表的增删改查操作
程序员文章站
2024-03-22 14:09:04
...
代码:
public static void main(String[] args) {
//测试
System.out.println("双向链表的测试~~");
HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
HeroNode2 hero2 = new HeroNode2(3, "吴用", "智多星");
HeroNode2 hero3 = new HeroNode2(2, "卢俊义", "玉麒麟");
HeroNode2 hero4 = new HeroNode2(7, "林冲", "豹子头");
HeroNode2 hero5 = new HeroNode2(1, "宋江", "及时雨");
HeroNode2 hero6 = new HeroNode2(9, "吴用", "智多星");
HeroNode2 hero7 = new HeroNode2(8, "卢俊义", "玉麒麟");
HeroNode2 hero8 = new HeroNode2(6, "林冲", "豹子头");
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
/*doubleLinkedList.add(hero1);
doubleLinkedList.add(hero2);
doubleLinkedList.add(hero3);
doubleLinkedList.add(hero4);
doubleLinkedList.add(hero5);
doubleLinkedList.add(hero6);
doubleLinkedList.add(hero7);
doubleLinkedList.add(hero8);*/
doubleLinkedList.addByOrder(hero1);
doubleLinkedList.addByOrder(hero2);
doubleLinkedList.addByOrder(hero3);
doubleLinkedList.addByOrder(hero4);
doubleLinkedList.addByOrder(hero5);
doubleLinkedList.addByOrder(hero6);
doubleLinkedList.addByOrder(hero7);
doubleLinkedList.addByOrder(hero8);
doubleLinkedList.list();
/* //修改
HeroNode2 newHreo = new HeroNode2(7, "公孙胜", "入云龙");
doubleLinkedList.update(newHreo);
System.out.println("修改后的链表情况~~");
doubleLinkedList.list();
//删除
doubleLinkedList.del(9);
System.out.println("删除后的链表情况~~");
doubleLinkedList.list();*/
创建DoubleLinkedList类
//先初始化我们的头结点,头结点不要动,不存放具体数据
private HeroNode2 head = new HeroNode2(0, "", "");
public HeroNode2 getHead() {
return head;
}
//第二种方式添加英雄,根据排名将英雄插入到指定位置
public void addByOrder(HeroNode2 heroNode) {
//头节点不能动,我们需要通过辅助变量来帮助找到添加的位置
HeroNode2 temp = head;
boolean flag = false;//flag标志添加的编号是否存在,默认为false
boolean flag1 = false;//flag标志添加的编号是否存在,默认为false
while (true) {
if (temp.next == null) {//说明temp已经在链表后面
flag1 = true;
break;
} else if (temp.next.id == heroNode.id) {//说明希望添加的heroNode编号已经存在
flag = true;//说明编号存在
break;
} else if (temp.next.id > heroNode.id) {
break;
}
temp = temp.next;//后移,遍历链表
}
//判断flag的值
if (flag) {//说明编号存在
System.out.printf("准备插入的英雄编号%d已经存在\n", heroNode.id);
} else if (flag1){
//在temp后面插入
heroNode.next = temp.next;
temp.next = heroNode;
heroNode.pre = temp;
flag1 = false;
}else{//在temp后面插入
heroNode.next = temp.next;
temp.next.pre = heroNode;
temp.next = heroNode;
heroNode.pre = temp;
}
}
//添加一个节点到双向链表的最后
public void add(HeroNode2 heroNode) {
//因为head节点不能动,我们需要一个辅助遍历temp
HeroNode2 temp = head;
//遍历链表,找到最后
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
//当退出while循环时,temp就指向了链表的最后
//形成一个双向链表
temp.next = heroNode;
heroNode.pre = temp;
}
//修改一个节点的内容,可以看到双向链表节点内容修改和单向链表一样
//只是节点类型改成了HeroNode2
public void update(HeroNode2 newHeroNode) {
//判断是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//找到需要修改的节点,根据id编号
//定义一个辅助变量
HeroNode2 temp = head.next;
boolean flag = false;//表示是否找到该节点
while (true) {
if (temp == null) {
break;//链表遍历结束
}
if (temp.id == newHeroNode.id) {//找到
flag = true;
break;
}
temp = temp.next;
}
//根据flag判断是否找到需要修改的节点
if (flag) {//找到
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
} else {
System.out.printf("没有找到编号 %d 的英雄,不能修改\n", newHeroNode.id);
}
}
//从双向链表中删除一个节点
public void del(int id) {
if (head.next == null) {
System.out.println("链表为空,无法删除");
return;
}
HeroNode2 temp = head.next;
boolean flag = false;//标志是否找到待删除的节点
while (true) {
if (temp == null) {//已经到链表最后
break;
}
if (temp.id == id) {
//找到待删除节点的前一个节点
flag = true;
break;
}
temp = temp.next;//遍历
}
//判断flag
if (flag) {//找到
//可以删除
temp.pre.next = temp.next;
//这里代码有问题
//如果是最后一个节点不需要执行这句话,否则出现空指针异常
if (temp.next != null) {
temp.next.pre = temp.pre;
}
} else {
System.out.printf("要删除的 %d 节点不存在\n", id);
}
}
//显示链表【遍历】
public void list() {
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为头结点不能动,我们需要一个辅助变量来遍历
HeroNode2 temp = head.next;
while (true) {
//判断是否到链表最后
if (temp == null) {
break;
}
//输出节点信息
System.out.println(temp);
//将temp向后移
temp = temp.next;
}
}
//定义HeroNode 每个HeroNode对象是一个节点
public int id;//编号
public String name;//姓名
public String nickName;//外号
public HeroNode2 next;//指向下一个英雄节点
public HeroNode2 pre;//指向下一个英雄节点
public HeroNode2(int id, String name, String nickName) {
this.id = id;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "HeroNode2{" +
"id=" + id +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
上一篇: LeetCode 算法面试汇总 多数元素
下一篇: Day2 python基础知识