Eliminar un nodo aleatorio de listas individuales y doblemente vinculadas

Question

Me está costando mucho encontrar la lógica para eliminar algún nodo de una lista vinculada doblemente y individualmente. Busqué en línea de ayuda, pero no pude encontrar un ejemplo simple de ello. Esto es lo que tengo:

---

Deleción doblemente vinculada. dCurrent es el nodo que queremos eliminar.

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

---

Esto es lo que tengo para la lista vinculada individualmente. Otra vez, sCurrent es el nodo para eliminar. y sPrev = sCurrent->prev.

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

---

El problema es que después de eliminar una colección de nodos aleatorios de ambas listas, la lista doblemente vinculada se muestra correctamente de cabeza a cola, pero no de cola a cabeza. La lista vinculada individualmente tampoco se muestra correctamente.

Answer 1

Tu lógica de la lista doblemente vinculada me parece bien. Mi única preocupación es que si dCurrent es el único elemento en la lista, entonces esto:

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

Lo más probable es que intente hacer referencia a un nulo de puente. (Depende de cómo diseñe su lista. Pero en un diseño típico, si dCurrent es el único nodo, entonces dCurrent->next es NULL.)

Su lógica de la lista vinculada individualmente también me parece bien, en abstracto, dada la suposición de que "sprev = scurrent-> anterior"; Pero no entiendo cómo esa suposición puede ser correcta. Si es una lista vinculada individualmente, entonces sCurrent no tener a prev puntero.

Answer 2

Los únicos problemas que puedo ver es que su código no funcionará correctamente para escenarios en los que la cabeza o la cola se actualicen a NULL.

Básicamente, si elimina el único nodo, Dhead apuntará a NULL, por lo que debe poner "guardias" en declaraciones posteriores como

dHead->prev = NULL;

al igual que

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

Una forma de "moverse" tener tantos condicionales es asignar un elemento NIL (no un tipo).

Nil es el "nodo" que reemplaza a NULL. Representa "fuera de la parte de datos de la lista", por lo que su siguiente es siempre nulo (una referencia circular) y su anterior es siempre nulo (una referencia circular). En tales casos, se asegura de que NIL nunca sea accesible fuera de la lista, y que Head-> Prev == nil y Tail-> Next == nil. De esa manera puedes evitar los muchos if (tail != null) { ... } Tipo de declaraciones.

Bajo una construcción de este tipo, una lista vacía es una donde head == NIL && tail == NIL. Esto reduce drásticamente el número de if (something == null) declaraciones, pero aún tiene una declaración if a considerar, cuando la cabeza es nula (después de eliminar algo) debe establecer la cola en nulo por el bien de la consistencia.