私はそのような質問を受け、私自身のことわざを持っていますが、短所と長所について何を言うべきか本当にわかりませんか? マイクロソフトは、候補者の 1 人にこの質問をしました。
単方向リストでは、一方向に進むことができます。一方、二重連結リストには、次と前の双方向の方向があります。
これは、Singly LinkedList と Doublely LinkedLists を描画する良い図です。
しかし、これらの項目の長所と短所をより整然と説明するにはどうすればよいでしょうか。
質問する
35557 次
6 に答える
27
この質問はすでに回答されていますが、私はどういうわけか回答に満足していません (不快感を与えるものではありません)。
何を使用するか - 単方向または二重にリンクされたリストは、目的とシステムの制限 (存在する場合) によって異なります。
片方向リスト:
長所：実装が簡単で、次のノードを削除/挿入する必要があると仮定すると、ストレージに必要なメモリが比較的少なくて済みます-削除/挿入はより高速です。
短所: 逆に反復することはできません。リストのヘッド ノードへのハンドルを維持する必要があります。それ以外の場合、リストはメモリ内で失われます。前のノードを削除するか、前のノードに挿入する場合、それらの操作を実行できるようにするには、リストを先頭から前のノードまでトラバースする必要があります – O(N) 時間。
--したがって、これはメモリが少なく、主な目的が要素の検索ではなく挿入/削除である場合に使用する必要があります。
双方向リスト:
長所: 順方向だけでなく逆方向にも反復できます。前のノードを削除する必要がある場合、「.previous」ポインタから削除するノードを見つけることができるため、先頭ノードからトラバースする必要はありません。
短所: 実装が比較的複雑で、ストレージ用により多くのメモリが必要です (ノードごとに 1 つの '.previous' ポインター)。挿入と削除は比較的時間がかかります (隣接ノードへの「.previous」ポインターの割り当て/再割り当て)
--これは、メモリに制限がないか最小限の制限があり、主な目的が要素の検索である場合に使用する必要があります。
他にも長所と短所がある場合は、お気軽に追加して、コメントに返信してください。ありがとう！
于 2012-09-12T12:02:24.617 に答える
25
私はそのような質問を受け、私自身のことわざを持っていますが、短所と長所について何を言うべきか本当にわかりませんか?
それはすべて使用法に帰着します。ここにはトレードオフがあります。
単一リンクリストは、実装の点でより単純であり、通常、前方参照メンバーを所定の位置に保持するだけでよいため、メモリ要件が小さくなります。
二重にリンクされたリストは、特に逆方向に反復する必要がある場合 (単一のリンクされたリストでは非常に非効率的です)、より効率的な反復と、特定のノードのより効率的な削除を行います。
そうは言っても、このタグ付き.NETがあるため、二重リンクリストには、LinkedList<T>クラスの形式でフレームワークに直接あるという利点もあります。これには、独自のコレクション クラスを実装、テスト、および保守する必要がないという大きな利点があります。
于 2012-05-22T19:31:38.760 に答える
12
単一リンクリストはノードあたりのメモリ使用量が少なくなりますが (1 つのポインターと 2 つのポインター)、その削除操作は、削除O(N)するノードへのポインターしかない場合ですO(1)。の単一リンク リストから削除できるあまり知られていないトリックがありますがO(1)、それが機能するにはリストが循環している必要があります ( の内容をnext現在のリストに移動し、 を削除しnextます)。
二重リンクリストは、単一リンクリストが機能しない場所 (両端キュー) で使用できますが、「ハウスキーピング」が少し必要になり、結果として挿入の効率がわずかに低下します。
于 2012-05-22T19:33:04.597 に答える
3
二重連結リストの利点: 双方向にトラバースできる
単一のリンクされたリストの利点: 更新/挿入/削除で行われる家事が少なくなり、メモリ使用量が少なくなります。
于 2012-05-22T19:32:16.800 に答える
2
まぁ、状況次第ですね。特定の要素から前の要素と次の要素の両方をすばやく取得できるようにする必要がある場合は、双方向にリンクされたリストが最適です。
特定の要素から次の要素を取得するだけでよい場合は、単方向リストで十分です。
于 2012-05-22T19:32:28.883 に答える