• 作成:

JavaのListの連結リストによる独自実装

大学の講義で2015年に書いたMyList.javaを2016年にgistにアップロードしていたのですが, 何故かこれだけ記事にしていませんでした.

何故でしょう? コードが汚かったから恥ずかしかったのかな?

昔のコードが汚いのは当たり前で恥ずかしがることでは無いのに.

というわけで, せっかくなので当時レポートに書いた解説を添えて記事にしておきます.

いやあ, HaskellやC++の思想がまぜこぜになって一貫していないのでかぶれてる感半端ないですね.

ソースコード

当時レポートに書いた解説

ListedList形式の実装を選択した.

フィールドに名前をつけるにあたって, 自分の中での命名法則を整理するために, InkScapeで図を描いた.

head, tailの命名はHaskellのPreludeの影響.

begin, rbegin, endの命名はC++のiteratorの影響.

prev, nextはJavaのiteratorの影響.

begin, rbegin

Mainへの追加

Mainではprintlnによる出力がされている.

いちいちこれを目で見て正しい値を確認するのは大変で, 必ず読み間違いというヒューマンエラーが発生する.

なので, assertによるチェックを挿入しておいた.

また, 独自のテストを末尾に追加した

  • list.subList(from, to).clear();でlistのfrom<=x<tofrom <= x < toまでが削除される
  • removeAllで重複した値が削除される
public class MyList<E> implements List<E>
{
    public static void main(String[] args)
    {
        // MyList クラスのテスト
        List<String> list = new MyList<String>();
        //#1. 引数無しコンストラクター
        list.add("banana");
        //#2. add(E) メソッド
        list.add(0, "apple");
        //#3. add(int,E) メソッド
        System.out.println(list);
        //#4. toString() メソッド -> [apple, banana]
        assert list.equals(new MyList<>(Arrays.asList("apple", "banana")));

        List<String> list2 = new MyList<String>(list);
        //#5. 引数有りコンストラクター(要素の実態をコピー)
        System.out.println(list2.size());
        //#6. size() メソッド -> 2
        assert list2.size() == 2;

        list.remove(0);
        //#7. remove(int) メソッド
        System.out.println(list2.get(0));
        //#8. get(int) メソッド -> apple
        assert list2.get(0) == "apple";

        list2.add("cherry");
        System.out.println(list2.subList(1, 3));
        //#9. subList(int,int) メソッド -> [banana, cherry]
        assert list2.subList(1,3).equals(new MyList<>(Arrays.asList("banana", "cherry")));

        list.clear();
        //#10. clear() メソッド
        System.out.println(list.isEmpty());
        //#11. isEmpty() メソッド -> true
        assert list.isEmpty(): list;

        list2.set(1, "durian");
        //#12. set(int,E) メソッド
        System.out.println(list2.contains("banana"));
        //#13. contains(Object) メソッド -> false
        assert list2.contains("banana") == false;

        System.out.println(list2.indexOf("banana"));
        //#14. indexOf(E) メソッド -> -1
        assert list2.indexOf("banana") == -1;

        Object[] array = list2.toArray();
        //#15. toArray() メソッド
        for(int i = 0; i < array.length; i++)
        {
            System.out.println(i + ":" + array[i]);
            //# -> 0:apple↵ 1:durian↵ 2:cherry
        }
        list = new MyList<String>(list2);
        System.out.println(list == list2);
        //# -> false
        assert (list == list2) == false;

        System.out.println(list.equals(list2));
        //#16. equals(Object) メソッド
        assert list.equals(list2);

        // test by ne260258
        MyList<String> l0 = new MyList<>(Arrays.asList("a", "b", "c", "d"));
        l0.subList(1, 3).clear();
        System.out.println(l0);
        assert l0.equals(new MyList<>(Arrays.asList("a", "d"))): l0;

        ArrayList<String> r0 = new ArrayList<>(Arrays.asList("a", "b", "a", "b", "b"));
        r0.removeAll(Arrays.asList("b"));
        System.out.println(r0);
        assert r0.equals(Arrays.asList("a", "a")) : r0;

        ArrayList<String> r1 = new ArrayList<>(Arrays.asList("a", "b", "a", "b", "b"));
        r1.removeAll(Arrays.asList("a"));
        System.out.println(r1);
        assert r1.equals(Arrays.asList("b", "b", "b")) : r1;
    }
    // メソッドは後述
}

