Javaでリストを実装する

基本情報記述者試験に向けて、Javaで基本的なアルゴリズムを再勉強しています。この記事ではリストを実装していきながらデータ構造とアルゴリズムについてまとめます。

連結リスト

Javaのリストといえば、ArrayListが有名ですが、今回はリストとしてのシンプルな機能を持つLinkedListクラスを参考にして実装してみます。

連結リストは、ノード(オブジェクト)を連結させることでリストとしての機能を提供します。

ノードは以下の2つのフィールドを持ちます。

  • データフィールド:データそのものを持ちます。
  • リンクフィールド:次のノードへの参照を持ちます。

また、リストの先頭にノードを追加するためには、ノードの先頭を管理するためのフィールドが必要です。

実際にコードを書くと以下のようになります。

class SNode {
    Object data;
    SNode next;
}

public class SLinkedList {
    private SNode first;
    
    public void addFirst(Object data) {
        SNode node = new SNode();
        node.data = data;
        node.next = first;
        first = node;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        // リストの先頭から順番に処理
        SNode current = first;
        // 要素がある間中繰り返し
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(", ");
            }
            // 次の要素に移動
            current = current.next;
        }
        sb.append(']');
        return sb.toString();
    }
}

SNodeクラスがノードです。SLinkedListクラスがリストを操作するクラスです。

このリストを使用するために以下のようなコードを実行してみます。

public class Sample_01 {
    public static void main(String[] args) {
        SLinkedList list = new SLinkedList();

        list.addFirst("abc");
        System.out.println(list);
        list.addFirst("def");
        System.out.println(list);
        list.addFirst("ghi");
        System.out.println(list);
    }
}

実行結果は以下です。

[abc]
[def, abc]
[ghi, def, abc]

リストに対してaddFirst()を実行することで、ノードを作成した後にそのノードをリストの先頭に追加します。addFirst()では、常に先頭要素を保持しているfirst変数のノードと、直前で作成したノードを入れ替えます。新たにfirst変数に格納されたノードは入替対象になったノードへの参照を保存します。

この他にも、目的のノードを探すためのcontains()やノードを削除するためのremove()をどのように実装するのかについて、次の項で扱います。

リスト要素の探索

リストから目的の要素を探すためにcontains()を実装します。

先ほどのSLinkedListクラスに以下のコードを追加します。

public boolean contains(Object data) {
    SNode current = first;
    while (current != null) {
        if (current.data.equals(data)) {
            return true;
        }
        current = current.next;
    }
    return false;
}

目的のデータを持つノードが見つかるまで、SNodeのnextフィールドを参照しながら、whileでノード間を移動します。目的のデータを持つノードが見つかったらtrue、見つからなかったらfalseを返します。

リスト要素の削除

リストから目的の要素を削除するためにremove()を実装します。

先ほどのSLinkedListクラスに以下のコードを追加します。

public void remove(Object data) {
    // リストが空の場合
    if (first == null) {
        return;
    }

    // 先頭が削除対象の場合の処理
    if (first.data.equals(data)) {
        first = first.next;
        return;
    }

    // 先頭以外が削除対象の場合
    SNode prev = first;
    SNode current = first.next;
    while (current != null) {
        if (current.data.equals(data)) {
            prev.next = current.next;
            return;
        }
        prev = current;
        current = current.next;
    }
}

「リストが空の場合」は何もしません。

「先頭が削除対象の場合」はfirst変数が参照する先頭ノードを次のノード(first.next)に付け替えます。このように処理を行うことでリストから要素を削除することができます。付け替え後に参照されなくなったノードは、時間の経過とともにJVMのガベージコレクションによって削除されます。

「先頭以外が削除対象の場合」は少し処理が複雑になります。カレントノードを削除する場合、カレントノードがリストから外されるので、カレントノードが抜けた分の連結を前のノードで行わなければなりません。つまり、前のノードの「次のノードへの参照」を付け替えなければならないのです。

23302

ダミーノードの導入

リストから要素を削除する処理では、「先頭要素」と「リストが空の場合」を特別扱いで処理する必要がありました。firstの初期値として、nullではなく、ダミーノードと呼ばれるデータを持たない、リンク情報だけのノードを用意することにより、このような特別扱いの処理をなくすことができます。このように「パターンを作り出し、ルールをシンプルにする」というのは数学でよく用いられるテクニックです。

