Java数据结构之双向链表图解

以下是Java数据结构之双向链表图解的完整攻略：

一、双向链表简介

1.1 定义

双向链表（Doubly Linked List），也叫双向链式线性表，是链式存储结构的基本形式之一。双向链表的每个节点都含有两个指针，分别指向前驱节点和后继节点，因此可以支持双向遍历。

1.2 结构

双向链表的结构可以用下图表示：

  +-------+    +-------+    +-------+
  |节点 1 |<-->|节点 2 |<-->|节点 3 |
  +-------+    +-------+    +-------+
  |  data |    |  data |    |  data |
  |  prev |<---|  prev |<---|  prev |
  |  next |--->|  next |--->|  next |
  +-------+    +-------+    +-------+

其中，每个节点都有data、prev、next三个属性，分别表示数据、前驱节点、后继节点。

二、双向链表的Java实现

下面我们来实现一个双向链表，并包含如下操作：

• 新增节点
• 删除节点
• 查找节点
• 遍历节点

public class DoublyLinkedList {

    private Node head; // 头节点

    private class Node {
        private int data;
        private Node prev;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 新增节点
     *
     * @param data 数据
     */
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.prev = temp;
        }
    }

    /**
     * 删除节点
     *
     * @param data 数据
     */
    public void remove(int data) {
        Node temp = head;
        while (temp != null) {
            if (temp.data == data) {
                if (temp.prev != null) {
                    temp.prev.next = temp.next;
                } else {
                    head = temp.next;
                }
                if (temp.next != null) {
                    temp.next.prev = temp.prev;
                }
                break;
            }
            temp = temp.next;
        }
    }

    /**
     * 查找节点
     *
     * @param data 数据
     * @return 节点
     */
    public Node find(int data) {
        Node temp = head;
        while (temp != null) {
            if (temp.data == data) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

    /**
     * 遍历节点，从前向后遍历
     */
    public void traverseForward() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    /**
     * 遍历节点，从后向前遍历
     */
    public void traverseBackward() {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.prev;
        }
        System.out.println();
    }
}

三、双向链表的示例操作

3.1 新增节点

public static void main(String[] args) {
    DoublyLinkedList list = new DoublyLinkedList();
    list.add(1);
    list.add(2);
    list.add(3);
    list.traverseForward(); // 1 2 3
}

3.2 删除节点

public static void main(String[] args) {
    DoublyLinkedList list = new DoublyLinkedList();
    list.add(1);
    list.add(2);
    list.add(3);
    list.traverseForward(); // 1 2 3
    list.remove(1);
    list.traverseForward(); // 2 3
}

以上就是Java数据结构之双向链表图解的完整攻略，希望对您有所帮助。