内部利用クラスNode<E>

実際のMyListの解説の前に, MyListが利用するクラスNodeについて解説する.

Nodeは構造体ライクに使われる非公開クラスである. 最初はConsで片方向クラスを実装しようとしたが, Listインターフェイスの仕様でPrevious方向へのアクセスが要求されるため, 双方向にリンクするNodeを作成した.

final class Node<E>
{
    public Node(E h)
    {
        this.head = h;
    }

    public Node(Node<E> take)
    {
        this.head = take.head;
        this.tail = take.tail;
        this.prev = take.prev;
    }

// メソッドは後述

    public E head;
    public Node<E> tail;
    public Node<E> prev;
}

Node<E> get(int distance)

distance分Nodeを辿って, そのNodeを返す.

Lispで言うとnthcdrに相当する.

    public Node<E> get(int distance)
    {
        if(0 <= distance)
        {
            Node<E> result = this;
            for(int i = 0; i < distance; ++i)
            {
                result = result.tail;
            }
            return result;
        }
        else
        {
            Node<E> result = this;
            for(int i = 0; i < Math.abs(distance); ++i)
            {
                result = result.prev;
            }
            return result;
        }
    }

int distance(Node<E> r)

引数rとの距離を計算する.

正(tail)との距離しか取れない.

C++のdistance関数に相当.

    public int distance(Node<E> r)
    {
        int distAmount = 0;
        for(Node<E> step = this; step != r; step = step.tail)
        {
            ++distAmount;
        }
        return distAmount + 1;
    }

static <E> Node<E> link(Node<E> l, Node<E> r)

引数のNodeを連結し, 先頭のNodeを返却する.

3引数版も用意している.

    public static <E> Node<E> link(Node<E> l, Node<E> r)
    {
        if(l == null && r == null)
        {
            return null;
        }
        else if(l == null)
        {
            r.prev = null;
            return r;
        }
        else if(r == null)
        {
            l.tail = null;
            return l;
        }
        else
        {
            l.tail = r;
            r.prev = l;
            return l;
        }
    }

    public static <E> Node<E> link(Node<E> p, Node<E> i, Node<E> n)
    {
        return Node.link(p, Node.link(i, n));
    }

内部利用クラスMyListIterator<E> implements ListIterator<E>

ListIteratorの実装.

indexは内部cacheする.

境界は引数によるbegin, endにより判定する.

recentはremoveの対象であり, 直前のnextである.

final class MyListIterator<E> implements ListIterator<E>
{
    public MyListIterator(int index, Node<E> next, Node<E> begin, Node<E> end)
    {
        this.index = index;
        this.next = next;
        this.begin = begin;
        this.end = end;
    }

// メソッドは後述

    private int index;
    private Node<E> next;
    private Node<E> begin;
    private Node<E> end;

    private Node<E> recent;
}

add

Node.linkを使えば途中に要素を挿入できる.

要素はnextの直前に挿入され, indexが1つ増える.

recentはaddの後に利用できないため, 消去する.

    public void add(E e)
    {
        Node.link(this.next.prev, new Node<E>(e), this.next);
        this.index += 1;
        this.recent = null;
    }

has{Next, Previous}

境界は引数によるbegin, endにより判定する.

    public boolean hasNext()
    {
        return this.next != end;
    }

    public boolean hasPrevious()
    {
        return this.next != begin;
    }

{next, previous}Index

indexは内部に保持している.

    public int nextIndex()
    {
        return this.index;
    }

    public int previousIndex()
    {
        return this.index - 1;
    }

next

nextを持たない場合は例外を投げる.

nextをrecentにキャッシュし, nextとindexを1つ進め, キャッシュしておいたrecentの要素を返す.

    public E next()
    {
        if(!this.hasNext())
        {
            throw new NoSuchElementException();
        }
        this.recent = this.next;
        this.next = this.next.tail;
        this.index += 1;
        return this.recent.head;
    }

previous

nextの逆.

    public E previous()
    {
        if(!this.hasPrevious())
        {
            throw new NoSuchElementException();
        }
        this.recent = this.next.prev;
        this.next = this.next.prev;
        this.index -= 1;
        return this.recent.head;
    }

remove

