Java双向链表的增删改查怎么实现

双向链表（Doubly Linked List）是一种常见的数据结构，它由多个节点组成，每个节点包含数据域和两个指针域，分别指向前一个节点和后一个节点。与单向链表相比，双向链表可以双向遍历，因此在某些场景下具有更高的灵活性。本文将介绍如何在Java中实现双向链表的增删改查操作。

1. 双向链表的节点定义

首先，我们需要定义一个节点类，用于表示双向链表中的每个节点。节点类包含三个属性：data（数据域）、prev（指向前一个节点的指针）和next（指向后一个节点的指针）。

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

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

2. 双向链表的定义

接下来，我们定义一个双向链表类，包含头节点head和尾节点tail。初始时，head和tail都为空。

class DoublyLinkedList {
    private Node head;
    private Node tail;

    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }
}

3. 增加节点

3.1 在链表头部插入节点

在链表头部插入节点时，新节点的next指针指向当前的头节点，头节点的prev指针指向新节点，然后将头节点更新为新节点。

public void insertAtHead(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        tail = newNode;
    } else {
        newNode.next = head;
        head.prev = newNode;
        head = newNode;
    }
}

3.2 在链表尾部插入节点

在链表尾部插入节点时，新节点的prev指针指向当前的尾节点，尾节点的next指针指向新节点，然后将尾节点更新为新节点。

public void insertAtTail(int data) {
    Node newNode = new Node(data);
    if (tail == null) {
        head = newNode;
        tail = newNode;
    } else {
        newNode.prev = tail;
        tail.next = newNode;
        tail = newNode;
    }
}

3.3 在指定位置插入节点

在指定位置插入节点时，需要先找到该位置的前一个节点，然后调整新节点和前一个节点的指针。

public void insertAtPosition(int data, int position) {
    if (position < 0) {
        throw new IllegalArgumentException("Position cannot be negative");
    }
    if (position == 0) {
        insertAtHead(data);
        return;
    }
    Node newNode = new Node(data);
    Node 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) {
        throw new IndexOutOfBoundsException("Position out of bounds");
    }
    newNode.next = current.next;
    if (current.next != null) {
        current.next.prev = newNode;
    }
    current.next = newNode;
    newNode.prev = current;
    if (newNode.next == null) {
        tail = newNode;
    }
}

4. 删除节点

4.1 删除头节点

删除头节点时，将头节点更新为下一个节点，并将新头节点的prev指针置为null。

public void deleteAtHead() {
    if (head == null) {
        throw new IllegalStateException("List is empty");
    }
    head = head.next;
    if (head != null) {
        head.prev = null;
    } else {
        tail = null;
    }
}

4.2 删除尾节点

删除尾节点时，将尾节点更新为前一个节点，并将新尾节点的next指针置为null。

public void deleteAtTail() {
    if (tail == null) {
        throw new IllegalStateException("List is empty");
    }
    tail = tail.prev;
    if (tail != null) {
        tail.next = null;
    } else {
        head = null;
    }
}

4.3 删除指定位置的节点

删除指定位置的节点时，需要先找到该节点，然后调整前后节点的指针。

public void deleteAtPosition(int position) {
    if (position < 0) {
        throw new IllegalArgumentException("Position cannot be negative");
    }
    if (head == null) {
        throw new IllegalStateException("List is empty");
    }
    if (position == 0) {
        deleteAtHead();
        return;
    }
    Node current = head;
    for (int i = 0; i < position; i++) {
        if (current == null) {
            throw new IndexOutOfBoundsException("Position out of bounds");
        }
        current = current.next;
    }
    if (current == null) {
        throw new IndexOutOfBoundsException("Position out of bounds");
    }
    if (current.prev != null) {
        current.prev.next = current.next;
    }
    if (current.next != null) {
        current.next.prev = current.prev;
    }
    if (current == tail) {
        tail = current.prev;
    }
}

5. 修改节点

修改节点时，需要先找到该节点，然后更新其数据域。

public void updateAtPosition(int data, int position) {
    if (position < 0) {
        throw new IllegalArgumentException("Position cannot be negative");
    }
    Node current = head;
    for (int i = 0; i < position; i++) {
        if (current == null) {
            throw new IndexOutOfBoundsException("Position out of bounds");
        }
        current = current.next;
    }
    if (current == null) {
        throw new IndexOutOfBoundsException("Position out of bounds");
    }
    current.data = data;
}

6. 查找节点

查找节点时，遍历链表，找到与目标数据匹配的节点。

public Node search(int data) {
    Node current = head;
    while (current != null) {
        if (current.data == data) {
            return current;
        }
        current = current.next;
    }
    return null;
}

7. 遍历链表

遍历链表时，可以从头节点开始，依次访问每个节点的数据。

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

8. 总结

本文介绍了如何在Java中实现双向链表的增删改查操作。通过定义节点类和双向链表类，我们可以轻松地实现这些操作。双向链表的灵活性使其在某些场景下比单向链表更具优势，但同时也增加了内存开销。在实际应用中，应根据具体需求选择合适的数据结构。

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.insertAtHead(1);
        list.insertAtTail(3);
        list.insertAtPosition(2, 1);
        list.traverse(); // 输出: 1 2 3

        list.updateAtPosition(4, 1);
        list.traverse(); // 输出: 1 4 3

        list.deleteAtPosition(1);
        list.traverse(); // 输出: 1 3

        Node node = list.search(3);
        if (node != null) {
            System.out.println("Found node with data: " + node.data);
        } else {
            System.out.println("Node not found");
        }
    }
}

通过以上代码示例，我们可以看到双向链表的基本操作是如何实现的。希望本文对你理解和使用双向链表有所帮助。