双向链表
一、与单链表的对比凸显优势
① 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
② 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除
二、双向链表实操
2.1 图解
双向链表1.png
2.2 双向链表的遍历
同单向链表一样，只是可以向前，也可以向后。
首先，进行节点定义：
//定义一个HeroNode2,每个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;
}
//toString方法
@Override
public String toString() {
return "HeroNode2 [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
//遍历显示双向链表的方法
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;
}
}
2.3 单链表的添加（默认添加到链表的最后）
(1) 先找到双向链表的最后这个节点 (2) temp.next = newHeroNode (3) newHeroNode.pre = temp;
//添加节点到双向链表最后
public void add(HeroNode2 heroNode){
// 因为head节点不能动，因此我们需要一个辅助遍历 temp
HeroNode2 temp = head;
// 遍历链表，找到最后
while (true) {
// 找到链表的最后
if (temp.next == null) {//
break;
}
// 如果没有找到最后, 将将temp后移
temp = temp.next;
}
// 当退出while循环时，temp就指向了链表的最后
// 形成一个双向链表
temp.next = heroNode;
heroNode.pre = temp;
}
2.4 双向链表的插入
模仿单链表简单进行修改
/第二种方式在添加英雄时，根据排名将英雄插入到指定位置(插入节点)
//(如果有这个排名，则添加失败，并给出提示)
public void addByOrder(HeroNode2 heroNode){
//因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
//因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
HeroNode2 temp = head;
boolean flag = false;//flag标志添加的编号是否存在，默认为false
while(true){
if(temp.next ==null){//说明temp已经在链表的最后--未找到
break;
}
if(temp.next.no > heroNode.no){ //位置找到，就在temp的后面插入
break;
}else if(temp.next.no == heroNode.no){
flag = true; //编号已经存在
break;
}
temp = temp.next; //遍历当前链表
}
//判断flag的值
if(flag){ //不能添加，说明编号存在
System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
}else{
//插入到链表中，temp的后面
heroNode.next = temp.next;
heroNode.pre = temp;
temp.next.pre = heroNode;
temp.next = heroNode;
}
}
2.5 双向链表的修改（同单向链表）
public void update(HeroNode2 newHeroNode) {
// 判断是否空
if (head.next == null) {
System.out.println("链表为空~");
return;
}
// 找到需要修改的节点, 根据no编号
// 定义一个辅助变量
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);
}
}
2.6 双向链表的删除
(1) 因为是双向链表，因此，我们可以实现自我删除某个节点 (2) 直接找到要删除的这个节点，比如 temp (3) temp.pre.next = temp.next (4) temp.next.pre = temp.pre;
// 从双向链表中删除一个节点,
// 说明
// 1 对于双向链表，我们可以直接找到要删除的这个节点
// 2 找到后，自我删除即可
public void del(int no) {
// 判断当前链表是否为空
if (head.next == null) {// 空链表
System.out.println("链表为空，无法删除");
return;
}
HeroNode2 temp = head.next; // 辅助变量(指针)
boolean flag = false; // 标志是否找到待删除节点的
while (true) {
if (temp == null) { // 已经到链表的最后
break;
}
if (temp.no == no) {
// 找到的待删除节点的前一个节点temp
flag = true;
break;
}
temp = temp.next; // temp后移，遍历
}
//判断flag
if(flag){
//找到可以删除
temp.pre.next = temp.next;
//如果是最后一个节点，就不需要执行下面这句话，否则会出现空指针
if(temp.next !=null){
temp.next.pre = temp.pre;
}
else{
System.out.println("要删除的节点不存在");
}
}
}
