[数据结构与算法]Java数据结构Day7--双向链表增删改查

?双向链表

双向链表在构造上与单向链表的差距,
就是单向链表只有指向下一节点的next指针
但是双向链表同时有指向上一节点的pre指针

对于双向链表的改操作,在我们获得了需要修改的节点之后,将其下个节点的pre指向更改后的节点,将其前个节点的next指向更改后的节点.

对于双向链表的删除操作,在我们获得了需要删除的节点x之后,将x下个节点的pre指向x的前个节点,将x前个节点的next指向x后面的节点

对于删除操作需要额外注意空指针问题,如果删除的是最后一个位置的节点,需要做一个if判断.

?整体代码

import java.util.Scanner;

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        char key = ' ';//用来接收用户传入的指令
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        while (flag){
            System.out.println("=====1.显示链表=====");
            System.out.println("=====2.退出程序=====");
            System.out.println("=====3.添加数据到链表=====");
            System.out.println("=====4.查看某个节点=====");
            System.out.println("=====5.删除某个节点=====");
            System.out.println("=====6.修改某个节点=====");
            key = scanner.next().charAt(0);
            switch (key){
                case '1':
                    doubleLinkedList.show();
                    break;
                case '2':
                    flag = false;
                    break;
                case '3':
                    System.out.println("请创建节点对象:id,姓名,昵称 中间用逗号分隔");
                    String next = scanner.next();
                    String[] split = next.split(",");
                    HeroNodeNew insert = new HeroNodeNew(Integer.parseInt(split[0]), split[1], split[2]);
                    doubleLinkedList.add(insert);
                    break;
                case '4':
                    System.out.println("请输入查找的id");
                    int id = scanner.nextInt();
                    System.out.println(doubleLinkedList.find(id).next);
                    break;
                case '5':
                    System.out.println("请输入删除的id");
                    int id1 = scanner.nextInt();
                    doubleLinkedList.remove(id1);
                    break;
                case '6':
                    System.out.println("请输入修改的节点对象:id,姓名,昵称 中间用逗号分隔");
                    String next1 = scanner.next();
                    String[] split1 = next1.split(",");
                    HeroNodeNew insert1 = new HeroNodeNew(Integer.parseInt(split1[0]), split1[1], split1[2]);
                    doubleLinkedList.change(insert1);
            }
        }
    }
}
//
class DoubleLinkedList{
    //定义头结点,指向链表头位置
    private HeroNodeNew header = new HeroNodeNew(0,"","");
    //返回头结点
    public HeroNodeNew getHeader(){
        return header;
    }
    //遍历双向链表
    public void show(){
        if (header.next == null){
            System.out.println("链表为空");
        }else{
            System.out.println("============显示链表============");
            HeroNodeNew tmp = header.next;
            while (true){
                //每次循环,都要判断tmp是否为null,如果为null,说明已经没有节点了,要退出循环
                if (tmp == null){
                    break;
                }
                System.out.println(tmp);
                tmp = tmp.next;
            }
        }
    }
    //添加节点(尾部)
    public void add(HeroNodeNew node){
        HeroNodeNew tmp = header;
        while (true){
            if (tmp.next == null){
                break;
            }
            //如果next不为null,说明还不是最后一个,所以继续往下查
            tmp = tmp.next;
        }
        //到这一步,说明跳出了循环,所以tmp此时就代表了最后一个元素
        //所以我们将tmp的next指向了新插入的node.这就完成了插入.
        tmp.next = node;
         TODO: 2021/11/30 不同的地方
        node.pre = tmp;
        System.out.println("==========添加成功==========");
    }
    public HeroNodeNew find(int id) {
        //还是要借助临时变量
        HeroNodeNew tmp = this.header;
        while (true){
            if (tmp.next == null || tmp.next.no == id){
                //为了增加这个方法的复用性,我们返回要找的节点的上一个节点
                //这样这个方法就可以被在删除,修改中调用了
                return tmp;
            }
            tmp = tmp.next;
        }
    }
    //修改节点
    public void change(HeroNodeNew node) {
        //找到原节点的前一个节点
        HeroNodeNew frontNode = find(node.no);
        //修改指向
        node.next = frontNode.next.next;
        frontNode.next = node;
         TODO: 2021/11/30 新增的部分 
        node.pre = frontNode;
        System.out.println("执行修改完成");
    }
    public void remove(int id) {
        //对于删除来说,首先find()找的是该节点的前一个节点
         TODO: 2021/11/30 但是在双向链表中,已经不需要借助临时节点了
        //下面得到的就是对应id的节点,因为find()找的是对应id的前一个!!!!
        HeroNodeNew next = find(id).next;
        //将后一个节点的前指针指向前一个节点
        next.pre.next = next.next;
        //将前一个节点的后指针指向后一个节点
         TODO: 2021/11/30 要考虑到,如果是删除的是尾节点,可能存在空指针问题,所以进行优化
        try {
            next.next.pre = next.pre;
        } catch (Exception e) {
            System.out.println("删除成功");
            return;
        }
        System.out.println("=====删除成功======");
    }
}
class HeroNodeNew { //一个HeroNode,就代表一个节点
    int no; //节点编号
    String name; //节点姓名  --不重要
    String nickName; // 节点小名(昵称)  --不重要
    public HeroNodeNew next; //后一个节点
     TODO: 2021/11/30 新添加--前一个节点的指向
    public HeroNodeNew pre; //前一个节点★★★★★★★★★★

    public HeroNodeNew(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    //重写toString方法
    @Override
    public String toString() {
        return "HeroNodeNew{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}