フレームワークやゲームを作成していると、色々なところでリスト構造が必要になります。
JavaにはArrayListやLinkedListなどが組み込みで存在するので、最初はこれを使おうと思っていたのですが、いくつかの点で望む使い方ができなかったため、リスト機能を自作することにしました。

まず最初に、ArrayListやLinkedListにどういう問題があったかというと
(1)オブジェクトを指定しての要素の削除に時間がかかる
(2)要素を削除するとイテレータが無効になる
(3)addの際にメモリ確保が発生する
大きく以上の３点です。
それぞれについて軽く解説します。

(1)の要素の削除に時間がかかるという問題です。
これに関してはLinkedListなら要素の削除が早いと色々なところで書かれています。
しかしこれには条件があって、イテレータでループを回してそのremoveを呼び出した場合には確かに早いのですが、オブジェクトを指定してremoveした場合は、そのオブジェクトを線形探査する処理が入るため、要素が多い場合には非常に遅くなります。

(2)のイテレータが無効になるというのは、リストに要素を追加、削除すると、そのリストから取得した他のイテレータが使えなくなるということです。（使うと例外が発生します）
ArrayListはインデックスでのアクセスができるため、要素を追加、削除すると、後ろにある要素がずれるため、イテレータが無効になるのは妥当です。
LinkedListに関しては実装上は問題なさそうですが、仕様としてそうなっているようです。
もしイテレータが無効にならないなら、(1)の要素の削除に時間がかかるという問題は、リストへの追加時にイテレータを保持しておくことで対処することが可能です。
また指定した要素の前後に新しく要素を追加したい場合も、この保持しておいたイテレータで行うことができます。

(3)のメモリ確保はArrayListの場合は毎回というわけではなく、メモリ確保の発生はキャパシティを超えた場合のみですが、それでもゲーム動作中にはあまりメモリ確保を行ってほしくありません。（ガベージコレクトは極力起こしたくありません）

このようにゲームで気軽に使うにはちょっとずつ問題があったため、必要機能を絞ったシンプルなリスト機能を自作することにしました。
その自作リストの仕様ですが、c++のライブラリであるboostにintrusive_listという機能があります。
これはリストの要素となるオブジェクトが特定のクラスを継承する必要があるのですが（もしくはメンバ変数として特定のクラスを持つ必要がある）、リストへの追加時にメモリ確保が発生しないという利点があります。
この仕様を参考に、Javaではリスト要素となるオブジェクトは以下のクラスを継承することにしました。

public class CListItem<T_TYPE extends CListItem<T_TYPE>>
{
	public T_TYPE	mPrevious;
	public T_TYPE	mNext;
}

ジェネリクスなクラスですが、型の指定が奇妙な感じになっています。
見慣れないと分かりにくいですが、要はCListItemのT_TYPEはCListItemを継承している必要があるという指定です。
ちなみにこのクラスを継承する方はどう書くかというと

public class CSampleItem extends CListItem<CSampleItem>

このようになります。こちらも継承元のテンプレート引数に自分自身が登場する奇妙な感じになっています。
ただ辿っていくとそれほど難解なものではなく、要は自分自身と同じ型のmNextとmPreviousをもつというだけの話です。
ちなみにこのように継承元に自分自身を渡すやり方を、奇妙に再帰したテンプレートパターン(Curiously Recurring Template Pattern)と言います。

これでリストに必要なデータをオブジェクト自体に持たせることができるようになりました。
あとはこのmNextとmPreviousを使用したリスト本体を作成すれば、自作リストの完成です。
長くなってきたので、リスト本体に関する話は次回にします。