【連結リスト(Linked List)】

　前回とりあげた Vector と ArrayList は，配列同様に複数のデータを格納するランダムアクセスコレクション
であった。前回学修したように，ランダムアクセスとは，

　・格納されている要素数とは無関係に各要素へ一瞬でアクセスすることが可能(要素番号からその要素の格納されているメモリ上の位置，つまりメモリアドレスが計算できるため)
　・要素の挿入・削除に，格納されている要素数に比例した時間がかかる(要素のずらしコピーが発生するため)

という性質を持つ。

　今回の最初に，このランダムアクセスとほぼ逆のアクセス特性を持つ連結リスト(Linked List)を紹介する。
連結リストとは，参照関係を使ってオブジェクトを数珠つなぎ状にしたデータ構造である(下図Fig. 1)。

まず，個々のデータはセル(cell)と呼ばれるオブジェクトにくるまれている(Fig.1 -(1)(a))。図にあるように，
セルにはデータを格納するフィールド(図の例ではdata)の他に，次のセルへの参照値を格納するフィールド
(図ではnext) がある。実際にJavaのコードでセルを表すクラスを定義すると Fig.1-(1)(b) の Cell の様になる。
この Cell の定義をよく見ると，自分と同じ Cell 型への参照フィールドがある。このように，自クラスへの
参照フィールドを持つクラスを一般に自己参照型と呼ぶ。

単純な連結リストの実装例を Fig.1-(2) に示す。Fig.1-(2)(a)に図示されているのは，登録されている有効
要素が1個も無い状態，つまり「空(から)」の状態である。Fig.1-(2)(b)の mainメソッドを①まで実行すると
この状態になる。すでに2つのセルが存在しているがこれはダミーのセルで，これから登録する有効要素(セル)
を前後から挟む形となる(下図右下のFig.1-(4)参照)。連結リストの実装では，このように有効要素の列をダミ
ーの要素で挟むと，連結リスのに関する処理がシンプルに書けることが知られている。
以降の説明は下図Fig.1のに続く。

図中のサンプルプログラム(SingleLinkedList.java)


　Fig.1-(2)に例示した連結リストに要素を追加する処理を　Fig.1-(3)に示す。Fig.1-(2)(b)の mainメソッドの①
まで実行した状態が Fig.1-(2)(a)の図であった。その状態から，Fig.1-(2)(b)の mainメソッドの①の次の for文
の処理にうつり，カウンタ変数iの値が1のとき，処理② sll.add( new SingleLinkedList( i )) を実行したときの様子が
Fig.1-(3) である。このfor文を最後まで実行すると Fig.1-(4)のように3個の有効要素(セル)が追加されることになる。

●連結リストの特徴

　ランダムアクセスなコレクション(配列・Vector・ArrayListなど) は，要素への高速なアクセスランダムアクセスが
可能であることを学んだ。しかし，連結リストは要素へのアクセスは遅い。Fig.1-(2)(b)の③のfor文で登録されている
全3個の要素のデータ値を表示しているが，先頭のセルから始めて各セルのnextフィールドに入っている参照値をたどっ
て次のセルへ、次のセルへ，というようにセルをたどっていることがわかる。

　このことからわかるように，連結リストでは，先頭要素から参照によるリンク(接続)を順にたどっていかないと目的の
要素へ到達できない。このように，目的の要素へ到達するためには最初の要素から始めて目的の要素までにあるすべて
の要素に順次アクセスしていかなくてはいけないアクセス方法をシーケンシャルアクセス(順次アクセス)と呼ぶ。その
仕組みから， 順次アクセスは，登録されている要素数の下図に比例して時間がかかってしまう。

　一方，連結リストは要素の挿入・要素の削除はほぼ即時に行うことが出来る。要素を挿入する場合の処理の流れを
下図 Fig.2 に示す。この図では，変数positionに格納されている参照値で参照されているセルの後ろに，変数theCellに
格納されている参照値で参照しているセルを挿入する処理を解説している。図で分かるように，たった2つの変数の参照値
を代入で書き換えるだけで挿入処理が完了する。もちろん，要素の削除はこの逆処理を行えば良いことになる。つまり，
連結リストは要素の挿入・削除は，連結リストに登録されている有効要素の数に関係無く，即時に行うことが出来る。



