En informática , una lista doblemente enlazada es una estructura de datos enlazada que consta de un conjunto de registros enlazados secuencialmente llamados nodos . Cada nodo contiene tres campos : dos campos de enlace ( referencias al nodo anterior y al siguiente en la secuencia de nodos) y un campo de datos. Los enlaces anterior y siguiente de los nodos inicial y final , respectivamente, apuntan a algún tipo de terminador, normalmente un nodo centinela o null , para facilitar el recorrido de la lista. Si solo hay un nodo centinela, entonces la lista está enlazada circularmente a través del nodo centinela. Puede conceptualizarse como dos listas enlazadas simples formadas a partir de los mismos elementos de datos, pero en órdenes secuenciales opuestos.
Los dos enlaces de nodos permiten recorrer la lista en cualquier dirección. Si bien agregar o eliminar un nodo en una lista doblemente enlazada requiere cambiar más enlaces que las mismas operaciones en una lista simplemente enlazada, las operaciones son más simples y potencialmente más eficientes (para nodos que no sean los primeros nodos) porque no hay necesidad de realizar un seguimiento del nodo anterior durante el recorrido o no hay necesidad de recorrer la lista para encontrar el nodo anterior, de modo que se pueda modificar su enlace.
Los nodos primero y último de una lista doblemente enlazada para todas las aplicaciones prácticas son inmediatamente accesibles (es decir, accesibles sin recorrido, y generalmente llamados cabeza y cola ) y, por lo tanto, permiten el recorrido de la lista desde el principio o el final de la lista, respectivamente: por ejemplo, recorriendo la lista desde el principio hasta el final, o desde el final hasta el principio, en una búsqueda de la lista para un nodo con un valor de datos específico. Cualquier nodo de una lista doblemente enlazada, una vez obtenido, se puede utilizar para comenzar un nuevo recorrido de la lista, en cualquier dirección (hacia el principio o el final), desde el nodo dado.
Los campos de enlace de un nodo de lista doblemente enlazada suelen denominarse next y previous o forward y reverse . Las referencias almacenadas en los campos de enlace suelen implementarse como punteros , pero (como en cualquier estructura de datos enlazada), también pueden ser desplazamientos de direcciones o índices en una matriz donde se encuentran los nodos.
Considere los siguientes algoritmos básicos escritos en Ada:
registro NodoDoblementeEnlazado { next // Una referencia al siguiente nodo prev // Una referencia al nodo anterior data // Datos o una referencia a datos}registro DoublyLinkedList { DoublyLinkedNode firstNode // apunta al primer nodo de la lista DoublyLinkedNode lastNode // apunta al último nodo de la lista}El recorrido de una lista doblemente enlazada puede realizarse en cualquier dirección. De hecho, la dirección del recorrido puede cambiar muchas veces, si se desea. El recorrido se suele denominar iteración , pero esa elección de terminología es desafortunada, ya que la iteración tiene una semántica bien definida (por ejemplo, en matemáticas) que no es análoga a la del recorrido .
Hacia adelante
nodo := lista.primerNodo mientras nodo ≠ nulo <hacer algo con node.data> nodo := nodo.siguiente
Hacia atrás
nodo := lista.últimoNodo mientras nodo ≠ nulo <hacer algo con node.data> nodo := nodo.prev
Estas funciones simétricas insertan un nodo antes o después de un nodo dado:
función insertAfter( Lista lista , Nodo nodo , Nodo nuevoNodo) nuevoNodo.prev := nodo si node.next == null newNode.next := null -- (no siempre es necesario) lista.lastNode := nuevoNodo demás nuevoNodo.siguiente := nodo.siguiente nodo.siguiente.anterior := nuevoNodo nodo.siguiente := nuevoNodo
función insertBefore( Lista lista , Nodo nodo , Nodo nuevoNodo) nuevoNodo.siguiente := nodo si node.prev == null newNode.prev := null -- (no siempre es necesario) lista.primerNodo := nuevoNodo demás nuevoNodo.prev := nodo.prev nodo.prev.next := nuevoNodo nodo.prev := nuevoNodo
También necesitamos una función para insertar un nodo al comienzo de una lista posiblemente vacía:
función insertBeginning( Lista lista , Nodo nuevoNodo) si lista.primerNodo == null lista.primerNodo := nuevoNodo lista.lastNode := nuevoNodo nuevoNodo.prev := nulo nuevoNodo.siguiente := null demás insertBefore(lista, lista.firstNode, nuevoNodo)
Una función simétrica inserta al final:
función insertEnd( Lista lista , Nodo nuevoNodo) si lista.lastNode == null insertBeginning(lista, nuevoNodo) demás insertarDespués(lista, lista.últimoNodo, nuevoNodo)
La eliminación de un nodo es más fácil que la inserción, pero requiere un manejo especial si el nodo que se va a eliminar es el firstNode o el lastNode :
función remove( Lista lista , Nodo nodo ) si nodo.prev == null lista.primerNodo := nodo.siguiente demás nodo.prev.next := nodo.siguiente si nodo.siguiente == nulo lista.lastNode := nodo.prev demás nodo.siguiente.anterior := nodo.anterior
Una consecuencia sutil del procedimiento anterior es que al eliminar el último nodo de una lista se establecen tanto firstNode como lastNode en null , por lo que se gestiona correctamente la eliminación del último nodo de una lista de un elemento. Observe que tampoco necesitamos métodos "removeBefore" o "removeAfter" independientes, porque en una lista doblemente enlazada podemos utilizar simplemente "remove(node.prev)" o "remove(node.next)" cuando sean válidos. Esto también supone que se garantiza que el nodo que se va a eliminar existe. Si el nodo no existe en esta lista, se requerirá algún tipo de gestión de errores.
Suponiendo que someNode es un nodo en una lista no vacía, este código recorre esa lista comenzando con someNode (cualquier nodo servirá):
Hacia adelante
nodo := algúnNodo hacer hacer algo con node.value nodo := nodo.siguientemientras nodo ≠ algúnNodo
Hacia atrás
nodo := algúnNodo hacer hacer algo con node.value nodo := nodo.prevmientras nodo ≠ algúnNodo
Observe que la prueba se pospone hasta el final del bucle. Esto es importante en el caso en que la lista contiene solo el nodo único someNode .
Esta sencilla función inserta un nodo en una lista circular enlazada doblemente después de un elemento dado:
función insertAfter( Nodo nodo , Nodo nuevoNodo) nuevoNodo.siguiente := nodo.siguiente nuevoNodo.prev := nodo nodo.siguiente.anterior := nuevoNodo nodo.siguiente := nuevoNodo
Para hacer un "insertBefore", podemos simplemente "insertAfter(node.prev, newNode)".
Para insertar un elemento en una lista posiblemente vacía se requiere una función especial:
función insertEnd( Lista lista , Nodo nodo ) si lista.lastNode == null nodo.prev := nodo nodo.siguiente := nodo demás insertarDespués(lista.últimoNodo,nodo) lista.lastNode := nodo
Para insertar al principio simplemente "insertAfter(list.lastNode, node)".
Finalmente, al eliminar un nodo se debe solucionar el caso en el que la lista se vacía:
función remove( Lista lista , Nodo nodo ); si nodo.next == nodo lista.lastNode := null de lo contrario nodo.siguiente.anterior := nodo.anterior nodo.prev.next := nodo.siguiente si nodo == lista.últimoNodo lista.lastNode := nodo.prev; destruir nodo
Al igual que en las listas doblemente enlazadas, "removeAfter" y "removeBefore" se pueden implementar con "remove(list, node.prev)" y "remove(list, node.next)".
Una lista doblemente enlazada asimétrica se encuentra en un punto intermedio entre la lista simple enlazada y la lista doblemente enlazada normal. Comparte algunas características con la lista simple enlazada (recorrido en una sola dirección) y otras con la lista doblemente enlazada (facilidad de modificación).
Se trata de una lista en la que el enlace anterior de cada nodo no apunta al nodo anterior, sino al enlace a sí mismo. Si bien esto hace poca diferencia entre los nodos (solo apunta a un desplazamiento dentro del nodo anterior), cambia el encabezado de la lista: permite que el primer nodo modifique el enlace del primer nodo fácilmente. [1] [2]
Mientras un nodo esté en una lista, su enlace anterior nunca será nulo.
Para insertar un nodo antes de otro, cambiamos el enlace que apuntaba al nodo antiguo, usando el enlace anterior ; luego, configuramos el siguiente enlace del nuevo nodo para que apunte al nodo antiguo, y cambiamos el enlace anterior de ese nodo en consecuencia.
función insertBefore( Nodo nodo , Nodo nuevoNodo) si nodo.prev == null error "El nodo no está en una lista" nuevoNodo.prev := nodo.prev atAddress(nuevoNodo.prev) := nuevoNodo nuevoNodo.siguiente := nodo nodo.prev = direccionDe(nuevoNodo.siguiente)
función insertAfter( Nodo nodo , Nodo nuevoNodo) nuevoNodo.siguiente := nodo.siguiente si newNode.next != nulo nuevoNodo.siguiente.prev = direcciónDe(nuevoNodo.siguiente) nodo.siguiente := nuevoNodo nuevoNodo.prev := direcciónDe(nodo.siguiente)
Para eliminar un nodo, simplemente modificamos el enlace apuntado por prev , independientemente de si el nodo fue el primero de la lista.
función remove( nodo nodo ) atAddress(nodo.prev) := nodo.siguiente si nodo.siguiente != nulo nodo.siguiente.anterior = nodo.anterior destruir nodo