1。ArrayListソースコード分析（JDK7）
ArrayListは、動的オブジェクトアレイを内部的に維持します。 ArrayListの動的な追加と削除は、このグループの動的な追加と削除です。
1。アレイリストの構築と初期化
ArrayList Instance Variable // ArrayList Default容量プライベート静的最終int default_capacity = 10; //デフォルトの空のオブジェクトアレイ、空のarraylistprivate静的オブジェクト[] empty_elementData = {}ArrayList Constructor：
パラメーターコンストラクターなし：つまり、空のオブジェクトを作成します[]
public arrayList（）{super（）; this.ElementData = empty_ElementData;}容量サイズの構成を指定します。
public arrayList（int initialCapacity）{super（）; if（initialcapacity <0）を新しいIllegalargumentException（ "違法容量："+ initial -capacity）; this.ElementData = new Object [initialCapacity];}コレクションインターフェイスを実装するコレクション構造を指定します。
public arrayList（collection <？extends e> c）{elementData = C.ToArray（）; size = elementdata.length; // C.ToArrayは（誤って）オブジェクトを返しない可能性があります[]（6260652を参照）if（elementData.getClass（）！= object []。class）elementData = arrays.copyof（size、object、class）;}これは、コレクションの役割と、Java-Collection-Framworkがリスト、セット、その他のインターフェイスを直接使用するのではなく、コレクションインターフェイスを設計する理由も説明しています。
2。アレイリストの容量割り当てメカニズム
ArrayListの容量キャップ：アレイリスト容量は上限であり、理論によりinteger.max_value -8サイズの容量の割り当てが可能になります。ただし、どのくらい割り当てられるかはスタック設定によって異なり、VMパラメーターを設定する必要があります
Private Static Final int max_array_size = integer.max_value -8;
追加メソッドを呼び出すときにボリュームを拡張します
public boolean add（e e）{ensurecapacityinternal（size + 1）; // increments modcount !! elementData [size ++] = e; trueを返します。 }EnsureCapacity -internal（int）メソッドは、実際に最小拡張サイズを決定します。
private void ensurecapacityinternal（int mincapacity）{if（elementData == empty_ElementData）{mincapacity = math.max（default_capacity、mincapacity）; } suresexplicitcapacity（mincapacity）; } private void suresexplicitcapacity（int mincapacity）{modcount ++; //オーバーフロー - 意識コードif（mincapacity -elementdata.length> 0）grow（mincapacity）; } ModCountについて：ModCountは、Abstract Class AbstractListで定義されています。ソースコードのコメントは基本的にその使用を説明しています。Iteratorを使用してトラバースを使用する場合、リスト内の要素に構造的な変更があるかどうかを確認するために使用されます（リスト要素の数の数が変更されました）。これは、主にマルチスレッド環境で使用され、1つのスレッドが反復するのを防ぎ、別のスレッドがこのリストの構造を変更します。
成長方法は実際の拡張方法です
private void grow（int mincapacity）{//オーバーフロー意識コードint oldcapacity = elementdata.length; int newcapacity = oldcapacity +（oldcapacity >> 1）; if（newcapacity -mincapacity <0）newcapacity = mincapacity; if（newcapacity -max_array_size> 0）newcapacity = hugecapacity（mincapacity）; // mincapacityは通常サイズに近いため、これはwinです。 }どれだけの容量が拡張されているかについてのugecapacityメソッドもあります
private static int hugecapacity（int mincapacity）{if（mincapacity <0）//オーバーフロー新しいoutofmemoryerror（）; return（mincapacity> max_array_size）？ integer.max_value：max_array_size; }要約：
各拡張にはアレイのコピーが伴うため、一度に適切な容量を与えると、パフォーマンスが少し向上します。
次の図は、私が要約した拡張プロセス全体です。
3.ArrayList Iterator
ArrayListとListItrの2つの主要な反復器がありますが、JDK1.8にはArrayListspliteratorも追加されています。それぞれITRとListITRのソースコード分析を学びましょう。
（1）ITR：後方にのみ進むことができます
プライベートクラスITRはIterator <e> {int cursor; // int lastret = -1を返す次の要素のインデックス; //最後の要素のインデックスが返されました。 -1そのような場合は// spedctionmodcountはmodcount int expectsmodcount = modcountのコピーです。 public boolean hasnext（）{return cursor！= size; } @suppresswarnings（ "unchecked"）public e next（）{checkforcomodification（）; //現在の位置を記録int i = cursor; if（i> = size）new nosuchelementexception（）; object [] elementData = arrayList.this.ElementData; if（i> = elementData.length）を新しいconcurrentModificationException（）; //次の要素の位置cursor = i + 1; return（e）elementData [lastret = i]; } // iterator's remodyメソッドを使用しますpublic void remove（）{if（lastret <0）throw new IllegalStateException（）; checkforcomodification（）; {//内側のクラスが外部クラスArrayList.this.remove（lastret）を呼び出す方法に注意してください。 //削除した後、各ポインターの位置を再調整する必要があります= lastret;ラストレット= -1; expectsModCount = modCount; } catch（indexoutofboundsexception ex）{新しいconcurrentModificationException（）; }} final void checkforcomodification（）{if（modcount！= expectsModCount）throw new concurrentModificiationException（）; }}ソースコードから、Itr Iteratorはフォワードイテレーターであることがわかります。これは、アレイリスト内の要素を取得する次の方法を提供します。
CheckForcomodificationは、Java-Collection-Framworkにおける故障エラー検出メカニズムです。マルチスレッド環境で同じセットでの操作により、フェイルファーストメカニズムがトリガーされ、同時モジオ化エクセプトの例外がスローされる場合があります。
ITR Iteratorは、expectsModCount Record ModCountのコピーを定義します。 ArrayListが操作を実行して、追加、削除、クリアメソッドなどの構造を変更すると、ModCountの値が変更されます。
ITRソースコードを介して、次のコードを呼び出してメソッドを削除すると、フェイルファストチェックがトリガーされることがわかります。この時点で、他のスレッドがセットを横断しながらセット構造を変更する操作を実行しているときに例外が発生した場合。
（2）listitr：前方および後方のトラバーサルをサポートします。 ListItrのソースコードを見てみましょう。
プライベートクラスlistitr拡張ITR実装listiterator <e> {listitr（int index）{super（）; cursor = index; } public boolean hasprevious（）{return cursor！= 0; } public int nextindex（）{return cursor; } public int fortion index（）{return cursor -1; } @suppresswarnings（ "unchecked"）public e fortion（）{checkforcomodification（）; // arrayList int i = cursor -1の前の要素の位置-1; if（i <0）を新しいnosuchelementexception（）; object [] elementData = arrayList.this.ElementData; if（i> = elementData.length）を新しいconcurrentModificationException（）; cursor = i; return（e）elementData [lastret = i]; } //セットメソッドがこのiterator public void set（e e）{if（lastret <0）throw new IllegalStateException（）に追加されます。 checkforcomodification（）; try {arraylist.this.set（lastret、e）; } catch（indexoutofboundsexception ex）{新しいconcurrentModificationException（）; }} //このiteratorは、public void add（e e）{checkforcomodification（）; try {int i = cursor; arraylist.this.add（i、e）; //ポインター位置cursor = i + 1に注意してください。ラストレット= -1; expectsModCount = modCount; } catch（indexoutofboundsexception ex）{新しいconcurrentModificationException（）; }}}ListITITRの実装は基本的にITRと同じであり、以前に移動できるメソッドを追加し、メソッドを追加および設定します。
（3）java.util.concurrentのcopyonwritearraylistを使用して、ファーストフェイルの問題を解決します
copyonwritearraylistはスレッドセーフです。詳細については、ADDメソッドソースコードを見てみましょう。
public boolean add（e e）{final reentrantlock lock = this.lock; lock.lock（）; try {object [] elements = getArray（）; int len = Elements.length; object [] newElements = arrays.copyof（elements、len + 1）; newElements [len] = e; SetArray（NewElements）; trueを返します。 }最後に{lock.unlock（）; }} copyonwritearrayListは、書き込みでコピーされた配列リストです。データの書き込みの操作を開始するとき、arrays.copyofは新しい配列であり、読み取り操作に影響しません。
このコストは、記憶を失い、パフォーマンスの問題をもたらすことです。 CopyOnWritearrayListが記載されている場合、コピーオブジェクトがメモリで生成され、元のオブジェクトがまだ存在します。
CopyOnWritearRayListは、データのリアルタイムでの一貫性を保証することはできません。結果の一貫性を保証することのみができます。同時状況でより多くを読み、より多くの書き込み、より少ない状況で書き留めるときのキャッシュなどのシナリオに適しています。
（4）その他のメソッドソースアレイリストのコード：
プライベートメソッドBatchRemove（コレクション<？
プライベートブールバッチレモ（コレクション<？ int r = 0、w = 0; Boolean Modified = false;リスト内の要素を介して{//静かにして、（; r <size; r ++）if（c.contains（elementData [r]）== complement）elementData [w ++] = elementData [r]; }最後に{// Tryで例外が発生した場合、データの一貫性を確保し、次のコピー操作を実行します（r！= size）{System.ArrayCopy（elementData、r、elementData、W、size -r）; w += size -r; } //未使用の要素を清掃し、GCに通知してリサイクルします（w！= size）{// clear gcに（int i = w; i <size; i ++）elementdata [i] = null; modcount += size -w; size = w; Modified = true; }} return modified; }ファイナルによって変更された変数は、後でデータの一貫性を維持するために同じ参照を指します。
この方法では、コレクションCに要素を保持する場合、補数値は真です。 Cの要素を削除する場合、補数値はfalseです。これは、それぞれ保持および除去方法になります。
スワップ：アレイリストの2つの位置を交換します
2。LinkedListソースコード分析（JDK7）
LinkedListはリンクリストです。注文表と比較して、リンクされたリストは、データを保存するために連続メモリユニットを使用する必要はありません。コンテナ構造を変更することによって引き起こされる移動要素の問題を軽減し、シーケンシャルアクセスは比較的効率的です。
1。ノードの定義
JDKのLinkedListは双方向リンクリストであり、各ノードはそれぞれ前のノードと次のノードに関する情報を保存します。その定義は次のとおりです。
プライベート静的クラスノード<e> {e item; node <e> next; node <e> prev; node <e>（node <e> prev、e element、node <e> next）{this.item = element; this.next = next; this.prev = prev; }}2。LinkedListの構築と初期化
メンバー：3つのメンバー変数がLinkedListに維持され、リンクリストのノードの数を記録し、ノードの前身と後継者を記録します
Transient Int Size = 0; Transient Node <e> first; Transient Node <e> last;
コンストラクター：デフォルトのコンストラクターは、空のlinkedListを作成することです
publiclinkedList（）{}または、他のコンテナに基づいて構築すると、後で順序付けられたリンクリストを形成するコンストラクターを書き込みます。
public linkedlist（collection <？extends e> c）{this（）; addall（c）;}ここに少し余分です。ジェネリック修飾子の違いは？スーパーTと拡張Tを拡張します。スーパーTとジェネリックの拡張Tの違いに関するこの記事を参照してください。
3。LinkedListの構造操作
ヘッダー挿入方法：つまり、リンクリストのヘッダーに要素を挿入します
private void linkfirst（e e）{final node <e> f = first;最終ノード<e> newNode = new Node <>（null、e、f）; first = newNode; //それが空のリンクリストであるかどうかを判断します（f == null）last = newNode; else f.prev = newNode;サイズ++; modcount ++; }テール挿入方法：つまり、リンクリストの最後に要素を挿入します
void linklast（e e）{final node <e> l = last;最終ノード<e> newNode = new Node <>（l、e、null）; last = newNode; if（l == null）first = newNode; else l.next = newNode;サイズ++; modcount ++; }現在のノードに挿入する前に：現在のノードのフロントドライブを見つけます
void linkbefored（e e、node <e> suck）{//ノードが空でないかどうかを判断します。 final node <e> newNode = new Node <>（pred、e、succ）; coucc.prev = newnode; //現在のノードが最初のノードであるかどうかを決定します（pred == null）first = newNode; else pred.next = newNode;サイズ++; modcount ++; }ヘッダー削除方法：リンクリストの最初のノードを削除する
Private E UnlinkFirst（node <e> f）{// assert f == first && f！= null;最終e要素= f.item;最終ノード<e> next = f.next; f.item = null; f.next = null; // gc first = next; if（next == null）last = null; else next.prev = null;サイズ - ; modcount ++;返品要素。 }テール削除方法：リンクリストの最後のノードを削除します
Private E Unlinklast（node <e> l）{// l == last and l！= null final e element = l.itemを確認してください。最終ノード<e> prev = l.prev; l.item = null; l.prev = null; // gc last = prevをヘルプします。 if（prev == null）first = null; else prev.next = null;サイズ - ; modcount ++;返品要素。 }4.リストインターフェイスとDeque間の一貫性を維持します
リストインターフェイスを使用すると、サブスクリプトを使用してコンテナへのランダムアクセスを実装することができ、このような配列へのランダムアクセスを簡単に実装できます。リンクされたリストの場合、JDKはリンクリストのノードのカウントを論理的に使用して、ランダムアクセスの実装を提供します
node <e> node（int index）{//インデックスの正しさを確保するif（index <（size >> 1））{node <e> x = first; for（int i = 0; i <index; i ++）x = x.next; xを返します。 } else {node <e> x = last; for（int i = size -1; i> index; i-）x = x.prev; xを返します。 }}インデックスは前半のカウントで、最初から検索します。インデックスは後半のカウントに属し、最後から検索します。双方向リンクリストの特性を最大限に活用します。
したがって、追加（int index、t t）、get（int）、set（int）、およびその他のメソッドを簡単に実装できます。
LinkedListは、Dequeインターフェイスを実装します。つまり、LinkedListは、両端のキューコンテナの方法を実装します。 APIの要約をいくつか紹介します。
5。LinkedListTraversal
LinkedListは双方向のリンクリストであるため、自然に前後に移動できます。 ArrayListと同様に、LinkedListは、マルチスレッドコンテナ操作に関しても障害のある問題もあります。
Fail-Fastの問題は前の記事で説明されているので、ここでは説明しません。
Iteratorsに関しては、LinkedListにはListiteratorの双方向のイテレーターと、Descendingiteratorの逆イテレータがあります。すべてがとてもシンプルです。ソースコードは分析されません
要素を通過すると、ランダムアクセスのコストが比較的高くなります。
3。LinkedList、ArrayList、Vector Summary
1。LinkedListおよびArrayList
ArrayListは、動的配列に基づいてデータ構造を実装し、LinkedListはリンクリストに基づいたデータ構造に基づいています。
LinkedListがポインターを移動するため、ランダムアクセスを取得および設定するために、ArrayListはLinkedListよりも優れています。
ArrayListがデータを移動する必要があるため、新規および削除操作の追加および削除の場合、LinedListはより良い利点があります。これは実際の状況に依存します。単一のデータのみが挿入または削除されている場合、ArrayListの速度はLinkedListの速度よりも優れています。ただし、データがバッチにランダムに挿入されている場合、LinkedListの速度はArrayListの速度よりもはるかに優れています。 ArrayListがデータを挿入するたびに、挿入点とすべてのデータをその後移動する必要があります。
2。アレイリストとベクトル
ベクトルはスレッド同期であるため、スレッドセーフでもありますが、アレイリストはスレッドアジンであり、安全ではありません。スレッドの安全係数が考慮されていない場合、アレイリストは一般により効率的です。
セット内の要素の数が現在のセット配列の長さよりも大きい場合、ベクトル成長率は現在の配列の長さの100％であり、アレイリストの成長率は現在のアレイ長の50％です。セット内に比較的大量のデータを持つデータを使用する場合、Vectorを使用すると特定の利点があります。
指定された場所でデータを探す場合、ベクトルとアレイリストが使用する時間は同じで、両方の0（1）であり、現時点ではベクターとアレイリストを使用できます。指定された場所でデータを移動するのに費やした時間が0（ni）nである場合、これは合計長さである場合は、リンクリストを使用することを検討する必要があります。特定の場所でデータを移動するには0（1）がかかり、指定された場所でデータを照会するのに費やされる時間は0（i）です。
ArrayListとVectorは、データを保存するための配列を使用します。この配列の要素の数は、実際の保存データよりも大きく、要素を追加および挿入します。どちらも直接シリアル番号インデックス要素を許可します。ただし、データの挿入は、配列要素やその他のメモリ操作を移動するように設計する必要があるため、インデックスデータはデータの挿入が速く、遅くなります。ベクターは同期された方法（スレッドセーフ）を使用するため、パフォーマンスはアレイリストよりも悪いです。 LinkedListは、双方向リンクリストを使用してデータを保存します。シリアル番号に従ってデータをインデックス作成するには、前方または後方の移動が必要ですが、データを挿入する場合、このアイテムのフロントアイテムのみが記録されるため、数度の挿入がより速くなります！