前の記事では、ArrayListの基礎となる実装を分析し、ArrayListの基礎となる実装がアレイに基づいていることを知っていたため、挿入と削除のゆっくりしている間、高速検索と変更の特性があります。この記事で導入されたLinkedListは、リストインターフェイスのもう1つの実装です。その基礎となる層は、双方向リンクリストに基づいています。したがって、検索と変更が遅い間、迅速な挿入と削除の特性があります。さらに、キューとスタックの機能は、双方向リンクリストの操作を通じて実現できます。 LinkedListの根底にある構造を下の図に示します。
fはヘッドノード参照を表し、lはテールノード参照を表し、リンクリストの各ノードには3つの要素があります。つまり、フォワードノード参照（P）、ノード要素値（e）、および後続のノード参照（n）です。ノードはインナークラスノードで表されます。内部構造を見てみましょう。
//ノード内部クラスプライベート静的クラスノード<e> {e item; //要素ノード<e> next; //次のノードノード<e> prev; //前のノードノード（node <e> prev、e element、node <e> next）{this.item = element; this.next = next; this.prev = prev; }}内部クラスのノードは実際には非常にシンプルで、メンバー変数は3つだけのコンストラクターだけです。アイテムはノードの値を表し、次は次のノードへの参照であり、前のノードへの参照です。これらの3つの値は、コンストラクターに渡されます。次に、LinkedListのメンバー変数とコンストラクターを見てみましょう。
//設定要素の数は翻訳されますint size = 0; //ヘッダーノード参照transientノード<e>最初; addall（c）;}
LinkedListは、ヘッダーノードへの参照とテールノードへの参照を保持します。 2つのコンストラクターがあり、1つはパラメーターのないコンストラクター、もう1つは外部コレクションに渡されたコンストラクターです。 ArrayListとは異なり、LinkedListは初期サイズコンストラクターを指定しません。追加、削除、変更、検索の方法を確認してください。
// public boolean add（e e）{// linklast（e）を追加する（e e）; true;} // public void add（int index、e element）{checkpositionindex（index）; if（index == size）{// linklast（element）; } else {// linkbefore（element、node（index））; }} // delete（give index）public e remove（int index）{//添え字が法的CheckElementIndex（index）であるかどうかを確認します。 return link（node（index））;} // delete（指定要素）public boolean remove（object o）{if（o == null）{for（node <e> x = first; x！= null; x = x.next）{if（x.item == null）{linnink（x）; trueを返します。 }}} else {// tranquility link for（node <e> x = first; x！= null; x = x.next）{if（o.equals（x.item））{// delete link（x）; trueを返します。 }}} return false;} // public e set（int index、e element）{// subscriptがlegual checkelementindex（index）であるかどうかを確認します。 //指定されたsubscript node <e> x = node（index）のノード参照を取得します。 //指定された添え字node e oldval = x.itemの値を取得します。 //ノード要素を新しい値x.item = elementに設定します。 //前の値を返すoldval;} // public e get（int index）{// subscriptがlegual checkelementindex（index）であるかどうかを確認します。 //指定されたsubscript returnノード（index）.item;}のノードの値を返します。}LinkedListに要素を追加する方法は、主に2つのメソッドLinklastとLinkbeBeforeを呼び出すことです。 Linklastメソッドは、リンクリストの背後にある要素をリンクすることであり、LinkbeForeメソッドは、リンクリストの中央に要素を挿入することです。 LinkedListの削除方法は、Unlinkメソッドを呼び出すことにより、リンクリストから要素を削除します。リンクリストの挿入操作と削除操作のコアコードを見てみましょう。
//指定されたノードvoid linkbebefore（e e、node <e> couck）にリンクする前に{//指定されたノード最終ノード<e> pred = coud.prevの前のノード参照を取得します。 //新しいノードを作成すると、新しいノードの前のノード参照が指定ノードの前のノードを指します//指定されたノードの前のノード参照を新しいノードcecc.prev = newNodeに向けます。 //指定されたノードの前のノードが空の場合、指定されたノードがヘッダーノードである場合を意味します（pred == null）{//ヘッダーノードの参照を新しいノードfirst = newNode; } else {//それ以外の場合は、新しいノードpred.next = newNodeへの次のノード参照をポイントします。 } // SET要素の数を1つのサイズ++に追加します。 //変更の数を1つのmodcount ++; } //指定されたノードe lonink（node <e> x）{//指定されたノード最終e要素= x.itemの要素を取得します。 //指定されたノード最終ノード<e> next = x.nextの次のノードへの参照を取得します。 //指定されたノード最終ノードの前のノードへの参照を取得<e> prev = x.prev; //指定されたノードの前のノードが空の場合、説明：指定されたノードはヘッダーノードです（prev == null）{//ヘッダーノード参照を指定ノードの次のノードに指しますfirst = next; } else {//前のノードの後継ノードを参照してください。 //指定されたノードの前のノードを参照x.prev = null; } //指定されたノードの次のノードが空の場合、指定されたノードがテールノードであることを意味します。 } else {//指定されたノードの前のノードを指す次のノードのフォワードノードを参照してくださいnext.prev = prev; x.next = null; } //特定のノードx.item = nullの要素を空にします。 //サイズごとに設定要素の数を減算します。 // modcount ++を追加; return element;} Linkbeboreとlinkは、ノードをリンクしてノードをアンインストールする代表的な操作です。両端でノードをリンクおよびアンインストールする他の方法は類似しているため、LinkbeBoreとLink Linkメソッドに焦点を当てます。
linkbeforeメソッドのプロセス図：
Unlinkメソッドのプロセス図：
上記の図を通して、リンクリストの挿入操作と削除操作の時間の複雑さはO（1）であり、リンクリストの検索および変更操作は、リンクリストを通過して要素を見つける必要があります。どちらの操作と呼ばれ、要素を見つけてサブスクリプトを介して要素を見つける方法を確認するためのnode（int index）メソッドと呼ばれます。
// node node <e> node（int index）{//インデックスがリンクリストの前半にある場合、[index <（size >> 1））{node <e> x = first; for（int i = 0; i <index; i ++）{x = x.next; } xを返します。 } else {//インデックスがリンクリストの後半にある場合、end node <e> x = lastから確認してください。 for（int i = size -1; i> index; i-）{x = x.prev; } xを返します。 }}サブスクリプトを配置するとき、最初にリンクリストの上半分か下半分にあるかを決定します。上半分にある場合は、最初から開始し、下半分の場合は最後から始めます。したがって、添え字の検索と変更の操作の時間の複雑さはO（n/2）です。双方向リンクリストの操作により、単一項目キュー、双方向キュー、スタックの関数も実現できます。
一元配置キュー操作：
//ヘッダーノードpublic e peek（）{final node <e> f = first; return（f == null）？ null：f.item;} //ヘッダーノードpublic e element（）{return getFirst（）;} //ヘッダーノードパブリックEポートをポップアップします{final node <e> f = first; return（f == null）？ null：Unlinkfirst（f）;} //ヘッダーノードを削除しますpublic e remove（）{return removefirst（）;} //キューパブリックブールンオファーの最後にノードを追加（e e）{return add（e）;}双方向キュー操作：
// public boolean offerfirst（e e）{addfirst（e）; true;} // public boolean offerlast（e e）{addlast（e）; return true;} //ヘッダーノードpublic e peekfirst（）{final node <e> f = first; return（f == null）？ null：f.item; } //テールノードパブリックe peeklast（）を取得{final node <e> l = last; return（l == null）？ null：l.item;}スタック操作：
//スタックパブリックボイドプッシュ（e e）{addfirst（e）;} //スタックパブリックe pop（）{return removefirst（）;}一方向のキュー、双方向キュー、スタックであろうと、それらは実際にリンクリストのヘッドとテールノードで動作します。それらの実装は、addfirst（）、addlast（）、removefirst（）、およびremovelast（）の4つの方法に基づいています。それらの操作は、LinkbeBefore（）およびUnlink（）に似ています。ただし、1つはリンクリストの両端で動作し、もう1つはリンクリストの中央で動作することです。これらの4つの方法は、linkbeforefore（）およびlonlink（）メソッドの特別なケースであると言えます。したがって、内部実装を理解することは難しくないため、ここでは紹介しません。この時点で、LinkedListの分析は終了しようとしています。テキスト全体の重要なポイントを要約します。
1。LinkedListは、双方向リンクリストに基づいて実装されています。追加、削除、修正、検索方法、またはキューとスタックの実装であろうと、操作ノードを介して実装できます。
2。LinkedListは、リンクされたリスト操作に基づいて、要素の追加とともにコレクションの容量が自動的に増加するため、事前に容量を指定する必要はありません。
3.LinkedListが削除された後にコレクションが占めるメモリが自動的に削減され、ArrayListのようなTrimTosize（）メソッドを呼び出す必要はありません
4. LinkedListのすべての方法は同期されていないため、スレッドセーフではなく、マルチスレッド環境では避ける必要があります。
5.上記の分析はJDK1.7に基づいており、他のバージョンにはいくつかの違いがあるため、一般化することはできません。
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。