[数据结构与算法]一文搞懂数据结构之 双向链表

查看上一篇文章

一文搞懂数据结构之 单向链表

和单向链表比较，双向链表多了一个必要的前驱节点指针变量。双向链表的每个节点记录了他的前驱和后继节点。可以往前遍历亦可以向后遍历

?单项链表增、删、插 、改时需关注的地方

? ? ? ? 1. 增加时

? ? ? ? 同样使用一个变量保存最后一次加入的节点的指针，暂且将这个指针命名为last

? ? ? ? last.next = node,node.pre = last, last = node

????????

public class DoubleLinkedList {
    private DHeroNode head = new DHeroNode();
    private DHeroNode last = head;

    // todo 增
    public void add(DHeroNode node){
        node.setPre(last);
        last.setNext(node);
        last = last.getNext();
    }

?2. 删除时：

? ? ? ? 双向链表可以自删除，所以不需要记录待删除节点的前驱节点,但是要注意，删除的节点是不是最后一个节点，如果是最后一个节点，只需要设置current.pre.next 即可。

设待删除节点 = current?

? ? ? ? current.pre.next = current.next; current.next.pre = current.pre

????????

 // todo 删
    public void remove(int no){
        DHeroNode temp = head;
        while ((temp = temp.getNext()) != null && temp.getNo() != no) {}
        // 找到了要删除的节点
        if (temp != null) {
            // 判断要删除的节点是不是最后一个
            if (temp.getNext() != null){
                // 不是的话就将下一个结点的前置节点连接到前一个结点
                temp.getNext().setPre(temp.getPre());
            }
            // 连接下一个节点
            temp.getPre().setNext(temp.getNext());
            return;
        }
        // 没找到要删除的节点
        System.out.println("未找到这个节点");
    }

?3. 插入时也很简单，注意点参考删除节点操作

4. 修改也没啥说的。

????????

package pers.uxteam.data;

public class DoubleLinkedList {
    private DHeroNode head = new DHeroNode();
    private DHeroNode last = head;

    // todo 增
    public void add(DHeroNode node){
        node.setPre(last);
        last.setNext(node);
        last = last.getNext();
    }

    // todo 删
    public void remove(int no){
        DHeroNode temp = head;
        while ((temp = temp.getNext()) != null && temp.getNo() != no) {}
        // 找到了要删除的节点
        if (temp != null) {
            // 判断要删除的节点是不是最后一个
            if (temp.getNext() != null){
                // 不是的话就将下一个结点的前置节点连接到前一个结点
                temp.getNext().setPre(temp.getPre());
            }
            // 连接下一个节点
            temp.getPre().setNext(temp.getNext());
            return;
        }
        // 没找到要删除的节点
        System.out.println("未找到这个节点");
    }
    // todo 是否为空
    public boolean isEmpty(){
        return head.getNext() == null;
    }
    // todo 改
    public void update(DHeroNode node){
        DHeroNode temp = head;
        while ((temp = temp.getNext()) != null && temp.getNo() != node.getNo()) {}
        if (temp != null){
            temp.setName(node.getName());
            temp.setNickName(node.getNickName());
        }
    }
    // todo 显示所有
    public void show(){
        DHeroNode temp = head;
        while ((temp = temp.getNext()) != null) {
            System.out.println(temp);
        }
    }
}

package pers.uxteam.data;

public class DHeroNode {
    /**
     * 英雄排名
     */
    private int no;
    /**
     * 英雄姓名
     */
    private String name;
    /**
     * 英雄称号
     */
    private String nickName;

    private DHeroNode pre;
    private DHeroNode next;

    public DHeroNode() {
    }

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    public DHeroNode getPre() {
        return pre;
    }

    public void setPre(DHeroNode pre) {
        this.pre = pre;
    }

    public DHeroNode getNext() {
        return next;
    }

    public void setNext(DHeroNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "DHeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}