[数据结构与算法]逆向行驶！数据结构双向链表DoubleLinkedList，Java实现增删改查

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

节点类

//节点类
class DNode {
    //数据域
    public int id;
    public String name;
    //指针域
    public DNode next; //指向后一个节点
    public DNode pre; //指向前一个节点

    public DNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

链表类

//链表类（管理节点）
class DoubleLinkedList {
    //头节点
    private DNode head = new DNode(0,null);

    //展示链表
    public void list(){
        if (head.next == null){
            System.out.println("链表为空！");
            return;
        }
        DNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //增（在链表尾部）
    public void add1(DNode newNode){
        //因为头节点不能动，因此要一个辅助变量temp
        DNode temp = head;
        //遍历找到最后
        while (true){
            if (temp.next == null){
                break;
            }
            temp = temp.next;
        }
        //当退出while就意味着找到最后一个节点了
        temp.next = newNode;
        newNode.pre = temp;
    }

    //删(根据id匹配删除)
    public void remove(int id){
        if (head.next == null){
            System.out.println("链表为空!");
            return;
        }
        DNode temp = head.next;
        boolean flag = false; //用来标记是否找到对应id的节点
        while (true){
            if (temp == null){
                break;
            }
            if (temp.id == id){ //找到要删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.pre.next = temp.next; //该节点前一个节点的next指向该节点后一个节点
            if (temp.next != null){ //只有当删除的节点不是最后一个节点时才需要执行下面，否则空指针异常
                temp.next.pre = temp.pre; //该节点后一个节点的pre指向该节点前一个节点
            }
        }else {
            System.out.println("没有找到要删除的节点，删除失败!");
        }
    }

    //改（根据id匹配要修改的节点）
    public void update(int id,String name){
        if (head.next == null){
            System.out.println("链表为空！");
            return;
        }
        DNode temp = head.next;
        boolean flag = false; //用来标记是否找到对应id的节点
        while (true){
            if (temp == null){
                break;
            }
            if (temp.id == id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = name;
        }else {
            System.out.println("没有找到要修改的节点，修改失败！");
        }
    }

    //查（根据id匹配）
    public DNode show(int id){
        if (head.next == null){
            System.out.println("链表为空！");
            return null;
        }
        DNode temp = head.next;
        boolean flag = false;
        while (true){
            if (temp == null){
                break;
            }
            if (temp.id == id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            return temp;
        }else {
            System.out.println("没有找到要查找的节点，查找失败！");
            return null;
        }
    }

}

测试类

/**
 * @Author: Yeman
 * @Date: 2021-10-15-20:20
 * @Description:
 */
public class DoubleLinkedListTest {
    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

        DNode node1 = new DNode(1, "阿兰");
        DNode node2 = new DNode(2, "洛国富");
        DNode node3 = new DNode(3, "艾克森");

        doubleLinkedList.add1(node1);
        doubleLinkedList.add1(node2);
        doubleLinkedList.add1(node3);

        doubleLinkedList.list();

//        doubleLinkedList.remove(3); //删
//        doubleLinkedList.update(3,"张玉宁"); //改
//        System.out.println(doubleLinkedList.show(3)); //查

        doubleLinkedList.list();
    }
}