详解双向链表结构及Java实现示例

双向链表（Double Linked List）是一种更复杂的数据结构，其中每个节点都包含两个链接：一个指向前一个节点，另一个指向后一个节点。这使得在链表中的任何位置插入或删除节点都变得相对容易。通常被表示为一系列通过箭头连接的节点，每个节点包含两个指向相邻节点的指针（一个指向前一个节点，另一个指向后一个节点）以及一个数据域。

以下是一个简单的双向链表的描述：

1. 节点结构：每个节点由三个部分组成：

• 数据域：用于存储节点的数据值。

• 前驱指针：指向链表中的前一个节点。对于链表的第一个节点（通常称为头节点），这个指针可能为空或指向链表的尾部节点（在循环双向链表中）。

• 后继指针：指向链表中的后一个节点。对于链表的最后一个节点，这个指针可能为空或指向链表的头节点（在循环双向链表中）。

2. 链表结构：多个节点通过前驱和后继指针连接在一起，形成一个连续的序列。在原型图中，可以使用箭头来表示这些指针，箭头从当前节点指向其前驱或后继节点。

3. 特殊节点：

• 头节点：双向链表通常有一个头节点，它作为链表的起始点。头节点的数据域可能不存储实际数据，而仅用于标识链表的开始。在循环双向链表中，头节点的后继指针指向链表的第一个实际数据节点，前驱指针指向链表的最后一个节点。

• 尾节点：双向链表的最后一个节点称为尾节点。在普通双向链表中，尾节点的后继指针为空；而在循环双向链表中，尾节点的后继指针指向头节点。

4. 操作：原型图还可以包含表示链表操作的元素，如添加节点（在头部、中间或尾部插入节点）、删除节点（删除指定节点或头/尾节点）、遍历链表等。这些操作可以通过在原型图中添加箭头和注释来表示。

下面是一个简单的Java双向链表的实现示例：

public class Node<T> {  
    T data;  
    Node<T> prev;  
    Node<T> next;  
  
    public Node(T data) {  
        this.data = data;  
        this.prev = null;  
        this.next = null;  
    }  
}  
  
public class DoublyLinkedList<T> {  
    Node<T> head;  
    Node<T> tail;  
  
    public DoublyLinkedList() {  
        head = null;  
        tail = null;  
    }  
  
    // 添加节点到链表尾部  
    public void add(T data) {  
        Node<T> newNode = new Node<>(data);  
        if (head == null) {  
            head = newNode;  
            tail = newNode;  
        } else {  
            tail.next = newNode;  
            newNode.prev = tail;  
            tail = newNode;  
        }  
    }  
  
    // 在指定位置插入节点  
    public void insert(T data, int position) {  
        if (position < 0) {  
            throw new IndexOutOfBoundsException("Position must be non-negative");  
        }  
        Node<T> newNode = new Node<>(data);  
        if (position == 0) {  
            if (head == null) {  
                head = newNode;  
                tail = newNode;  
            } else {  
                newNode.next = head;  
                head.prev = newNode;  
                head = newNode;  
            }  
        } else {  
            Node<T> current = head;  
            for (int i = 0; i < position - 1; i++) {  
                if (current == null) {  
                    throw new IndexOutOfBoundsException("Position out of bounds");  
                }  
                current = current.next;  
            }  
            if (current == null) {  
                tail.next = newNode;  
                newNode.prev = tail;  
                tail = newNode;  
            } else {  
                newNode.next = current.next;  
                if (current.next != null) {  
                    current.next.prev = newNode;  
                }  
                current.next = newNode;  
                newNode.prev = current;  
            }  
        }  
    }  
  
    // 删除指定节点  
    public void delete(Node<T> node) {  
        if (node == null) {  
            return;  
        }  
        if (node == head) {  
            head = head.next;  
            if (head != null) {  
                head.prev = null;  
            } else {  
                tail = null;  
            }  
        } else if (node == tail) {  
            tail = tail.prev;  
            tail.next = null;  
        } else {  
            node.prev.next = node.next;  
            if (node.next != null) {  
                node.next.prev = node.prev;  
            }  
        }  
    }  
  
    // ... 其他可能的方法，如搜索、遍历等  
}