如何在java中实现双向链表

在Java中实现双向链表，首先需要创建一个表示链表节点的类，然后创建一个双向链表类来管理这些节点

创建表示链表节点的类（Node）：

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;
    }
}

创建双向链表类（DoublyLinkedList）：

public class DoublyLinkedList<T> {
    private Node<T> head; // 链表头节点
    private Node<T> tail; // 链表尾节点

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

    // 在链表头部添加节点
    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // 在链表尾部添加节点
    public void addLast(T data) {
        Node<T> newNode = new Node<>(data);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 删除链表头部的节点
    public void removeFirst() {
        if (head == null) {
            System.out.println("链表为空，无法删除元素");
            return;
        }
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.prev = null;
        }
    }

    // 删除链表尾部的节点
    public void removeLast() {
        if (tail == null) {
            System.out.println("链表为空，无法删除元素");
            return;
        }
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            tail = tail.prev;
            tail.next = null;
        }
    }

    // 遍历并打印链表中的所有元素
    public void printList() {
        Node<T> currentNode = head;
        while (currentNode != null) {
            System.out.print(currentNode.data + " ");
            currentNode = currentNode.next;
        }
        System.out.println();
    }
}

使用示例：

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList<Integer> list = new DoublyLinkedList<>();
        list.addFirst(1);
        list.addFirst(2);
        list.addLast(3);
        list.addFirst(4);
        list.printList(); // 输出: 4 2 1 3

        list.removeFirst();
        list.removeLast();
        list.printList(); // 输出: 2 1
    }
}

这个例子展示了如何实现一个简单的双向链表。你可以根据需要扩展这个实现，例如添加更多的方法来操作链表，如插入、删除指定位置的节点等。

最新问答

相关标签