22

ウィキペディアの記事にあるように、単一のリンクされたリストの最後で削除するのに O(1) 時間かかる理由がよくわかりません。

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

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

O(1) の最後のノードを削除できます。ただし、その場合、削除された最後のノードへの参照がまだ含まれているため、新しい最後のノード (前のノード) の参照を null に設定しません。だから私は疑問に思っていました、彼らは実行時間分析でそれを無視していますか? それとも、参照が何も指していないだけなので、それを変更する必要はないと考えられていますか?

無視されなければ、削除は O(n) であると主張するからです。リスト全体を反復処理して、新しく最後のノードに到達し、その参照も null に設定する必要があるためです。二重リンクリストでのみ、実際には O(1) になります。

-編集- たぶん、この観点はもう少し明確になります。しかし、「ノードの削除」は、ノード自体を正常に削除し、以前の参照をnullに設定していると思います。

4

8 に答える 8

42

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

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

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

お役に立てれば！

于 2012-12-27T01:11:22.933 に答える
8

任意の場所での任意のノードの追加/削除は O(1) です。ノードを追加/削除するために、コードは固定コスト (いくつかのポインター計算と malloc/frees) で遊ぶだけです。この算術コストは、特定のケースに対して固定されています。

ただし、目的のノードに到達する (インデックスを作成する) ためのコストは O(n) です。

この記事では、追加/削除を複数のサブカテゴリ (途中で追加、最初に追加、最後に追加) にリストしているだけで、途中で追加するコストは最初/最後に追加するコストとは異なることを示しています (ただし、それぞれのコストは依然として固定されています)。

于 2012-12-27T01:08:38.587 に答える
0

O(1) は単に「一定のコスト」を意味します。1操作という意味ではありません。これは、他のパラメーターの変更 (リストサイズなど) に関係なく、C が固定された「最大 C」操作を意味します。実際、大王の時々混乱する世界では、O(1) == O(22) です。

対照的に、リスト全体の削除には O(n) のコストがかかります。これは、コストがリストのサイズ (n) によって変化するためです。

于 2012-12-27T01:11:35.603 に答える
0

今後の参考のために、いくつかの調査の結果、この質問への回答で提供された議論はどれも関連性がないことがわかりました. 答えは、スタックの一番上を (テールではなく) リンクされたリストの先頭にすることを単純に決定することです。これにより、プッシュ ルーチンがわずかに変更されますが、ポップとプッシュは両方とも o(1) のままです。

于 2016-06-01T04:49:01.693 に答える
0

ぶら下がっているノードを修正するコストを含めている場合でも、最後にセンチネル ノードを使用して O(1) で実行できます (そのページにも説明があります)。

あなたの「空の」リストは、単一の歩哨から始まります

Head -> [Sentinel]

いくつかのものを追加

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

3 だったノードを無効としてマークし、古いセンチネルへのリンクを削除して、メモリを解放することにより、テール (3) を削除します。

Head -> 1 -> 2 -> 3 -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel]
于 2012-12-31T09:21:54.613 に答える
-1

たとえば、最後 (「末尾から 2 番目」) の前の要素へのポインターを保持し、削除する場合: 1. この「末尾から 2 番目」の要素の *next を削除します。2.この「最後から2番目」を* NULLの隣に設定します

于 2012-12-27T01:10:30.330 に答える