Javaで両方向循環リストを実装の方法

Javaの循環連結リストを実現するには、ノードの値を保持するデータフィールドと、前のノードと次のノードを指す2つのポインタフィールド（prevとnext）を持つNodeクラスを作成する必要があります。次に、連結リストのの先頭ノードを指すポインタフィールド（head）を持つ双方向循環連結リストクラスを作成する必要があります。

単純な双方向循環リンクリストのネイティブな実装例を次に示します。

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メソッドは新しいノードをリストの最後尾に追加するために使われました。リストが空の場合は新しいノードをリストの先頭にセットし、自身のprevとnextフィールドを自身に向けます。それ以外の場合は新しいノードを最後に追加し、関連ノードのprevとnextフィールドを更新します。

リスト内の各ノードの値を表示するためには display メソッドを使用します。リストは循環型なので、少なくとも 1 回はリスト内を確実に反復するため do-while ループを使用する必要があります。

mainメソッドでは、双方向循環リストを生成し、その末尾に3つのノードを挿入しました。次に、displayメソッドを呼び出し、リスト内のすべてのノードの値を表示しました。