1つのリンクされたリストO（1）を削除するのはなぜですか？

Question

wikipedia articleのように、1つのリンクリストの最後にある削除がO（1）時間になる理由を私は理解していません。

単一リンクリストは、ノードから構成されます。ノードには、ある種のデータと、次のノードへの参照が含まれています。リンクされたリスト内の最後のノードの参照はnullです。

-------------- --------------   -------------- 
| data | ref | -> | data | ref | -> ... -> | data | ref | 
-------------- --------------   -------------- 

実際、O（1）の最後のノードを削除できます。しかし、その場合は、削除された最後のノードへの参照がまだ含まれているため、最後のノード（以前のもの）の参照をnullに設定しないでください。だから私は彼らが実行時間の分析でそれを無視しているのだろうかと思っていたのですか？それとも、参照を変更しなくてもいいということは合意されていますか？

もし無視されなければ、私は削除がO（n）であると主張するだろうから。新しく最後のノードに到達するには、リスト全体を反復処理し、その参照もnullに設定する必要があるためです。ダブルリンクされたリストの中では、本当にO（1）になります。

-edit- 多分、この観点から、より多くの透明性が得られます。しかし、ノード自体を正しく削除し、以前の参照をnullに設定することで、「ノードの削除」が表示されます。

Answer 1

O（1）の単一リンクリストの最後のエントリを削除することができるというウィキペディアの記事にはわかりませんほとんどの場合、その情報は間違っています。リンクされたリスト内の個々のノードがあれば、そのノードの周りでリストを再配線することによって、O（1）時間後にノードを削除することは常に可能です。したがって、リンク先リストの最後から2番目のノードへのポインタが与えられていれば、リストの最後の要素をO（1）の時間に削除できます。

しかし、ヘッドポインタ以外のリストに余分なポインタがない場合、リストの最後までスキャンしないとリストの最後の要素を削除できませんでした。これにはΘ（n ）時間が必要です。最初のポインタを変更せずに最後のノードを削除するだけでは、非常に悪い考えです。これを行う場合、既存のリストには割り当てられていないオブジェクトへのポインタが含まれるためです。

さらに一般的には、挿入または削除するノードの直前のノードへのポインタがあると仮定すると、単一リンクリストで挿入または削除を行うコストはO（1）です。ただし、そのノードを見つけるには余分な作業（最大Θ（n）まで）を行う必要があります。

希望すると便利です。

Answer 2

の追加/削除ノードのANYの場所はO（1）です。コードはノードを追加/削除するために、固定コスト（わずかなポインタの計算とmalloc /解放）で再生されます。この算術的コストは、特定の場合に固定されています。

ただし、目的のノードに到達する（索引付けする）コストはO（n）です。

この記事では、途中で追加するコストが開始/終了で追加するコストと異なることを示すために、複数のサブカテゴリ（中、初め、終わりに追加）の単なる追加/削除を列挙しています）。

Answer 3

たとえば、最後に要素を指すポインタ（「2番目から最後）」と削除する場合は、次のようにします。 1.この「second from end」要素を削除*します。 2.これをNULLの隣の*から2番目に設定する

Answer 4

O（1）は単に「一定コスト」を意味します。 1つの操作を意味するものではありません。これは、他のパラメータの変更（リストサイズなど）に関係なく、Cが固定された「最大でC」の演算を意味します。実際には、ときには大物の紛らわしい世界：O（1）== O（22）。

対照的に、コストはリストのサイズ（n）によって変化するため、リスト全体を削除するとO（n）コストが発生します。

Answer 5

ぶら下がっているノードを修正するコストが含まれている場合は、末尾にもセンチネルノードを使用してO（1）で実行できます（このページにも記載されています）。あなたの「空」のリストには、いくつかのもの

Head -> 1 -> 2 -> 3 -> [Sentinel] 

を追加し、単一のセンチネル

Head -> [Sentinel] 

で始まる

さて3無効としてあったノードをマークすることにより、（3）尾を削除し、古いセンチネルへのリンクを削除し、そのメモリを解放する：

Head -> 1 -> 2 -> 3 -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] 

Answer 6

今後の参考として、いくつかの研究の後、私は、この質問に対する回答として提出された議論はどれも適切ではないことを発見しました。その答えは、スタックの先頭が（テールではなく）リンクされたリストの先頭になるように単純に決定することです。これにより、プッシュルーチンにわずかな変更が加えられますが、ポップとプッシュの両方がo（1）のままになります。