私は昨日インタビューを受けました。それは、インタビュアーが二重リンクリストでは、挿入操作で影響を受けるポインタはいくつですか？
だった尋ねた「挿入操作に影響を受けることになりますどのように多くのポインタ二重にリンクされたリストには、？」
をするので、彼が特に求められていなかったことを、まず最初に始めました挿入する場所は、DLLにいくつのノードがあるかによって異なります。
影響を受ける合計ポインタは、リストが空であるかどうか、挿入が行われる場所によって異なります。
しかし、彼は私が彼に確信しているかどうかは何も言わなかった。
私は正しいか、多分何かを見逃しましたか？
答えは、新しいノードをリストの中央に挿入するか（2つのノードで囲まれる）、リストの先頭または末尾に挿入するかによって異なります。リストの中央に挿入するため
、次のように新しいノードにスプライスする：
A --- B
^^ splice M in here
A.next = M
M.prev = A
B.prev = M
M.next = B
従って4ポインタの割り当てが行われます。ただし、挿入が頭や尾にある場合は、ポインタの割り当ては2つだけ必要です。
TAIL (insert M afterward)
TAIL.next = M
M.prev = TAIL
だから、結局のところ、ノードの総数に左右されませんよね？ – Barry
あなたが行うポインタの計算量は、ノードの数に依存しません。 _However_これは、リンクされたリストに挿入するための実行時間がリストのサイズに依存しないことを示すものではありません。むしろ、ソートされたリストの場合、実際の挿入操作を開始する前に、挿入ポイントを見つけるために 'O（N * lgN）'時間がかかります。 –
なぜO（N * log N）ですか？ソートされた*配列*の場合、ソートされた* list *の場合、バイナリ検索でO（log N）で実行できます。最悪の場合は、すべての要素を調べる必要があります）。私は最悪の場合にすべての要素以上を見なければならない理由は明確ではありません。 –
あなたの質問は不明です。正確に*影響を受けるのは？読む？書きましたか？逆参照？そして、正確に*「挿入」は何を意味しますか？それは挿入する場所を検索することを含むか、または*実際の挿入操作のみを参照するか？ –
@JörgWMittag私は「影響を受ける」とは、挿入すると、次に新しいノードにポインタを変更する必要があることを意味します。 – Barry