これまでに書いてきたコードにダミーノードを導入したコードが以下になります。

public class SLinkedList {
    private SNode first;

    public SLinkedList() {
        // ダミーノードを作成
        first = new SNode();
    }

    public void addFirst(Object data) {
        SNode node = new SNode();
        node.data = data;
        // 先頭要素はダミーノードの次
        node.next = first.next;
        first.next = node;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        // 先頭要素はダミーノードの次
        SNode current = first.next;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(", ");
            }
            current = current.next;
        }
        sb.append(']');
        return sb.toString();
    }

    public boolean contains(Object data) {
        // 先頭要素はダミーノードの次
        SNode current = first.next;
        while (current != null) {
            if (current.data.equals(data)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public void remove(Object data) {
        // ダミーノードを導入することにより、
        // 先頭要素を特別扱いする必要がなくなる(初めの2つのif文は削除)
        SNode prev = first;
        SNode current = first.next;
        while (current != null) {
            if (current.data.equals(data)) {
                prev.next = current.next;
                return;
            }
            prev = current;
            current = current.next;
        }
    }
}

removeメソッドでは前項で説明した先頭2つのif文がなくなっています。以下が該当する2つのif文です。何故これを削除してもいいのかを確認してみます。

public void remove(Object data) {
    // リストが空の場合
    if (first == null) {
        return;
    }

    // 先頭が削除対象の場合の処理
    if (first.data.equals(data)) {
        first = first.next;
        return;
    }
    ...
}

ダミーノード導入後のソースコードでは、コンストラクタを追加し、その中でfirst変数にダミーノードを設定しています。つまり、SLinkedListインスタンスを作成した時点で以下のようになります。

23401

addFirstメソッドを呼び出して要素を追加したとき、prevとcurrentは次のようになります。これはコンストラクタによってダミーノードがprevに設定され、addFirstに渡されたノード(オブジェクト)がcurrentに設定されるためです。

23403

currentとして先頭要素、prevとしてダミーノードで初期化されるため、先頭要素を特別扱いする必要がなくなります(この後に続くwhile文では2つ目以降のノードを処理対象にしているので、ダミーノードの導入前までは1つ目のノードだけを特別扱いして処理していました)。

また、リストが空の場合、currentとしてnullが設定されます。そのため、空であることを特別扱いしなくてもwhile文の中身が実行されることなくメソッドが終了します。

双方向リスト

双方向リストは、連結リストとほとんど同じです。連結リストは次のノードへの参照のみを持っていましたが、双方向連結リストでは、次のノードと前のノードへの参照を持ちます。

ノードは以下の3つのフィールドを持ちます。

  • データフィールド:データそのものを持ちます。
  • Nextリンクフィールド:次のオブジェクトへの参照を持ちます。
  • Prevリンクフィールド:前のオブジェクトへの参照を持ちます。

また、今回はリストの先頭と末尾にノードを追加するために、ノードの先頭・ノードの末尾を管理する2つのフィールドが必要です。

実際にコードを書くと以下のようになります。

class DNode {
    Object data;
    DNode next;
    DNode prev;
}

public class DLinkedList {
    private DNode first;
    private DNode last;
    
    public DLinkedList() {
        // ダミーノードを作成
        first = new DNode();
        last = new DNode();
        first.next = last;
        last.prev = first;
    }
}

DNodeクラスがノードです。DLinkedListクラスがリストを操作するクラスです。
次に前方・後方の両方向にリストが辿れることを確認するために、DLinkedListクラスにtoString()toStringReverse()を実装します。

後方向にリストをたどれることを確認するためにtoStringメソッドを実装します。toStringメソッドは、今まで扱ってきたものとあまり変わりがありません。whileの終了条件として、nullの代わりにlastを使用するようにします(lastはダミーノードなので表示する必要はありません)。

public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    // 先頭要素はダミーノードの次
    DNode current = first.next;
    // 末尾のダミーノードに達するまで繰り返し
    while (current != last) {
        sb.append(current.data);
        if (current.next != last) {
            sb.append(", ");
        }
        // 次の要素に移動
        current = current.next;
    }
    sb.append(']');
    return sb.toString();
}

前方向にリストをたどれることを確認するためにtoStringReverseメソッドを実装します。

public String toStringReverse() {
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    // 末尾要素はダミーノードの前
    DNode current = last.prev;
    // 先頭のダミーノードに達するまで繰り返し
    while (current != first) {
        sb.append(current.data);
        if (current.prev != first) {
            sb.append(", ");
        }
        // 前の要素に移動
        current = current.prev;
    }
    sb.append(']');
    return sb.toString();
}

toStringメソッドとtoStringReverseメソッドの違いは、初期値、終了条件、リストをたどる方向になります。

続いて、リストの先頭に要素を追加するためにaddFirst()を実装してみます。

public void addFirst(Object data) {
    DNode node = new DNode();
    node.data = data;
    node.next = first.next;
    node.prev = first;
    first.next.prev = node;
    first.next = node;
}

first.next.prev = node;が難解ですが、これは「先頭ノードの次のノードのprevフィールドに新しく追加するノードを格納している」ということです。
直感的に理解するのが難しいと思うので、以下の図を参考にしてください。

24203

ノードの追加方法が分かれば、逆の処理を行うことでノードを削除することもできます。興味があれば、実装してみましょう。ノードを削除する方法の説明は割愛します。

このリストを使用するために以下のようなコードを実行してみます。

public class Sample02 {
    public static void main(String[] args) {
        DLinkedList list = new DLinkedList();

        System.out.println("リストへの要素の追加");
        list.addFirst("abc");
        System.out.println(list);
        list.addFirst("def");
        System.out.println(list);
        list.addFirst("ghi");
        System.out.println(list);
        System.out.println();

        System.out.println("リストの逆順表示");
        System.out.println(list.toStringReverse());
        System.out.println();
    }
} 

実行結果は以下です。

リストへの要素の追加
[abc]
[def, abc]
[ghi, def, abc]

リストの逆順表示
[abc, def, ghi]

環状リスト

環状リストとは、リストの先頭と末尾が接続されたリストです。循環リストとも呼ばれます。
ちなみに、末尾の次がnullになっているリストを線形リストと言います。

24301

環状リストを利用することにより、リスト中の任意のノードを起点としてリスト全体を辿ることができます。例えば、上記のリストで言うと「def」を起点として「abc」、「ghi」とたどることができるようになります。

なお、上記の例は片方向の環状リストです。双方向の環状リストを作成することも可能です。その場合、リストの先頭の「前」はリストの末尾を指します。

以下のコードが環状リストです。

package jp.winschool.algorithm.chapter2;

class CNode {
    Object data;
    CNode next;
    
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        CNode current = this;
        // 自分を起点に、一周するまでノードを表示(ダミーノード除く)
        do {
            if (current.data != null) {
                sb.append(current.data);
            }
            if (current.next.data != null && current.next != this) {
                sb.append(", ");
            }
            current = current.next;
        } while (current != this);
        sb.append(']');
        return sb.toString();
    }
}