前回のnext or previous要素を消す, という動作なので, キャッシュしておいたrecentの両端をlinkすれば, recentを消せることがわかる.

indexが減るのは消去するのが後方の場合のみなので, 前回がnextだった時のみである.

    public void remove()
    {
        if(recent == null)
        {
            throw new IllegalStateException();
        }
        if(this.recent != this.next) // 前回実行はnext
        {
            this.index -= 1;
        }
        Node.link(this.recent.prev, this.recent.tail);
        this.recent = null;
    }

set

前回のnext or previous要素の中身を書き換える, という動作なので, recentのheadを書き換える.

    public void set(E e)
    {
        if(recent == null)
        {
            throw new IllegalStateException();
        }
        this.recent.head = e;
        this.recent = null;
    }

MyListのコンストラクタ

空コンストラクタ, 1つの要素で初期化するコンストラクタ, Collectionで初期化するコンストラクタの他に, subListで利用するための, Nodeを2つ取るコンストラクタを作成した. Nodeを2つ取るものは, subListで使うだけなので, private指定してある.

    public MyList()
    {
    }

    public MyList(E e)
    {
        this.begin = new Node<E>(e);
        this.rbegin = this.begin;
    }

    public MyList(Collection<? extends E> c)
    {
        c.stream().forEach(this::add);
    }

    private MyList(Node<E> l, Node<E> r)
    {
        this.begin = l;
        this.rbegin = r;
    }

add

  • add(E e)
  • add(int index, E element)
  • addFirst(E e)
  • addLast(E e)

の4つのメソッドを作成した.

この内, addはaddLastのただのエイリアスである.

    public boolean add(E e)
    {
        this.addLast(e);
        return true;
    }

要素を中間に挿入するという操作は, Node.linkを使えば容易に実現できる.

しかし, 両端をフィールドとして保持している関係上, 先端か終端への追加があった場合, 両端を更新しなければならない.

そのため, 挿入する要素の左隣となるNodeを比較する. nullなら先端, rbeginなら終端に挿入されるとわかるため, addFirst,addLastを呼び出す.

    public void add(int index, E element)
    {
        Node<E> l = this.getNode(index - 1);
        if(l == null)
        {
            this.addFirst(element);
        }
        else if(l == this.rbegin)
        {
            this.addLast(element);
        }
        else
        {
            Node.link(l, new Node<E>(element), l.tail);
        }
    }

    public void addFirst(E e)
    {
        if(this.begin == null)  // cons的な方式だと両端リストには対応できないので,nullチェックが必要
        {
            this.begin = new Node<E>(e);
            this.rbegin = this.begin;
        }
        else
        {
            this.begin = Node.link(this.begin.prev, new Node<E>(e), this.begin);
        }
    }

    public void addLast(E e)
    {
        if(this.begin == null)
        {
            this.begin = new Node<E>(e);
            this.rbegin = this.begin;
        }
        else
        {
            this.rbegin = Node.link(this.rbegin, new Node<E>(e), this.rbegin.tail).tail;
        }
    }

addAll

streamライブラリ1を使って挿入動作を繰り返す.

    public boolean addAll(Collection<? extends E> c)
    {
        c.stream().forEach(this::addLast);
        return (c.isEmpty()) ? false : true;
    }

    public boolean addAll(int index, Collection<? extends E> c)
    {
        return index !=
            c.stream().reduce(index, (i, e) ->
                              {
                                  this.add(i, e);
                                  return index + 1;
                              },
                              (il, ir) -> il + ir);
    }

clear

IntStream.range(0, n).forEachを使えばn回操作を繰り返せるので, それを使ってn回removeFirstすれば全て消える.

ここでbeginとrbeginをnullにする.という操作をしてはいけない. subList.clear()で元のリストの要素が消えなくなる.

    public void clear()
    {
        IntStream.range(0, this.size()).forEach(n -> this.removeFirst());
    }

contain

containsは同じ要素が1つでもあれば良い. anyMatchを使えば, 簡単に1つ含んでいるかの検索が出来る.

    public boolean contains(Object o)
    {
        return this.stream().anyMatch(e -> e == null ? o == null : e.equals(o));
    }

containsAllは引数Collection cの全ての要素において, containsがtrueになれば良いので, allMatchを使って全てtrueか判定する.

    public boolean containsAll(Collection<?> c)
    {
        return c.stream().allMatch(this::contains);
    }

