java代码如何实现双向链表并处理节点关系 java代码双向链表的基础编写教程​

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

    public Node(int data) {
        this.data = data;
        this.prev = null; // 初始时，前驱和后继都为空
        this.next = null;
    }
}

public class DoublyLinkedList {
    private Node head;
    private Node tail;
    private int size; // 维护链表大小，方便快速获取

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

    // 添加到链表头部
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) { // 链表为空
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head; // 新节点的next指向原head
            head.prev = newNode; // 原head的prev指向新节点
            head = newNode;      // 更新head为新节点
        }
        size++;
        // System.out.println("Added " + data + " to head. Current size: " + size);
    }

    // 添加到链表尾部
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (tail == null) { // 链表为空
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode; // 原tail的next指向新节点
            newNode.prev = tail; // 新节点的prev指向原tail
            tail = newNode;      // 更新tail为新节点
        }
        size++;
        // System.out.println("Added " + data + " to tail. Current size: " + size);
    }

    // 在指定索引处添加（这里只是一个简单的示例，实际可能需要更多边界检查）
    public void addAtIndex(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size) {
            addLast(data);
            return;
        }

        Node newNode = new Node(data);
        Node current = head;
        // 遍历到目标位置的前一个节点
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        // current现在是新节点的前一个节点
        newNode.next = current.next;
        newNode.prev = current;
        current.next.prev = newNode; // 原来current.next的prev指向新节点
        current.next = newNode;      // current的next指向新节点
        size++;
        // System.out.println("Added " + data + " at index " + index + ". Current size: " + size);
    }

    // 删除链表头部
    public int removeFirst() {
        if (head == null) {
            throw new IllegalStateException("List is empty.");
        }
        int data = head.data;
        if (head == tail) { // 只有一个节点
            head = null;
            tail = null;
        } else {
            head = head.next; // head指向下一个节点
            if (head != null) { // 新的head的prev应该为null
                head.prev = null;
            }
        }
        size--;
        // System.out.println("Removed " + data + " from head. Current size: " + size);
        return data;
    }

    // 删除链表尾部
    public int removeLast() {
        if (tail == null) {
            throw new IllegalStateException("List is empty.");
        }
        int data = tail.data;
        if (head == tail) { // 只有一个节点
            head = null;
            tail = null;
        } else {
            tail = tail.prev; // tail指向前一个节点
            if (tail != null) { // 新的tail的next应该为null
                tail.next = null;
            }
        }
        size--;
        // System.out.println("Removed " + data + " from tail. Current size: " + size);
        return data;
    }

    // 删除指定索引处的节点
    public int removeAtIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == 0) {
            return removeFirst();
        }
        if (index == size - 1) {
            return removeLast();
        }

        Node current = head;
        // 遍历到目标节点
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        // current现在是需要删除的节点
        int data = current.data;
        current.prev.next = current.next; // 前一个节点的next指向删除节点的next
        current.next.prev = current.prev; // 后一个节点的prev指向删除节点的prev
        size--;
        // System.out.println("Removed " + data + " at index " + index + ". Current size: " + size);
        return data;
    }

    // 从头到尾遍历
    public void displayForward() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        Node current = head;
        System.out.print("Forward: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // 从尾到头遍历
    public void displayBackward() {
        if (tail == null) {
            System.out.println("List is empty.");
            return;
        }
        Node current = tail;
        System.out.print("Backward: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

public class DoublyLinkedListDemo {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        System.out.println("Is list empty? " + list.isEmpty()); // true

        list.addLast(10);
        list.addFirst(5);
        list.addLast(20);
        list.addAtIndex(1, 15); // 链表: 5 -> 15 -> 10 -> 20

        list.displayForward();  // Output: Forward: 5 15 10 20
        list.displayBackward(); // Output: Backward: 20 10 15 5
        System.out.println("List size: " + list.getSize()); // 4

        list.removeFirst(); // 移除 5
        list.displayForward(); // Output: Forward: 15 10 20
        list.removeLast();  // 移除 20
        list.displayForward(); // Output: Forward: 15 10
        list.removeAtIndex(0); // 移除 15
        list.displayForward(); // Output: Forward: 10

        System.out.println("List size: " + list.getSize()); // 1
        list.removeFirst(); // 移除 10
        list.displayForward(); // Output: List is empty.
        System.out.println("Is list empty? " + list.isEmpty()); // true
    }
}

node.prev

node.next

head == null

tail == null

addLast

removeFirst

removeLast

IllegalStateException

tail.prev

if (node != null)

removeFirst()

head.prev = null

if (head != null)

addAtIndex

removeAtIndex

index < 0

index > size