public class CLinkedList {
    private CNode first;
    
    public CLinkedList() {
        // ダミーノードを作成
        first = new CNode();
        // 初期状態では次の要素として自分自身を参照する
        first.next = first;
    }

    public CNode addFirst(Object data) {
        CNode node = new CNode();
        node.data = data;
        // 先頭要素はダミーノードの次
        node.next = first.next;
        first.next = node;
        return node;
    }
}

addFirstメソッドでは追加したCNodeインスタンスを返すようにしています。これは任意のノードを起点にリストをたどれるようにするためです。

addFirstメソッドを呼び出すことでリストがどのように変化していくか確認しましょう。

まず、初期状態です。コンストラクタにfirst.next = firstと記述されています。firstの「次」としてfirstを参照しているので以下のようになります。

24302

「abc」を追加すると以下のように、追加したノードの「次」はダミーノードになります。

24303

さらに「def」を追加すると以下のようになります。このように追加が行われても正しく環状リストが形成できています。

24304

このリストを使用するために以下のようなコードを実行してみます。

public class Sample03 {
    public static void main(String[] args) {
        CLinkedList list = new CLinkedList();
        CNode node1 = list.addFirst("abc");
        CNode node2 = list.addFirst("def");
        CNode node3 = list.addFirst("ghi");
        System.out.println(node1);
        System.out.println(node2);
        System.out.println(node3);
    }
}

実行結果は以下です。

[abc, ghi, def]
[def, abc, ghi]
[ghi, def, abc]

このコードは少し不可解に見えるかもしれません。ノードの中でtoString()を実装している理由は、任意のノードを起点としてリスト全体を辿ることができるようにするためです。

参考資料
スクールの教科書
書籍 プログラマの数学