Rimozione di un nodo a caso da entrambe le liste singly- e doppiamente-linked

Question

Sto avendo un momento difficile venire con la logica per la rimozione di qualche nodo sia da una lista doppiamente e concatenata. Ho guardato online da aiuto, ma non riuscivo a trovare un semplice esempio di esso. Ecco quello che ho:

---

eliminazione Doppiamente collegato. dCurrent è il nodo che vogliamo eliminare.

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;   
}

---

Ecco quello che ho per la lista concatenata. Ancora una volta, sCurrent è il nodo da eliminare. e sPrev = sCurrent->prev.

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

---

Il problema è che dopo elimina un insieme di nodi casuali da entrambe le liste, l'elenco mostra doppiamente collegate correttamente dalla testa alla coda, ma non coda alla testa. La lista concatenata non viene visualizzato correttamente, sia.

Answer 1

La logica doppiamente lista concatenata guarda bene a me. La mia unica preoccupazione è che se dCurrent è l'unico elemento della lista, allora questo:

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

molto probabilmente cercherà di fare riferimento a un null-pointer. (Dipende da come si progetta la vostra lista. Ma in un design tipico, se dCurrent è l'unico nodo, allora dCurrent->next è NULL.)

La logica singolarmente-linked-list guarda anche bene a me, in astratto, dato il presupposto che "sPrev = sCurrent-> prev"; ma io non capisco come questa ipotesi possa essere corretto. Se si tratta di una lista singolarmente legata, quindi sCurrent non lo fa sono un puntatore prev.

Answer 2

Gli unici problemi che posso vedere è che il codice non funzionerà correttamente per gli scenari in cui capo o la coda vengono aggiornati a NULL.

In sostanza, se si elimina l'unico nodo, dHead punterà a nulla, quindi è necessario mettere "guardie" dichiarazioni intorno successive come

dHead->prev = NULL;

in questo modo

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

Un modo per "aggirare" avere così tanti condizionali è quello di assegnare un elemento NIL (non un tipo).

NIL è il "nodo" che sostituisce NULL. Rappresenta "la porzione di dati dell'elenco" quindi il suo successivo è sempre nulla (un riferimento circolare) ed è precedente è sempre nulla (un riferimento circolare). In questi casi, ci si assicura che NIL non è mai al di fuori accessibile della lista, e che testa-> prev == NIL e di coda> prossimo == NIL. In questo modo è possibile evitare le molte dichiarazioni di tipo if (tail != null) { ... }.

In un tale costrutto, un elenco vuoto è quella in cui head == NIL && tail == NIL. Questo riduce drasticamente il numero di dichiarazioni if (something == null), ma avete ancora uno if da considerare, quando la testa è pari a zero (dopo l'eliminazione di qualcosa) è necessario coda set a zero per l'amor di coerenza.