Cómo eliminar un nodo en una lista de enlaces individuales con solo un puntero apuntando al nodo que se va a eliminar?Eliminar un nodo en la lista de enlaces individuales
[inicio y final punteros no se conocen, la información disponible es puntero al nodo que debe ser eliminado]
Puede eliminar un nodo sin obtener el nodo anterior, al tener que imitan el siguiente nodo y la supresión de que uno en su lugar:
void delete(Node *n) {
if (!is_sentinel(n->next)) {
n->content = n->next->content;
Node *next = n->next;
n->next = n->next->next;
free(next);
} else {
n->content = NULL;
free(n->next);
n->next = NULL;
}
}
Como puede ver, tendrá que ocuparse especialmente del último elemento. Estoy usando un nodo especial como nodo centinela para marcar la terminación que tiene content y next sea NULL.
ACTUALIZACIÓN: las líneas Node *next = n->next; n->next = n->next->next básicamente baraja el contenido del nodo, y libera el nodo: La imagen que se obtiene una referencia al nodo B para borrar en:
A /To be deleted
next ---> B
next ---> C
next ---> *sentinel*
El primer paso es n->content = n->next->content: copiar el contenido de la siguiente nodo al nodo de ser "eliminado":
A /To be deleted
next ---> C
next ---> C
next ---> *sentinel*
Entonces, modificar los next puntos:
A /To be deleted
next ---> C /----------------
next ---| C |
next ---> *sentinel*
El realmente libre el siguiente elemento, llegando al final del caso:
A /To be deleted
next ---> C
next ---> *sentinel*
La única sensible y segura opción bajo tales restricciones es marcan el nodo eliminado sin llegar a desenlazándolo, difiriendo que a un tiempo posterior.
No es la única opción sino una buena, por lo tanto, +1. Hacemos eso en nuestro sistema bastante con eliminaciones de marcas no utilizadas/diferidas. – Adisak
No es posible.
Hay hacks para imitar la eliminación.
Pero nada de eso eliminará realmente el nodo al que apunta el puntero.
a eliminar la solución popular de la supresión de la siguiente nodo y copiar su contenido al nodo realtiene efectos secundarios si tiene punteros externos que apuntan a los nodos de la lista, en cuyo caso una el puntero externo que apunta al siguiente nodo quedará colgando.
Puede encontrar alguna discusión sobre SO here.
Node * siguiente = n-> siguiente; n-> siguiente = n-> siguiente-> siguiente; ¿Puedes por favor elaborar esto más? – user215968
Si la lista enlazada es lo suficientemente larga, ¿será el cambio de contenido una solución viable? – user215968
@unknown, sí, sería una solución factible. Este enfoque puede complicar el aliasing (otro código contiene una referencia a los nodos afectados y tal); pero lo tendrás de todos modos. – notnoop