java雙向循環(huán)鏈表怎么實(shí)現(xiàn)

小億
92
2023-12-01 22:46:54

要實(shí)現(xiàn)java雙向循環(huán)鏈表，你需要?jiǎng)?chuàng)建一個(gè)Node類(lèi)來(lái)表示鏈表中的節(jié)點(diǎn)。Node類(lèi)應(yīng)該有一個(gè)數(shù)據(jù)字段來(lái)存儲(chǔ)節(jié)點(diǎn)的值，以及兩個(gè)指針字段prev和next來(lái)分別指向上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)。然后，你需要?jiǎng)?chuàng)建一個(gè)雙向循環(huán)鏈表類(lèi)，該類(lèi)應(yīng)該有一個(gè)指向鏈表頭節(jié)點(diǎn)的指針字段head。

以下是一個(gè)簡(jiǎn)單的雙向循環(huán)鏈表的實(shí)現(xiàn)示例：

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

public class DoublyLinkedList {
    public Node head;

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

    public void display() {
        if (head == null) {
            System.out.println("Doubly linked list is empty.");
            return;
        }
        
        Node currentNode = head;
        
        do {
            System.out.print(currentNode.data + " ");
            currentNode = currentNode.next;
        } while (currentNode != head);
        
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        
        list.insertAtEnd(1);
        list.insertAtEnd(2);
        list.insertAtEnd(3);
        
        list.display(); // Output: 1 2 3
    }
}

在上面的示例中，insertAtEnd方法用于在鏈表末尾插入一個(gè)新節(jié)點(diǎn)。如果鏈表為空，則將新節(jié)點(diǎn)設(shè)置為鏈表的頭節(jié)點(diǎn)，并將其prev和next字段都指向自身。否則，將新節(jié)點(diǎn)插入到鏈表末尾，并更新相關(guān)節(jié)點(diǎn)的prev和next字段。

display方法用于遍歷鏈表并打印每個(gè)節(jié)點(diǎn)的值。由于鏈表是循環(huán)的，所以我們需要使用do-while循環(huán)來(lái)確保至少遍歷一次鏈表。

在main方法中，我們創(chuàng)建了一個(gè)雙向循環(huán)鏈表，并在末尾插入了三個(gè)節(jié)點(diǎn)。然后，我們調(diào)用display方法來(lái)顯示鏈表中的所有節(jié)點(diǎn)的值。

0 踩