私はドイツのコンピュータサイエンスの学生です。私の教授は、以下の質問を使用して考えました。O（1）の複雑さを持つ単一のリンクリストの1つの要素を削除するアルゴリズム
'（最後のノードではない）単一リンクリストのノードへの参照が与えられています。整合性を維持しながらO（1）の複雑さを持つリストからこの要素を削除するアルゴリズムを提供する '。
私はこれについて考えましたが、そのようなアルゴリズムはないと確信しています。 1つのリンクされたリストであるため、削除するノードに到達するまで、リスト内のすべてのノードをループする必要があります。削除する前にノードのnext-Pointerを変更する必要があるからです。それはO（n）の複雑さをもたらすでしょう。
何か不足していますか？
ノードが可変であるかどうかによって異なります。あなたはノードと好きなものを行うことができれば
ありはは、それを行う方法です：
toDelete.value = toDelete.next.value
toDelete.next = toDelete.next.next
toDeleteからのすべての情報は今古いtoDelete.next内の情報によって、上書きされました。 （プラットフォームに応じて、古いtoDelete.nextを解放する必要があるかもしれません - これは一時的な参照を保持することを意味します。 。）
それはしかし、リスト内の最後のノードでこのないに依存しているん...
を私はそれを離れて与えることなく、それを示唆する方法をうまくしようとしたが、それはちょっと難しいです。
正確にノードを削除すると考えられていますが、現在の次のノードのデータをコピーして、次のノードを削除することができない：
// pseudocode:
this.data = next.data;
var temp = this.next;
this.next = next.next;
delete temp;
はい。前のリストの次のポインタへのポインタを反復ポインタとして保持します。ノードがメモリ内の基本的な構造がある場合
walk = &head;
while (!match(*walk)) {
walk = &walk[0]->next;
if (!*walk) return ;
}
*walk = walk[0]->next;
それはO（1）ではありません。 –
取り外し部分はこちらです。 リンクリストの更新イテレータは、常に次のノードへのポインタへのポインタを使用する必要があります。 – Joshua
、あなたが削除したノードのメモリ位置に「次」のノードの内容をコピーし、「次」のノードがために使用メモリを解放することができます。
削除するノードへのポインタがあるとします。次の値を現在のノードに複製します。現在のポインタを、次に指し示すノードに置き換えます。
リンクではなくデータを移動します。 このスレッドを見る： Deleting a middle node from a single linked list when pointer to the previous node is not available
ああ、それを得ました。ありがとう:) –
ジョーンが説明したように、これがうまくいくためにはノード構造をプライベートにする必要があります。ノード自体への参照を保持する必要はありません。さもなければ、コンシューマには古いtoDelete.nextオブジェクトへの無効な参照が残ってしまいます（たとえば、C++でノード構造を削除した場合や、最高で無効なノードオブジェクトの場合）。 –
これは本当に単独でリンクされたリストから要素を削除するための 'アルゴリズム'ではありませんか？これは、リストから要素を削除する標準的な方法です。 – Dinuk