Nuestros mejores investigadores han agotado sus provisiones de café, en su búsqueda a tiempo completo por la resolución, hasta que Emilia halló el hallazgo en Bitbucket así que en este momento la comparte con nosotros.
Solución:
La inserción es claramente menos laboriosa en una lista con un solo enlace, siempre y cuando se contente con insertar siempre al principio o después de algún elemento conocido. (Es decir, no puede insertar antes de un elemento conocido, pero consulte a continuación).
La eliminación, por otro lado, es más complicada porque necesita conocer el elemento antes que el elemento que se eliminará.
Una forma de hacerlo es hacer que la API de eliminación funcione con el predecesor del elemento que se va a eliminar. Esto refleja la API de inserción, que toma el elemento que será el predecesor del nuevo elemento, pero no es muy conveniente y es difícil de documentar. Sin embargo, por lo general es posible. En términos generales, se llega a un elemento de una lista recorriendo la lista.
Por supuesto, puede buscar en la lista desde el principio para encontrar el elemento que desea eliminar, de modo que sepa cuál fue su predecesor. Eso supone que la API de eliminación incluye el encabezado de la lista, lo que también es un inconveniente. Además, la búsqueda es estúpidamente lenta.
La forma que casi nadie usa, pero que en realidad es bastante efectiva, es definir un iterador de lista de enlace único para que sea el puntero al elemento que precede al objetivo actual del iterador. Esto es simple, solo una indirección más lenta que usar un puntero directamente al elemento, y hace que tanto la inserción como la eliminación sean rápidas. La desventaja es que eliminar un elemento puede invalidar otros iteradores para enumerar elementos, lo cual es molesto. (No invalida el iterador del elemento que se está eliminando, lo cual es bueno para recorridos que eliminan algunos elementos, pero eso no es una gran compensación).
Si la eliminación no es importante, quizás porque las estructuras de datos son inmutables, las listas de enlaces simples ofrecen otra propiedad realmente útil: permiten compartir estructuras. Una lista con un solo enlace felizmente puede ser la cola de varias cabezas, algo que es imposible para una lista con doble enlace. Por esta razón, las listas de enlaces simples han sido tradicionalmente la estructura de datos simple de elección para los lenguajes funcionales.
Aquí hay un código que me hizo más claro … Tener:
class Node
Node next;
Node prev;
ELIMINAR un nodo en una ÚNICA LISTA VINCULADA -Sobre)-
No sabe cuál es el nodo anterior, por lo que debe recorrer la lista hasta encontrarlo:
deleteNode(Node node)
prevNode = tmpNode;
tmpNode = prevNode.next;
while (tmpNode != null)
if (tmpNode == node)
prevNode.next = tmpNode.next;
prevNode = tmpNode;
tmpNode = prevNode.next;
ELIMINAR un nodo en una LISTA DOBLE ENLACE -O(1)-
Simplemente puede actualizar los enlaces de esta manera:
deleteNode(Node node)
node.prev.next = node.next;
node.next.prev = node.prev;
Aquí están mis pensamientos sobre la lista doblemente enlazada:
-
Tiene acceso listoinsertar en ambos extremos.
-
puede funcionar como Cola y Pila al mismo tiempo.
-
La eliminación de nodos no requiere punteros adicionales.
-
Puede aplicar el recorrido Hill-Climb ya que ya tiene acceso en ambos extremos.
-
Si está almacenando valores numéricos y su lista está ordenada, puede mantener un puntero/variable para la mediana, entonces la operación de búsqueda puede ser muy óptima utilizando el enfoque estadístico.
Reseñas y valoraciones de la guía
Nos puedes confirmar nuestra publicación exponiendo un comentario o dejando una valoración te estamos eternamente agradecidos.