Javaでリンクリストを逆にする

投稿日: 2022-10-18 2022-10-18
タグ: Algorithms, Java Collections

1. 序章

このチュートリアルでは、Javaに2つのリンクリスト反転アルゴリズムを実装します。

2. リンクリストのデータ構造

リンクリストは、各要素のポインタが順序を決定する線形データ構造です。 リンクリストの各要素には、リストデータを格納するデータフィールドと、シーケンス内の次の要素を指すポインタフィールドが含まれます。また、headポインタを使用してリンクリストの開始要素をポイントします。

リンクリストを逆にした後、 head は元のリンクリストの最後の要素を指し、各要素のポインターは元のリンクリストの前の要素を指します。

Javaには、ListおよびDequeインターフェースの二重リンクリスト実装を提供するLinkedListクラスがあります。ただし、このチュートリアルでは、一般的な単一リンクリストのデータ構造を使用します。

まず、リンクリストの要素を表すListNodeクラスから始めましょう。

public class ListNode {

    private int data;
    private ListNode next;

    ListNode(int data) {
        this.data = data;
        this.next = null;
    }

   // standard getters and setters
}

ListNodeクラスには2つのフィールドがあります。

要素のデータを表す整数値
次の要素へのポインタ/参照

リンクリストには、複数のListNodeオブジェクトが含まれる場合があります。たとえば、ループを使用して上記のサンプルリンクリストを作成できます。

ListNode constructLinkedList() {
    ListNode head = null;
    ListNode tail = null;
    for (int i = 1; i <= 5; i++) {
        ListNode node = new ListNode(i);
        if (head == null) {
            head = node;
        } else {
            tail.setNext(node);
        }
        tail = node;
    }
    return head;
}

3. 反復アルゴリズムの実装

Javaに反復アルゴリズムを実装しましょう。

ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextElement = current.getNext();
        current.setNext(previous);
        previous = current;
        current = nextElement;
    }
    return previous;
}

この反復アルゴリズムでは、2つの ListNode 変数、previousおよびcurrentを使用して、リンクリスト内の2つの隣接する要素を表します。反復ごとに、これら2つの要素を逆にしてから、次の2つの要素にシフトします。

最終的に、現在のポインターは null、になり、前のポインターは古いリンクリストの最後の要素になります。したがって、前のは、逆リンクリストの新しいヘッドポインターでもあり、メソッドから返します。

この反復的な実装は、簡単な単体テストで検証できます。

@Test
public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {
    ListNode head = constructLinkedList();
    ListNode node = head;
    for (int i = 1; i <= 5; i++) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
 
    LinkedListReversal reversal = new LinkedListReversal();
    node = reversal.reverseList(head);
 
    for (int i = 5; i >= 1; i--) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
}

この単体テストでは、最初に5つのノードを持つサンプルのリンクリストを作成します。また、リンクリストの各ノードに正しいデータ値が含まれていることを確認します。次に、反復関数を呼び出してリンクリストを逆にします。最後に、逆リンクリストをチェックして、データが期待どおりに逆になっていることを確認します。

4. 再帰的アルゴリズムの実装

それでは、再帰アルゴリズムをJavaに実装しましょう。

ListNode reverseListRecursive(ListNode head) {
    if (head == null) {
        return null;
    }
    if (head.getNext() == null) {
        return head;
    }
    ListNode node = reverseListRecursive(head.getNext());
    head.getNext().setNext(head);
    head.setNext(null);
    return node;
}

reverseListRecursive 関数では、最後の要素に到達するまで、リンクリストの各要素に再帰的にアクセスします。この最後の要素は、逆リンクリストの新しいヘッドになります。また、部分的に反転されたリンクリストの最後にvisited要素を追加します。

同様に、この再帰的な実装を簡単な単体テストで検証できます。

@Test
public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {
    ListNode head = constructLinkedList();
    ListNode node = head;
    for (int i = 1; i <= 5; i++) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
 
    LinkedListReversal reversal = new LinkedListReversal();
    node = reversal.reverseListRecursive(head);
 
    for (int i = 5; i >= 1; i--) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
}

5. 結論

このチュートリアルでは、リンクリストを逆にするために2つのアルゴリズムを実装しました。いつものように、記事のソースコードはGitHubでから入手できます。

getdocs

13036