基本概念

节点结构：双向链表每个节点都包含三个部分：数据域、指向前一个节点的指针（prev）和指向后一个节点的指针域（next）。头节点：双向链表通常会有一个头节点（next指针指向第一个有效节点）。

示意图

代码实战

定义一个节点类

/** * 节点类 * @param <T> */class Node<T> {    /** 节点编号 */    public int no;    /** 节点数据 */    public T t;    /** 前一个节点 */    public Node<T> prev;    /** 后一个节点 */    public Node<T> next;    public Node(int no, T t) {        this.no = no;        this.t = t;    }​    @Override    public String toString() {        return "Node{" +                "no=" + no +                ", t=" + t +                '}';    }}

定义双向链表类

/** * 双向链表 * @param <T> */class DoubleLinkedList<T> {    /**     * 初始化 头节点     */    private Node<T> head = new Node<>(0, null);        /**     * 新增节点     *     * @param node     */    public void add(Node<T> node) {        Node<T> temp = head;        // 遍历 查找尾节点        while (temp.next != null) {            temp = temp.next;        }        // 当前尾节点的下一节点（next）指向新增节点        temp.next = node;        // 新增节点的上一节点（prev）指向当前尾节点        node.prev = temp;    }         /**     * 根据节点no，按顺序添加节点     *     * @param node     */    public void addOrderByAsc(Node<T> node) {        Node<T> temp = head;        // 遍历 查找大于 新增节点（node）节点编号的上一节点        while (true) {            // 查至尾节点，未查询到，则添加到尾节点            if (temp.next == null) {                temp.next = node;                node.prev = temp;                break;            }            // 查询到，则插入到当前节点之后            if (temp.next.no > node.no) {                // 新增节点的下一节点（next）指向 当前节点的下一节点                node.next = temp.next;                // 新增节点的上一节点（prev）指向 当前节点                node.prev = temp;                // 当前节点的下一节点（next）的上一节点（prev）指向 新增节点                temp.next.prev = node;                // 当前节点的下一节点（next）指向 新增节点                temp.next = node;                break;            }            if (temp.next.no == node.no) {                System.out.printf("节点%d已存在，无法添加节点：%s\n", node.no, node);                break;            }            temp = temp.next;        }    }         /**     * 修改节点     *     * @param node     */    public void update(Node<T> node) {        if (head.next == null) {            System.out.println("链表为空");            return;        }        Node<T> temp = head.next;        // 遍历 节点        while (temp != null) {            // 找到待修改的节点            if (temp.no == node.no) {                temp.t = node.t;                break;            }            temp = temp.next;        }    }        /**     * 根据编号删除节点     * @param no     */    public void del(int no) {        if (head.next == null) {            System.out.println("链表为空");        }        Node<T> temp = head.next;        // 遍历 节点        while (temp != null) {            // 找到待删除的节点            if (temp.no == no) {                // 不是尾节点                if (temp.next != null) {                    temp.next.prev = temp.prev;                }                temp.prev.next = temp.next;                break;            }            temp = temp.next;        }    }        /**     * 遍历双向链表     */    public void showAll() {        if (head.next == null) {            System.out.println("链表为空");            return;        }        Node<T> temp = head.next;        while (temp != null) {            System.out.println(temp);            temp = temp.next;        }    }        /**     * 获取链表有效数据个数     * @return     */    public int getLength() {        int length = 0;        Node<T> temp = head;        while(temp.next != null) {            length++;            temp = temp.next;        }        return length;    }        /**     * 栈遍历 倒叙打印链表数据     */    public void resverseStackPrint() {        Stack<Node<T>> stack = new Stack<>();        if (head.next == null) {            System.out.println("链表为空");            return;        }        Node<T> temp = head.next;        while (temp != null) {            stack.add(temp);            temp = temp.next;        }​        while (!stack.isEmpty()) {            Node<T> pop = stack.pop();            System.out.println(pop);        }    }        /**     * 翻转链表     */    public void reversal() {        if (head.next == null || head.next.next == null) {            return;        }        // 当前节点        Node<T> current = head.next;        // 下一个节点        Node<T> next = null;        // 临时头节点        Node<T> headNode = new Node<>(0, null);        // 遍历        while (true) {            // 不存在下一节点时，结束循环            if (current == null) {                break;            }            // 获取下一个节点            next = current.next;            // 当前的节点next指针 指向 头节点的下一节点            current.next = headNode.next;            // 非首节点时，更新 原先的上一节点指针            if (headNode.next != null) {                headNode.next.prev = current;            }            // 头节点的next指针指向当前节点            headNode.next = current;            // 当前节点的prev指针指向头节点            current.prev = headNode;            // 更新当前节点            current = next;        }        head.next = headNode.next;    }}

总结

双向链表是一种强大的数据结构，它不仅提供了单向链表的所有优点，还增加了访问前驱节点的能力，这在许多实际应用中是非常有用的。希望本文能帮助您更好地理解和掌握双向链表的原理与实现。