今日のインタビューで、私は質問を受けました。
リストの逆順と順方向と逆方向のトラバーサルの両方に答える以外に、インタビュアーが強調し続けた「基本的な」何かがありました。私はあきらめ、もちろんインタビューの後、少し調査を行いました。挿入と削除は、単方向リストよりも二重方向リストの方が効率的であるようです。変更するにはより多くの参照が必要であることは明らかであるため、二重にリンクされたリストの場合にどのように効率化できるかはよくわかりません。背後にある秘密を説明できる人はいますか? 私は正直なところ、かなりの調査を行いましたが、二重リンクリストには O(n) 検索がまだ必要であるという主な問題を理解できませんでした。
挿入は、常に先頭または既知の要素の後に挿入することに満足している限り、単一リンクリストでの作業は明らかに少なくなります。(つまり、既知の要素の前に挿入することはできませんが、以下を参照してください。)
一方、削除は、削除する要素の前に要素を知る必要があるため、より注意が必要です。
これを行う 1 つの方法は、削除 API を、削除する要素の先行要素と連携させることです。これは、新しい要素の前身となる要素を取得する挿入 API を反映していますが、あまり便利ではなく、文書化するのも困難です。通常は可能ですが。一般的に言えば、リストをトラバースすることでリスト内の要素に到達します。
もちろん、リストを最初から検索して、削除する要素を見つけて、その前の要素が何であるかを知ることもできます。これは、delete API にリストの先頭が含まれていることを前提としていますが、これも不便です。また、検索は非常に遅いです。
ほとんど誰も使用しないが、実際には非常に効果的な方法は、単一リンク リスト反復子を、反復子の現在のターゲットの前の要素へのポインターになるように定義することです。これは単純で、要素への直接ポインターを使用するよりも 1 つの間接参照のみが遅く、挿入と削除の両方が高速になります。欠点は、要素を削除すると、要素をリストするための他のイテレータが無効になる可能性があることです。これは煩わしいことです。(削除される要素へのイテレータを無効にするわけではありません。これは、一部の要素を削除するトラバーサルには適していますが、それほど補償にはなりません。)
おそらくデータ構造が不変であるため、削除が重要でない場合、単一リンクリストは別の非常に便利なプロパティを提供します: それらは構造の共有を可能にします。一重連結リストは、幸いにも複数の頭の尾になることができますが、これは二重連結リストでは不可能です。このため、単方向リストは伝統的に、関数型言語の単純なデータ構造として選ばれてきました。
二重連結リストに関する私の考えは次のとおりです。
両端にすぐにアクセス\挿入できます。
キューとスタックとして同時に機能できます。
ノードの削除には、追加のポインターは必要ありません。
すでに両端でアクセスできるため、Hill-Climb トラバーサルを適用できます。
数値を保存していて、リストがソートされている場合、中央値のポインター/変数を保持でき、統計的アプローチを使用して検索操作を最適化できます。
リンク リスト内の要素を削除する場合は、前の要素を次の要素にリンクする必要があります。双方向リンク リストでは、両方の要素へのリンクがあるため、両方の要素にすぐにアクセスできます。
これは、削除する必要がある要素へのポインターが既にあり、検索が含まれていないことを前提としています。
「リストの逆順と順方向と逆方向の両方のトラバーサルに答える以外に、「基本的な」何かがありました。
誰も言及していないようです。二重リンクリストでは、削除された要素へのポインターを持つだけで、削除された要素を再挿入できます。Knuth の Dancing Links の論文を参照してください。それはかなり基本的なことだと思います。