equals

equalは, Listの規約でListの実装のみと等しくなると決まっている.

そのため, Listへのキャストに失敗した場合はfalseとなるため, 例外をキャッチしたらfalseを返す.

比較は普通にiteratorで出来る.自明.

    @SuppressWarnings("unchecked") // 例外はcatchするので問題ない
    public boolean equals(Object o)
    {
        try
        {
            // 規約によると,ListはListとのみ等しくなる
            for(ListIterator<E> ti = this.listIterator(), oi = ((List<E>)o).listIterator();
                ti.hasNext() || oi.hasNext();)
            {
                if(ti.next() != oi.next())
                {
                    return false;
                }
            }
            return true;
        }
        catch(RuntimeException e)
        {
            return false;
        }
    }

get

node.get(n)を使うだけで良かったのだが, nullチェックをまとめたかったため, getNodeをメソッド化して呼ぶ.

    private Node<E> getNode(int index)
    {
        if(this.begin == null)
        {
            throw new IndexOutOfBoundsException();
        }
        return this.begin.get(index);
    }

    public E get(int index)
    {
        return this.getNode(index).head;
    }

hashCode

これは規約で計算方法が決まっている.2

    public int hashCode()
    {
        return this.stream().reduce(1, (l, r) -> 31 * l + r.hashCode(), (a, b) -> a + b);
    }

indexOf

null同士も等しいとみなす.

見つからなければ-1を返す.

後は自明.

    public int indexOf(Object o)
    {
        int index = 0;
        for(ListIterator<E> it = this.listIterator(); it.hasNext(); ++index)
        {
            final E e = it.next();
            if((o == null && e == null) || o.equals(e))
            {
                return index;
            }
        }
        return -1;              // List規約: 見つからなければ-1
    }

lastIndexOf

indexOfの逆.

    public int lastIndexOf(Object o)
    {
        int index = this.size() - 1;
        for(ListIterator<E> it = this.listIterator(this.size() - 1); it.hasPrevious(); --index)
        {
            final E e = it.previous();
            if((o == null && e == null) || o.equals(e))
            {
                return index;
            }
        }
        return -1;              // List規約: 見つからなければ-1
    }

isEmpty

MyListでは, 先端のNodeがnullの時が空リストであると規定した.

    public boolean isEmpty()
    {
        return this.begin == null;
    }

iterator

MyListIteratorクラスのコンストラクタを呼ぶ.

ただし, 空リストの場合, next = begin = end = nullである動かないiteratorを作る. 空リストのgetNodeを使うと例外が発生することの回避でもある.

    public Iterator<E> iterator()
    {
        return this.listIterator();
    }

    public ListIterator<E> listIterator()
    {
        return this.listIterator(0);
    }

    public ListIterator<E> listIterator(int index)
    {
        return this.begin == null ?
            new MyListIterator<E>(index, null, null, null):
            new MyListIterator<E>(index, this.getNode(index), this.begin, this.rbegin.tail);
    }

remove

addのように, 両端への呼び出しはbegin, rbeginを更新する必要がある. 削除自体はNode.linkを使えば簡単である.

boolean remove(Object o)では内部でfirstとlastにマッチした時の処理をする.

    public E remove(int index)
    {
        Node<E> removeTarget = this.getNode(index);
        if(removeTarget == this.begin)
        {
            return removeFirst();
        }
        else if(removeTarget == this.rbegin)
        {
            return removeLast();
        }
        else
        {
            E result = removeTarget.head;
            Node.link(removeTarget.prev,
 removeTarget.tail);
            return result;
        }
    }

    public E removeFirst()
    {
        E removedElement = this.begin.head;
        Node.link(this.begin.prev, this.begin.tail);
        this.begin = this.begin.tail;
        return removedElement;
    }

    public E removeLast()
    {
        E removedElement = this.rbegin.head;
        Node.link(this.rbegin.prev, this.rbegin.tail);
        this.rbegin = this.rbegin.prev;
        return removedElement;
    }

    public boolean remove(Object o)
    {
        Node<E> e = this.begin;
        if(e.head.equals(o))    // first
        {
            this.removeFirst();
            return true;
        }
        for(e = e.tail; e != this.rbegin; e = e.tail)
        {
            if(e.head.equals(o))
            {
                Node.link(e.prev, e.tail);
                return true;
            }
        }
        if(e.head.equals(o))    // last
        {
            this.removeLast();
            return true;
        }
        return false;
    }

