List

list.png
クラス 説明 重複 利点 欠点
ArrayList 配列を扱います。 O 任意の位置への参照get(index)が速い sort()が無い,末尾以外へのadd()がLinkedListよりも遅い
LinkedList 配列を扱います。挿入・削除が高速です。順次アクセスも高速 O 任意の位置へのadd(),remove()が高速 任意の位置への参照が遅い
Vector 配列を扱います。排他制御をおこなう.パフォーマンスが悪いため現在ではあまり推奨されない古いクラスです。互換性のためだけに存在している O

各要素に順番にアクセスするときはiteratorか、getか?

ArrayListの時はget()の方が若干早いが、あまり大差がない。どっちにしろ遅いって感じ。
LinkedList…get()にすると圧倒的に遅く、Iteratorにすると圧倒的に早い、ArrayList使うよりも早い[1]

ArrayListとLinkedListの違い

ArrayListは、リストの真ん中あたりにある要素の番号を指定して要素を引っ張り出してくるのが早い。
LinkedListは、頭から数えていかないととってこれない。
ArrayListは、リストの真ん中あたりにある要素を削除したり追加したりするときに、他の要素の番号を振りなおさないといけないので大変。
LinkedListは、リンクを切り貼りするだけで済む。
大量のデータをリストに入れる場合、真ん中あたりへの追加や削除が多そうだったらLinkedList。真ん中あたりを参照するのが多そうだったらArrayList。っていう感じで判断すれば良いと思う。

配列よりリストを選ぶ理由

名著Effective Javaの項目25に配列よりリストを選ぶとある。
配列の方が速いからなるべく配列を使うべきだって思ってたんだけど、どういうこと?

配列の欠点 ジェネリックスの美点
配列は共変である。
配列は具象化されている。
違う型を入れても、実行時にならないとエラーかどうかわからない。
ジェネリックスは不変である
ジェネリックスはイレイジャで実装されている
違う型を入れたら、コンパイル時にエラーになる。
Object[] objArray=new Long[1];
objArray[0]="I Don't fit in";//実行時にArrayStoreExceptionがスローされる
//ArrayStoreException は、配列に不正な型のオブジェクトを格納しようとしたときに起きる
List<Object> ol=new ArrayList<Long>();//互換性の無い型
ol.add("I Don't fit in");//ちゃんとコンパイルエラーになる。

sequence-container

サポートサイト Wikidot.com sequence-container