単一と二重のリストの両方からランダムノードを削除する

Question

二重で単独でリンクされたリストの両方からノードを削除するためのロジックを思いつくのに苦労しています。私はヘルプからオンラインで見ましたが、それの簡単な例を見つけることができませんでした。これが私が持っているものです：

---

二重にリンクされた削除。 dCurrent 削除するノードです。

if (dCurrent == dHead){
   dHead = dCurrent->next;
   dHead->prev = NULL;
}
else if(dCurrent == dTail){
   dTail = dCurrent->prev;
   dTail->next = NULL;
}
else{
   dCurrent->next->prev = dCurrent->prev;
   dCurrent->prev->next = dCurrent->next;   
}

---

これが私が単独でリンクしたリストに持っているものです。また、 sCurrent 削除するノードです。と sPrev = sCurrent->prev.

if(sPrev == NULL){
   sHead = sCurrent->next;
}
else{
   sPrev->next = sCurrent->next;
}

---

問題は、両方のリストからランダムノードのコレクションを削除した後、二重にリンクされたリストがヘッドからテールまで正しく表示されますが、ヘッドからテールではなく表示されることです。単独でリンクされたリストも正しく表示されません。

Answer 1

あなたの二重にリンクされたリストのロジックは私にはうまく見えます。私の唯一の懸念は、その場合です dCurrent リスト内の唯一の要素です。これは次のとおりです。

if (dCurrent == dHead){
    dHead = dCurrent->next;
    dHead->prev = NULL;
}

ほとんどの場合、ヌルポインターを参照しようとします。 （それはあなたがあなたのリストをどのようにデザインするかに依存します。しかし、典型的なデザインでは、 dCurrent 次に、唯一のノードです dCurrent->next は NULL.)

「sprev = scurrent-> prev」という仮定を考えると、抽象的に、あなたの単独でリンクされたリストのロジックも私にはうまく見えます。しかし、私はその仮定がどのように正しいか理解していません。それが単独でリンクされたリストの場合、そうです sCurrent そうではありません 持ってる a prev ポインター。

Answer 2

私が見ることができる唯一の問題は、ヘッドまたはテールがnullに更新されるシナリオでは、コードが適切に機能しないことです。

基本的に唯一のノードを削除すると、dheadはnullを指しますので、次のようなステートメントに「警備員」を置く必要があります

dHead->prev = NULL;

そのようです

if (dHead != NULL) {
  dHead->prev = NULL;
}

非常に多くの条件を「回避」する1つの方法は、nil（タイプではない）要素を割り当てることです。

nilは、nullを置き換える「ノード」です。これは「リストのデータ部分から外れている」ことを表します。そのため、次は常にnil（循環参照）であり、以前は常にnil（循環参照）です。そのような場合、NILがリストの外部でアクセスできないこと、およびそのhead-> prev == nilとtail-> next == nilを保証します。そうすれば、あなたは多くを避けることができます if (tail != null) { ... } タイプステートメント。

そのような構成要素の下では、空のリストは head == NIL && tail == NIL. 。これにより、の数が劇的に減少します if (something == null) ステートメントですが、ヘッドがゼロの場合（何かを削除した後）、一貫性のために尾をゼロに設定する必要がある場合、考慮すべき声明が1つあります。