はじめに
ArrayList
ArrayListは、リストインターフェイスの実装クラスは、下部には、ストレージ構造の配列の実装に基づいており、データをロードするために使用することができます、データは、配列変数に格納されています。
transient Object[] elementData;
transientはキーワードであり、その役割は、1つの文に要約することができます：キーワードtransientを直列化する必要がないプロパティの前に追加すると、オブジェクトを直列化するとき、このプロパティは直列化されません。 あなたは奇妙に感じるかもしれませんが、ArrayListはああ、ソースコードが、java.io.Serializableインタフェースの実装をシリアライズすることができ、なぜtransientの定義と配列変数それ？
これについては後述しますのでご心配なく、アイデアを売り込むためではなく、結末をどう見るか、それから見るポイントを教えてください。
新しいインスタンスが作成されると、ArrayListはデフォルトで配列のサイズを10に初期化します。
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
しかし、これは配列の容量サイズだけで、リストの実際のサイズではないことに注意してください、リストのサイズは、ソースコードでは、実際の容量を取得するには、格納されているデータの量によって決定されるべきであることを示すために、実際には変数のサイズです。
private int size;
ソースコードでは、データはデフォルトで配列の最初のインデックスから格納され、データを追加するとき、ArrayListは最後のインデックスの後ろまでデータを埋めるので、ArrayListのデータは順序付けされています。また、ArrayList自体が配列のストレージに基づいているため、クエリは正しい要素を見つけるためにインデックスの添え字に基づいてのみでよいので、クエリのパフォーマンスが非常に高く、これもArrayListに非常に有利であることが最も重要な理由です。
しかし、配列の容量は決まっているので、格納するデータのサイズが配列のサイズを超えると、配列のout-of-bounds問題が発生するのでは？
この点については、心配しないで、ArrayListは、処理の動的拡張を行うには、新しいデータ、リストのサイズが配列の容量を超えていることが判明した場合、それは新しい配列の元の1.5倍の容量のための新しい配列を追加し、データの元の配列は、新しい配列に変更されずにコピーし、新しい配列の完了時に元の配列オブジェクトに新しい配列を割り当てます。
拡張後、アレイは新しいデータを追加するのに十分な容量を持っています。
さらに、ArrayListは、新しいメソッドのインデックスを指定するためのサポートを提供しています。つまり、セットインデックスの添え字にデータを挿入することができます。
挿入データは、ArrayListの操作は、すべての上にもう一度コピーする配列の背後にある最初の3であり、その後、データのこの部分は、実際には、1つずつ1つのバックのインデックス位置に割り当てられて移動し、位置の後ろに3が空にすることができます、データ操作の挿入の完了に4を入れて
削除する場合も同様で、インデックスを指定し、その後ろのデータのコピーを作成し、元のインデックスの位置のデータが削除されるように前に移動します。
ここでは、この配列ベースのクエリが効率的であることを見つけるのは難しいことではありませんが、データを追加または削除すると、すべての要素の後ろに対応するインデックスを移動する要素の各増分削除は、非常にパフォーマンスが消費されるため、データの量は問題ではありませんが、あなたは努力にデータの数千数千を格納する場合ので、それは頻繁な追加と削除の場合であれば、それはArrayListを使用することはお勧めしません。
ArrayListは推奨されないので、このような場合に利用できる他のコレクションはありますか？
もちろんありますし、私のような温厚な男なら真っ先に教えてくれるに違いありません。それが、これからお話しするLinkedListにつながるのです。
LinkedList
LinkedListは、双方向チェーンテーブルの実装に基づいて、初期容量を指定する必要はありません、チェーンテーブル内の任意のストレージユニットは、前方または後方のポインタは、ストレージユニットの前面または背面に取得することができます。LinkedListのソースコードでは、そのストレージユニットはNodeクラスで表されます：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
ノードには、データを格納するitem、前の記憶装置を指すprev、次の記憶装置を指すnextの3つのメンバがあり、この2つのノードを前後のノードと関連付けることで、チェーンテーブルの構造に組み立てることができます。
ノードのアドレスの前後に保存されているため、LinkedListの追加と削除のデータがArrayListのようなデータの全体の部分を移動する必要はありません、ちょうど参照によって2つのノードの前と後のインデックスの位置を指定することができます、たとえば、李白と韓信の間に孫悟空のノードに挿入されるため、唯一のこのようなノードへのポインティングのアドレスの下にノードに対処する必要があります：
インデックス位置の前後2つのノードのアドレスを変更するだけです。
このようなリンクリスト構造は、LinkedListは、データの追加と削除で非常に効率的にすることができ、シナリオの頻繁な追加と削除では、使用することは非常に良いことができますが、欠点もあります。
データの追加と削除は非常に高速ですが、クエリがよくない、LinkedListは、データのインデックス位置に対応するクエリが、それは最初の値のチェーンテーブルの半分の合計の長さの値を計算し、インデックスが左または右の値である読み取り、その後、ノードの先頭ノードまたは末尾からトラバースを開始することを決定し、インデックスが末尾から計算されます双方向チェーンテーブルストレージに基づいています。
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
最適化のために二等分されたとはいえ、チェーンテーブルの半分の長さをトラバースすることになり、データ量が非常に多い場合、このようなクエリは非常に時間がかかることは間違いありません。
これはまた、最も無力な場所LinkedListは、魚と熊の両方にすることはできませんが、両方の高速をチェックしたいだけでなく、高速に追加および削除するには、どのようにこのような良いことがそれに遭遇させることができますか？したがって、一般的にLinkedListが増加し、より少ないクエリのシナリオを削除するために使用することをお勧めします。
加えて、LinkedListのメモリ消費量も比較的大きく、結局のところ、各Nodeは、アドレスの前後を指すノードを維持し、データ量が多ければ、多くのメモリ領域を占有します。
どちらの方がスペースをとりますか？
そういえば、タイトルの疑問は晴れましたか？
ビジネスに戻って、表面的には、LinkedListのノードのストレージ構造は、より多くのスペースを取るように見えますが、ArrayListの拡張の導入を忘れてはならない、それはデフォルトでは、元の1.5倍に配列の容量を拡張するために、もしあなただけの要素を追加すると、元の配列のほぼ半分の大きさのスペースが無駄になります元の配列が非常に大きい場合、その後要素を1つ追加するだけなら、配列の元のサイズの半分近くが無駄になります。
ですから、大量のデータをリアルタイムで追加する場合、ArrayListの方がLinkedListの容量よりも少ない容量で済むとは限りませんので、もう少し慎重な答えになり、納得しやすく聞こえますが、この答えが完璧だと思いますか？しかし、あなたはこの答えが完璧だと思いますか？
先ほどのtransient変数を覚えていますか？transientでelementDataを変更するということは、elementData配列をシリアライズさせたくないということです。なぜそんなことを？
なぜなら、ArrayListをシリアライズするとき、ArrayListの中のelementData、つまり配列がいっぱいになるとは限らないからです。 もちろん必要ありません。そこでArrayListはwriteObjectメソッドを書き直しました：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
あなたがシリアライズするたびにこのメソッドを呼び出して、最初にArrayList内の非一時的な要素をシリアライズするdefaultWriteObject（）メソッドを呼び出し、elementData配列オブジェクトは、それをシリアライズするために行くことはありませんが、elementDataをトラバースし、その中にデータを持っている配列の要素のみをシリアライズし、この方法では、することができます。シリアライズの速度を加速するだけでなく、スペースのオーバーヘッドを減らすことができます。
各ノードが前後のアドレスを指す2つのノードを維持するため、一般的に、LinkedListは、より多くのスペースを占有しますが、それは絶対的なものではありません、それはArrayListのデフォルトの一時的な値のデータ量よりも多くなることが発生した場合、ArrayListは、スペースを占有するため、理由の拡大は、元の配列の容量のほぼ半分を無駄にされる、しかし、小さいものではありません。ArrayListの配列変数は、transientキーワードで変更され、コレクション自体が直列化操作を行う必要がある場合は、ArrayListの余分な領域のこの部分は直列化されません。
