さて前回に続いて自作Listの話です。
前回、リストの要素はCListItemを継承するようにしました。
これでリストの要素自体がリストの前後の情報を持つようになったため、あとは一般的なリストアルゴリズムを適用するだけです。

まずはソースコードです。

public class CList<T_TYPE extends CListItem<T_TYPE>>
{
	T_TYPE	mFront;
	T_TYPE	mBack;
	
	public final T_TYPE front()
	{
		return mFront;
	}
	
	public final T_TYPE back()
	{
		return mBack;
	}

	public final void add(T_TYPE iItem)
	{
		insert(iItem, null);
	}
	
	public final void insert(T_TYPE iItem, T_TYPE iPosition)
	{
		/* iPositionの前にiItemを追加。iPositionがnullなら最後 */
	}
	
	public final void remove(T_TYPE iItem)
	{
		/* 要素を削除する */
	}

	public final void clear()
	{
		/* 全要素をクリアする */
	}
}

insertとremove、clearの詳細な実装は省略しています。
mFrontが最初の要素、mBackが最後の要素を差します。
各要素はmPreviousとmNextで前後の要素を差します。
最初の要素のmPreviousはnull、最後の要素のmNextはnullとなります。
insertとremoveのアルゴリズムで面倒なのは、このmFrontやmBackを適切に設定する部分だけです。

このリストを使用する方法は以下のようになります。

public class CSampleItem extends CListItem<CSampleItem>
{
	public void print() { ～～ }
}

CList<CSampleItem> aList = new CList<CSampleItem>();
aList.add(new CSampleItem());
aList.add(new CSampleItem());
aList.add(new CSampleItem());
for(CSampleItem aItem = aList.front(); aItem != null; aItem = aItem.mNext)
{
	aItem.print();
}

通常のリストとはいくつか異なる点もありますが、しっかりリストになっています。

このリストであれば、前回挙げたArrayListやLinkedListの問題点
(1)オブジェクトを指定しての要素の削除に時間がかかる
(2)要素を削除するとイテレータが無効になる
(3)addの際にメモリ確保が発生する
これらが全て解決します。
ただもちろんよいことばかりではなく、一つの要素は一つのリストにしか追加できなかったりするなどの制約もあります。
またそもそも他のクラスを継承したい場合には使えません。

拡張案としてCListItemをインターフェースにして、継承クラスでgetPrevious()、getNext()を実装するようにすれば、他のクラスを継承していても使えるようになりますが、出来るかぎりリストを辿る部分の処理を高速化するため、単純なメンバー変数としました。

以上で自作リストが使えるようになりました。
フレームワーク内では、このリストを色々なところで使用しています。