removeAll

変更されたらtrueを返すため, changed変数に記録しておく.

streamライブラリはJavaのreduceが同じ型しか取れないこと, Javaのラムダ式がクロージャではないことからchangeが変更できないので使えない.

iteratorで辿ってremoveする.

    @SuppressWarnings("unchecked") // 例外発生までがListの仕様
    public boolean removeAll(Collection<?> c)
    {
        boolean changed = false;
        for(ListIterator<E> eit = this.listIterator(); eit.hasNext();)
        {
            if(c.contains(eit.next()))
            {
                eit.remove();
                changed = true;
            }
        }
        return changed;
    }

retainAll

retainAllでは, removeAllとは逆の条件文を設定する.

    @SuppressWarnings("unchecked") // 例外発生までがListの仕様
    public boolean retainAll(Collection<?> c)
    {
        boolean changed = false;
        for(ListIterator<E> eit = this.listIterator(); eit.hasNext();)
        {
            if(!c.contains(eit.next()))
            {
                eit.remove();
                changed = true;
            }
        }
        return changed;
    }

set

getNodeで取得した要素のheadを変更するだけ.

    public E set(int index, E element)
    {
        Node<E> resetNode = this.getNode(index);
        E resetElement = resetNode.head;
        resetNode.head = element;
        return resetElement;
    }

size

距離を測るNode.distanceでbeginとrbeginの距離を測る. ただし, 空リストの場合はsize == 0であると直接記述する.

    public int size()
    {
        return this.begin == null ? 0 : this.begin.distance(this.rbegin);
    }

subList

toIndexの要素は含まないことに注意して, 新しいリストを返す.

    public List<E> subList(int fromIndex, int toIndex)
    {
        return new MyList<E>(this.getNode(fromIndex), this.getNode(toIndex - 1));
    }

toArray

this.sizeの長さObjectのArrayを生成してそれに各要素を突っ込んで返すだけ.

引数ありのバージョンでは, 余った要素にはnullを入力する必要がある.

    public Object[] toArray()
    {
        Object[] array = new Object[this.size()];
        int i = 0;
        for(ListIterator it = this.listIterator(); it.hasNext(); ++i)
        {
            array[i] = (Object)(it.next());
        }
        return array;
    }

    @SuppressWarnings("unchecked") // 例外発生許容
    public <T> T[] toArray(T[] a)
    {
        if(this.size() <= a.length)
        {
            int i = 0;
            for(ListIterator<E> it = this.listIterator(); it.hasNext(); ++i)
            {
                a[i] = (T)(it.next());
            }
            for(; i < a.length; ++i) // Listの規約: 残りはnull埋めする
            {
                a[i] = null;
            }
            return a;
        }
        else
        {
            Object[] array = new Object[this.size()];
            int i = 0;
            for(ListIterator it = this.listIterator(); it.hasNext(); ++i)
            {
                array[i] = (T)(it.next());
            }
            return (T[])array;
        }
    }

toString

StringBuilderにtoStringした各要素を足してそれを返すだけ.

ただし, 全てループで行うと最後に余計なカンマが入るため, 最初の要素だけは特別に処理する.

    public String toString()
    {
        StringBuilder acc = new StringBuilder("[");
        ListIterator<E> it = this.listIterator();
        if(it.hasNext())
        {
            acc.append(it.next());
        }
        while(it.hasNext())
        {
            acc.append(", ");
            acc.append(it.next());
        }
        acc.append("]");
        return acc.toString();
    }

テスト実行結果

% java -ea MyList
[apple, banana]
2
apple
[banana, cherry]
true
false
-1
0:apple
1:durian
2:cherry
false
true
[a, d]

補遺

未テストのメソッドがかなりある.その動作はかなり怪しい.

特にMyListIterator関連のメソッドはテストしていない.

全てのメソッドに対してテストを記述しようとしたが, 時間が足りなかったため断念した. 今回の課題のテストはクリアしているので, 課題としては良いとする.

  1. Java Streamメモ(Hishidama's Java8 Stream Memo)↩︎

  2. https://docs.oracle.com/javase/jp/8/api/java/util/List.html#hashCode--↩︎