基于Java实现双向链表

实现双向链表的步骤

1. 定义链表节点类

双向链表的节点类需要有三个属性：

• data: 保存节点所存放的数据。
• prev: 保存上一个节点的引用。
• next: 保存下一个节点的引用。

以下是这个节点类的简单实现：

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

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

2. 实现双向链表类

2.1 定义头节点

你需要实现一个DoubleLinkedList的类。这个类应该有一个头节点head，头节点的下一个节点指向链表的第一个节点。

public class DoubleLinkedList {
    private Node head;

    public DoubleLinkedList() {
        this.head = new Node(0);
        this.head.prev = null;
        this.head.next = null;
    }
}

2.2 遍历整个链表

你可以使用一个辅助节点来遍历双向链表。你可以从头节点开始，直到遇到链表的末尾节点。

public void display() {
    Node node = head.next;
    while (node != null) {
        System.out.print(node.data + " ");
        node = node.next;
    }
}

2.3 在链表末尾添加节点

双向链表的末尾的next应该指向新的节点，新的节点的prev应该指向双向链表的末尾节点。

public void add(int data) {
    Node node = new Node(data);
    Node lastNode = this.getLastNode();
    lastNode.next = node;
    node.prev = lastNode;
}

2.4 在指定位置插入节点

你需要一个辅助节点来遍历你需要插入的位置。新节点的prev应该指向遍历到的节点的prev，新节点的next应该指向遍历到的节点，遍历到的节点的prev应该指向新节点。

public void add(int index, int data) {
    Node node = new Node(data);
    Node curr = head.next;

    for (int i = 0; i < index - 1 && curr != null; i++) {
        curr = curr.next;
    }

    if (curr != null) {
        node.next = curr;
        node.prev = curr.prev;
        curr.prev.next = node;
        curr.prev = node;
    }
}

2.5 删除指定节点

这个操作的实现较为简单。你需要找到需要删除的节点，把前后节点的next或prev相连即可。

public void remove(int data) {
    Node curr = head.next;
    while (curr != null) {
        if (curr.data == data) {
            curr.prev.next = curr.next;
            if (curr.next != null) {
                curr.next.prev = curr.prev;
            }
            break;
        }
        curr = curr.next;
    }
}

3. 测试双向链表实现类

你可以定义一个main函数来测试你的代码。以下是一个简单的测试用例：

public static void main(String[] args) {
    DoubleLinkedList list = new DoubleLinkedList();

    // 在链表末尾添加节点
    list.add(1);
    list.add(2);
    list.add(3);

    // 在指定位置插入节点
    list.add(2, 5);

    // 删除节点
    list.remove(3);

    // 遍历链表并输出节点的值
    list.display();
}

这个测试用例的输出结果为：1 2 5。

4. 示例说明

示例1

下面是执行代码list.add(1); list.add(2); list.add(3); list.add(4); list.add(5);后，双向链表的结构示意图：

head ↀ─────→ 1 ←─────〉 2 ←─────〉 3 ←─────〉 4 ←─────〉 5 ←─────ↀ null
                  prev  next  prev  next  prev  next  prev  next  prev  next 

示例2

下面是执行代码list.add(2, 6);后，双向链表的结构示意图：

head ↀ─────→ 1 ←─────〉 2 ←─────〉 6 ←─────〉 3 ←─────〉 4 ←─────〉 5 ←─────ↀ null
                  prev  next  prev  next  prev  next  prev  next  prev  next 

在这个例子中，我们在双向链表的第二个位置插入了一个值为6的节点。你可以看到，新节点的prev指向了2，而next则指向了3。同时，原本在链表中第二个位置的节点2的next指向了新节点6，而在链表中第三个位置的节点3的prev指向了新节点6。