public class DoubleLinkedListDemo {
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.add(hero1);
// doubleLinkedList.add(hero3);
// doubleLinkedList.add(hero2);
// doubleLinkedList.add(hero4);
// 有序添加
doubleLinkedList.addByOrder(hero1);
doubleLinkedList.addByOrder(hero2);
doubleLinkedList.addByOrder(hero4);
doubleLinkedList.addByOrder(hero3);
doubleLinkedList.list();
// 根据编号修改节点
HeroNode2 newHero = new HeroNode2(2,"小卢","玉麒麟~~");
doubleLinkedList.update(newHero);
System.out.println("修改后的链表");
doubleLinkedList.list();
// 删除节点
doubleLinkedList.delete(4);
System.out.println("删除后的链表");
doubleLinkedList.list();
}
}
// 链表操作类
class DoubleLinkedList {
// 创建头节点 不能动
private HeroNode2 head = new HeroNode2(0,"","");
public HeroNode2 getHead() {
return head;
}
// 添加节点(同单向,但有点区别,加上前一个指针)
public void add(HeroNode2 heroNode2) {
// 存放指针 并寻找最后一个节点
HeroNode2 temp = head;
while (null != temp.next) {
// 指针后移
temp = temp.next;
}
temp.next = heroNode2;
heroNode2.pre = temp;
}
// 添加节点并排序
public void addByOrder(HeroNode2 heroNode2) {
if (null == head.next) {
// 空链表 要单独处理 因为头节点不需要pre属性
head.next = heroNode2;
heroNode2.pre = head;
return;
}
// temp 代表要插入位置的前一个节点
HeroNode2 temp = head;
boolean flag = false;
while (null != temp.next) {
if (temp.next.no > heroNode2.no) {
break; // 找见要插入的位置
} else if (temp.next.no == heroNode2.no) {
flag = true;
break; // 插入的位置已存在
}
temp = temp.next;
}
if (flag) {
System.out.printf("准备插入的英雄的编号 %d 已经存在了,不能加入n",heroNode2.no);
} else {
// 2代表找到位置(temp不代表尾节点)
heroNode2.pre = temp;
heroNode2.next = temp.next;
if (null != temp.next) {
// 如果temp是最后一个 则不需要将下一节点pre指向新节点(否则会有空指针)
temp.next.pre = heroNode2;
}
temp.next = heroNode2;
}
}
// 根据序号修改节点(同单向)
public void update(HeroNode2 newHeroNode2) {
// 直接从第一个节点查找
HeroNode2 temp = head.next;
boolean flag = false;
while (null != temp) {
if (temp.no == newHeroNode2.no) {
flag = true;
break; // 找见要修改的位置
}
temp = temp.next;
}
if (flag) {
temp.name = newHeroNode2.name;
temp.nickname = newHeroNode2.nickname;
} else {
System.out.printf("没有找到 编号 %d 的节点,不能修改n",newHeroNode2.no);
}
}
// 根据序号删除节点(直接找对应的节点,不需要和单链表一样,查找修改的前一个节点)
public void delete(int no) {
// 不能删除头结点(直接从第一个节点开始查找)
HeroNode2 temp = head.next;
boolean flag = false;
while (null != temp) {
if (temp.no == no) {
flag = true;
break; // 找见要删除的节点
}
temp = temp.next;
}
if (flag) {
// 删除节点 比如 1 2 3 删除2 让1指向3 让3指向1即可
temp.pre.next = temp.next;
if (null != temp.next){
// 如果删除的节点是最后一个 则不需要将下一节点指向前一个节点(否则会有空指针)
temp.next.pre = temp.pre;
}
} else {
System.out.printf("要删除的 %d 节点不存在n",no);
}
}
// 显示链表
public void list() {
if (null == head.next) {
return;
}
HeroNode2 temp = head.next;
while (null != temp) {
System.out.println(temp);
temp = temp.next;
}
}
}
// 链表节点类
class HeroNode2 {
public int no;
public String name;
public String nickname;
public HeroNode2 pre; // 指向前一个节点 默认null
public HeroNode2 next; // 指向下一个节点 默认null
public HeroNode2(int no,String name,String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode2{" +
"no=" + no +
",name='" + name + ''' +
",nickname='" + nickname + ''' +
'}';
}
}