ここで，
　・ランダムアクセスなコレクション(配列・Vector・ArrayListなど)
　・連結リスト
の主な性質を下表にまとめてみる。表からも明らかなように，両者は対照的な性質を持っているので，
　・要素が頻繁に挿入削除される→連結リストを使う
　・要素が頻繁に挿入削除されることはない→ランダムアクセスなコレクション(配列・Vector・ArrayListなど)を使う
というように使い分けると良い。

●LinkedList<E>クラス

　Javaにも当然ながら連結リストを実装したジェネリッククラスとしてjava.util パッケージの LinkedLis<E>が用意されている。
LinkedList<E>は，下図Fig.3 のように，「次の要素への参照値」だけでなく「直前の要素への参照値」も使い，双方向に要素
をリンクさせた二重リンクリスト(双方向リスト，double linked list)になっている。そのため，逆方向のリンクをたどることで
末尾要素から先頭要素に向けて要素を走査することも可能になっている。




●LinkedList<E>の使用例とリストイテレータ

LinkedList<E>の使用例 LinkedListSample.java を以下に示す。

import java.util.LinkedList; // java.util.LinkedListをインポートする。
import java.util.ListIterator; // java.util.ListIteratorをインポートする。

class LinkedListSample{

  public static void main( String [ ] args ) {

    LinkedList<Integer> llist = new LinkedList<Integer>();  // LinkedList<Integer>型オブジェクトの生成

    for( int i = 1; i <= 3; i++ ) llist.add( new Integer( i ) ); // 有効要素の末尾に3個要素を追加。
    llist.add( 0, new Integer( 0 ) ); // 0番目に新たに要素を追加

    ListIterator<Integer> itor = llist.listIterator( 0 ); // 0番目(先頭)の要素を指すリストイテレータを得る。
    while( itor.hasNext( ) ) { // リストイテレータの hasNextメソッドは次の要素がまだあれば true を返す。
      System.out.println( itor.next( ) ); // リストイテレータの nextメソッドは，現在の要素を返し，イテレータを進める。
    }
    // for( int i = 0; i < llist.size(); i++ ) System.out.println( llist.indexOf( i ) ); // これは非効率
  }
}

解説：
　・1行目で LinkedList をインポートしている。
　・8行目で ，Integer型オブジェクトを格納する LinkedList<Integer>型オブジェクトを生成している。
　・9行目で，addメソッドで新たな要素を連結リストの末尾に追加している。
　・17行目で全有効要素の値を表示しているが，実はこれは非効率である。sizeメソッドで有効要素の総数を，indexOfメソッドで
　　要素番号で要素を指定している。ところが，llist.indexOf( i ) としてi番目の要素までその都度シーケンシャルアクセスするので
　　遅くなる。そこで，リストの特性を活かして全要素の走査を効率良く行っているのが13〜16行目である。
　・13行目で，listIterator というメソッドを呼び出して，ListIterator<Integer>型のオブジェクトを取得している。イテレータ
　　とは，反復子とも呼ばれ， 要素列中の要素を指し示し，要素の値を読み書きする装置のようなものである(下図Fig.5)。
　　14行目で使われている hasNext メソッドは，イテレータが指し示す要素の次の要素が存在する場合は true を返す。
　　15行目で使われている next メソッドは，イテレータが指している要素(ここではInteger型オブジェクト)を返し，イテレータ自身
　　は次の要素を指すように移動する。ちなみに，ここでは使用していないがpreviousメソッドはイテレータが指している要素を返し，
　　イテレータ自身は直前の要素を指すように移動する。このようにイテレータを使う事で，効率良く連結リストの要素を走査するこ
　　とができる。




LinkedList<E>のより詳しい使い方については，APIドキュメントのLinkedList<E>の項目を見よ。

次に進む