[数据结构与算法]双链表增删改查+排序插入

思考

双向链表，遍历，添加，修改，删除的思路
遍历：与单链表意义，但是可以双向查找
添加：默认添加到表尾，
      先找到要最后一个节点tmp
     1.newHeroNode.next = tmp.next;把后面的连上
     2.newHeroNode.prev = tmp ;
     3. newHeroNode.next = newNode.prev 把前面的连上
修改：与原来单向链表一样，之间找到要修改的节点

 删除：找到要删除的节点 p
 p.prev.next = p.next ;
 p.next.prev = p.prev;

节点类

 class DHeroNode{
    public DHeroNode prev;
    public int no;
    public DHeroNode next;
    public String name;
    public String nickname;

     public DHeroNode(int no, String name, String nickname) {
         this.no = no;
         this.name = name;
         this.nickname = nickname;
     }

     public DHeroNode() {
     }

     @Override
     public String toString() {
         return "[no："+ no
                 +",name：" + name
                 + ",nickname：" +nickname
                 +"]";
     }
 }

链表类

class DoubleLinkedList{
    private DHeroNode head = new DHeroNode(0,"","");

    //遍历打印
    public void list(){
        if(head.next == null){
            System.out.println("链表是空的");
            return;
        }
        DHeroNode tmp = head.next;
        while(tmp != null){
            System.out.println(tmp);
            tmp = tmp.next;
        }
    }
    //添加节点到末尾
    public void addToEnd(DHeroNode newHero){
        DHeroNode tmp = head;
        while(tmp.next != null){
            tmp = tmp.next;
        }//循环完毕时，tmp指向最后一个节点
        newHero.next = null;//将新加结点后一个赋空值
        tmp.next = newHero;
        newHero.prev = tmp;
    }
    //修改指定位置元素
    public void update(DHeroNode heroNode){
        if(head.next == null){
            System.out.println("表为空");
            return ;
        }
        DHeroNode tmp = head.next;
        boolean flag = false;
        while(true){
            if(tmp == null){//遍历完毕
                break;
            }if(heroNode.no == tmp.no){
                flag = true;
                break;
            }
            tmp = tmp.next;//不断下移
        }
        if(flag){
            tmp.name = heroNode.name;
            tmp.nickname = heroNode.nickname;
        }else{
            System.out.println("没找到此节点，不能修改");
        }
    }
    //获取长度
    public int getLength(){
        if(head.next == null){
            System.out.println("表为空");
            return 0;
        }
        DHeroNode cur = head.next;
        int len = 0;
        while(cur != null){
            len++;
            cur = cur.next;
        }
        return len;
    }
    //删除节点
    public void delete(int no){
        if(head.next == null){
            System.out.println("链表为空，不能删除");
            return;
        }
        DHeroNode tmp = head.next;
        boolean flag = false;
        while(tmp != null){
            if(tmp.no == no){
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if(flag){
            tmp.prev.next = tmp.next;
            //如果是最后一个节点回出现问题
            if(tmp.next != null) {
                tmp.next.prev = tmp.prev;
            }
        }else {
            System.out.println("没找到该节点");
        }
    }

    //按照编号顺序添加
    public void addByOrder(DHeroNode heroNode){
        if(head.next == null) {
            head.next = heroNode ;
            return;
        }
        //插入位置在队首
        DHeroNode tmp = head.next;
        if(heroNode.no < tmp.no){
            head.next = heroNode;
            heroNode.next = tmp;
            heroNode.prev = head;
            tmp.prev = heroNode;
            return;
        }
        while(tmp != null) {
            if (tmp.next != null) {//插入位置在中间
                if (tmp.no < heroNode.no && heroNode.no < tmp.next.no) {
                    heroNode.next = tmp.next;
                    tmp.next.prev = heroNode;
                    tmp.next = heroNode;
                    heroNode.prev = tmp;
                    return;
                }
            }
            if (tmp.next == null) {//插到末尾
                if (tmp.no < heroNode.no) {
                    heroNode.next = null;//先连接后面
                    heroNode.prev = tmp;
                    tmp.next = heroNode;
                    return;
                }
            }
            tmp = tmp.next;
        }
    }
}

测试

public class DLinkedListDemo {
    public static void main(String[] args) {
        DHeroNode heroNode1 = new DHeroNode(1, "宋江", "及时雨");
        DHeroNode heroNode2 = new DHeroNode(2, "卢俊义", "玉麒麟");
        DHeroNode heroNode3 = new DHeroNode(3, "吴用", "智多星");
        DHeroNode heroNode4 = new DHeroNode(4, "林冲", "豹子头");
        DHeroNode heroNode5 = new DHeroNode(5, "鲁智深", "花和尚");

        DoubleLinkedList singleLinkedList1 = new  DoubleLinkedList();
        singleLinkedList1.addByOrder(heroNode5);
        singleLinkedList1.addByOrder(heroNode1);
        singleLinkedList1.addByOrder(heroNode2);
        singleLinkedList1.addByOrder(heroNode4);
        singleLinkedList1.addByOrder(heroNode3);
        singleLinkedList1.list();


//        System.out.println("修改");
//        singleLinkedList1.update(new DHeroNode(3,"公孙胜","入云龙"));
//        singleLinkedList1.list();
//        System.out.println("删除");
//        singleLinkedList1.delete(3);
//        singleLinkedList1.list();
//        System.out.println(singleLinkedList1.getLength());
    }
}

小结

在删除节点时，注意未节点的删除与其他节点删除不同，tail.next.prev = tail.prev会报空指针异常，
插入操作要注意不要弄丢指针，可以多使用两个临时节点用来记录要删除节点tmp的前一个节点tmp.next和后一个节点tmp.prev
头指针不能动