跳到主要内容

编写Java代码实现双向链表 ?

参考答案:

下面是一个简单的Java实现双向链表的例子。这个实现定义了一个双向链表节点类Node和一个双向链表类DoublyLinkedList

public class DoublyLinkedList {
    Node head;  // 链表头节点

    // 链表节点类
    static class Node {
        int data;
        Node next;
        Node prev;

        Node(int d) {
            data = d;
            next = null;
            prev = null;
        }
    }

    // 在链表末尾添加新节点
    public void append(int new_data) {
        Node new_node = new Node(new_data);
        Node last = head;

        // 如果链表为空,新节点就是头节点
        if (head == null) {
            head = new_node;
            return;
        }

        // 否则,找到最后一个节点
        while (last.next != null) {
            last = last.next;
        }

        // 添加新节点到链表末尾
        last.next = new_node;
        new_node.prev = last;
    }

    // 打印链表
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    // 在链表头部添加新节点
    public void prepend(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = head;

        // 如果链表不为空,更新头节点的prev指针
        if (head != null) {
            head.prev = new_node;
        }

        head = new_node;
    }

    // 在给定位置插入新节点
    public void insertAfter(Node prev_node, int new_data) {
        if (prev_node == null) {
            System.out.println("给定的前一个节点不能为null");
            return;
        }

        Node new_node = new Node(new_data);
        new_node.next = prev_node.next;
        new_node.prev = prev_node;

        // 如果prev_node是最后一个节点,新节点就是新的最后一个节点
        if (prev_node.next != null) {
            prev_node.next.prev = new_node;
        }

        prev_node.next = new_node;
    }

    // 删除节点
    public void deleteNode(Node del) {
        if (del == null) {
            System.out.println("要删除的节点不能为null");
            return;
        }

        // 如果要删除的节点是头节点
        if (del == head) {
            head = del.next;

            // 如果链表不为空,更新新头节点的prev指针
            if (head != null) {
                head.prev = null;
            }
            return;
        }

        // 如果要删除的节点不是最后一个节点
        if (del.next != null) {
            del.next.prev = del.prev;
        }

        // 如果要删除的节点不是头节点
        if (del.prev != null) {
            del.prev.next = del.next;
        }
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();

        dll.append(5);
        dll.append(10);
        dll.append(15);

        dll.printList();  // 输出: 5 10 15

        dll.prepend(20);
        dll.printList();  // 输出: 20 5 10 15

        dll.insertAfter(dll.head, 25);
        dll.printList();  // 输出: 20 25 5 10 15

        dll.deleteNode(dll.head.next);
        dll.printList();  // 输出: 20 5 10 15
    }
}

这个双向链表实现提供了append(在链表末尾添加新节点)、prepend(在链表头部添加新节点)、insertAfter(在给定节点后插入新节点)和deleteNode(删除给定节点)等方法。printList