単方向リストの理解とJavaでの実装

線形単方向リスト(Singly-linked linear list)は、最も基本的なデータ構造のひとつです。また色々なデータ構造に対する考え方の基礎を学ぶことができるので良い題材です。 Java の java.util.LinkedList はその実装を見てみれば分かる通り双方向(Doubly)連結リストなので、これを参考にしながら単方向リストについてざっくりと実装をして、理解を深めました。

データ構造入門：基礎用語と概念の確認

単方向リストについて考える前に、データ構造とアルゴリズム全般の基礎知識を確認しておきましょう。

連結リストの要件

連結リストとは、連続した要素がポインタでつながれていて、最後の要素が null であるもの。 実行中にサイズを増減でき、メモリを無駄遣いしないという特徴がある（配列は要素がない状態のときでもメモリを消費している）。

抽象データ型としての連結リスト

配列との比較

単方向リストのノード

単方向リストのイメージ図
[データ|ポインタ] => [データ|ポインタ] => [データ|null]

単方向リストのノード構造は非常にシンプルです。 値と次のノードへのポインタという２つの要素しかありません。 コードで書くと次のような具合。

public class SinglyLinkedList{
    private static class Node<E> {
        E item;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

    private int size = 0;
    private Node<E> first = null;   // リストの先頭要素を指すポインタ
}

サイズを保持しておくと、ノードの追加・削除時に便利です。 またリストの先頭ノードを示すポインタも保持しておかなければなりません。

リストの横断

リストを横断する処理は単純に各ノードの next を参照することを繰り返せば良いです。 null が出てきた時点でリストの末尾に達したことになります。

まずはあえてリストを横断して要素数を数えるメソッドを定義してみます。 本来は size で保持しているのですが、今回はリストの横断を見るために書いてみます。

    /**
     * 単方向リストを横断して要素数を返す
     * 時間計算量:O(n)
     * 空間計算量:0(1)
     *
     * @param head 横断を始めるノード
     * @return 要素数
     */
    private int length(Node<E> head) {
        Node<E> current = head;
        if (current == null) return 0;

        int count = 1;
        while (current.next != null) {
            count++;
            current = current.next;
        }
        return count;
    }

また、指定された位置のノードを取得するメソッドも定義しておきます。

    /**
     * 与えられた整数値がリストのインデックスとして有効か判断する
     *
     * @param index 判定する整数値
     * @return 与えられた整数値が有効であるのか
     */
    private Boolean isPositionIndex(int index) {
        return 0 <= index && index <= size;
    }

    /**
     * 指定された位置のNodeを返す
     *
     * @param index 欲しいNodeの位置を表す整数
     * @return 要求されたNode
     * @throws IndexOutOfBoundsException
     */
    private Node<E> node(int index) {
        if (!isPositionIndex(index)) throw new IndexOutOfBoundsException();

        Node<E> current = first;
        for (int i = 0; i < index; i++)
            current = current.next;

        return current;
    }

リストへの挿入

なんかあまりきれいじゃない気がするけどこんな感じで書きました。

    /***************************************************
     * ノードのlink・unlinkメソッド
     * 前後のnullチェックなどは行わず、
     * 低レベルのlink・unlinkのみを行う。
     ***************************************************/
    /**
     * 指定されたノードに新しい要素のノードをリンクする
     *
     * @param node     リンク元のノード
     * @param nextNode リンクを張りたいノード
     */
    private void link(Node<E> node, Node<E> nextNode) {
        node.next = nextNode;
    }

    /**
     * 与えられたノードが保持する、次のノードとアイテムへのポインタを削除する
     *
     * @param node リンクを断ち切りたいノード
     */
    private void unlink(Node<E> node) {
        node.item = null;
        node.next = null;
    }

    /***************************************************
     * 単一連結リストの挿入
     ***************************************************/
    /**
     * リストの先頭に要素を追加する
     * 時間計算量:O(1)
     * 空間計算量:O(1)
     *
     * @param element 追加したい要素
     * @return 追加後のリスト
     */
    public SinglyLinkedList<E> addFirst(E element) {
        if (first == null)
            first = new Node<E>(element, null); //リストが空だったとき
        else
            this.first = new Node<E>(element, this.first);

        size++;
        return this;
    }

    /**
     * リストの末尾に要素を追加する
     *
     * @param element 追加したい要素
     * @return 追加後のリスト
     */
    public SinglyLinkedList<E> addLast(E element) {
        if (size == 0) return addFirst(element);
        return add(size, element); // sizeのカウントアップはadd(int, E)で行う
    }

    /**
     * リストの指定位置に要素を追加する
     *
     * @param index   要素を追加したい位置
     * @param element 追加したい要素
     * @return 追加後のリスト
     * @throws IndexOutOfBoundsException
     */
    public SinglyLinkedList<E> add(int index, E element) {
        if (!isPositionIndex(index)) throw new IndexOutOfBoundsException();
        if (index == 0) return addFirst(element);

        Node<E> beforeNewNode = node(index - 1);
        link(beforeNewNode, new Node<E>(element, beforeNewNode.next));

        size++;
        return this;
    }