Java数据结构之双向链表的实现

一、双向链表的定义

双向链表是一种包含两个指针的链表数据结构，每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。

二、双向链表的实现

1. 定义节点

首先，我们需要定义一个节点类，包含节点的值，指向前一个节点的指针pre和指向后一个节点的指针next，代码如下：

public class Node {
    int value;
    Node pre;
    Node next;
    public Node(int value) {
        this.value = value;
        this.pre = null;
        this.next = null;
    }
}

2. 定义双向链表类

接着，我们需要定义一个双向链表类，包含指向链表头部的指针head和指向链表尾部的指针tail，代码如下：

public class DoubleLinkedList {
    Node head;
    Node tail;
    public DoubleLinkedList() {
        this.head = null;
        this.tail = null;
    }
}

3. 双向链表的添加操作

双向链表的添加操作和单向链表类似，但需要注意的是在添加节点时，要同时更新前一个节点和后一个节点的指针pre和next，代码如下：

public void add(int value) {
    Node node = new Node(value);
    if (head == null) {
        head = node;
        tail = node;
        return;
    }
    tail.next = node;
    node.pre = tail;
    tail = node;
}

4. 双向链表的删除操作

双向链表的删除操作同样需要同时更新前一个节点和后一个节点的指针pre和next，代码如下：

public void remove(int value) {
    Node current = head;
    while (current != null) {
        if (current.value == value) {
            if (current == head) {
                head = current.next;
                head.pre = null;
            } else if (current == tail) {
                tail = current.pre;
                tail.next = null;
            } else {
                current.pre.next = current.next;
                current.next.pre = current.pre;
            }
            return;
        }
        current = current.next;
    }
}

5. 双向链表的遍历操作

双向链表的遍历操作可以从头部开始遍历，也可以从尾部开始遍历，代码如下：

从头部开始遍历：

public void traverseFromHead() {
    Node current = head;
    while (current != null) {
        System.out.print(current.value + " ");
        current = current.next;
    }
}

从尾部开始遍历：

public void traverseFromTail() {
    Node current = tail;
    while (current != null) {
        System.out.print(current.value + " ");
        current = current.pre;
    }
}

三、示例说明

1. 示例一

DoubleLinkedList list = new DoubleLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.remove(2);
list.traverseFromHead();

输出结果：

1 3 4

2. 示例二

DoubleLinkedList list = new DoubleLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.traverseFromTail();

输出结果：

4 3 2 1

四、总结

双向链表相对于单向链表，除了可以遍历指向下一个节点的指针next外，还可以遍历指向前一个节点的指针pre。因此，在一些特定的场景下，双向链表可以更加方便地进行操作。