Lista doblemente enlazada

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 nulo, 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.

El primer y el último nodo de una lista doblemente enlazada para todas las aplicaciones prácticas son inmediatamente accesibles (es decir, accesibles sin necesidad de recorrerlos, y normalmente se denominan cabeza y cola) y, por lo tanto, permiten recorrer la lista desde el principio o el final de la lista, respectivamente: por ejemplo, recorrer la lista desde el principio hasta el final, o desde el final hasta el principio, en una búsqueda de la lista de un nodo con un valor de datos específico. Cualquier nodo de una lista doblemente enlazada, una vez obtenido, puede utilizarse para comenzar un nuevo recorrido de la lista, en cualquier dirección (hacia el principio o hacia el final), desde el nodo dado.

Los campos de enlace de un nodo de lista doblemente enlazada se denominan a menudo next y previous o forward y backward. Las referencias almacenadas en los campos de enlace se implementan normalmente 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:

récord DoublyLinkedNode {}
siguiente // Una referencia al próximo nodoprev // Una referencia al nodo anteriordatos // Datos o referencia a los datos}

récord DoublyLinkedList {}
 DoublyLinkedNode primero Node // apunta al primer nodo de lista DoublyLinkedNode último Node // puntos a último nodo de 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 recorrido.

Adelante

nodo:= lista.
mientras nodo nuloHaga algo con node.data
nodo:= nodo.next

Hacia atrás

nodo:= list.lastNode
mientras nodo nuloHaga algo con node.data
nodo:= nodo.prev

Estas funciones simétricas insertan un nodo ya sea antes o después de un nodo determinado:

función insertarDespués(Lista lista, Node nodo, Node newNode)
newNode.prev:= node
 si nodo.next == nulonewNode.next:= nulo -- (no siempre necesario)list.lastNode:= newNode
 másnewNode.next:= node.next
node.next.prev:= newNode
nodo.next:= newNode

función insérteseAntesLista lista, Node nodo, Node newNode)
newNode.next:= nodos
 si nodo.prev == nulonewNode.prev:= nulo -- (no siempre necesario)list.firstNode:= newNode
 másnewNode.prev:= node.prev
node.prev.next:= newNode
node.prev:= newNode

También necesitamos una función para insertar un nodo al comienzo de una lista posiblemente vacía:

función insertarComenzar(Lista lista, Node newNode)
 si lista. firstNode == nulolist.firstNode:= newNode
list.lastNode:= newNode
nuevoNode.prev:= null
newNode.next:= nulo
 másinsertarAntes(lista, lista.firstNode, newNode)

Una función simétrica se inserta al final:

función insertEnd(Lista lista, Node newNode)
 si list.lastNode == nuloinsertComenzar(lista, nuevoNodo)
 másinsert After(list, list.lastNode, newNode)

La eliminación de un nodo es más sencilla que su inserción, pero requiere un manejo especial si el nodo que se va a eliminar es el primerNodo o el últimoNodo:

función quitar(Lista lista, Node nodo)
 si nodo.prev == nulolist.firstNode:= node.next
 másnode.prev.next:= node.next
 si nodo.next == nulolist.lastNode:= node.prev
 másnode.next.prev:= node.prev

Una consecuencia sutil del procedimiento anterior es que al eliminar el último nodo de una lista se establecen tanto firstNode como lastNode como null, y por lo tanto se maneja correctamente la eliminación del último nodo de una lista de un elemento. Observe que tampoco necesitamos métodos "removeBefore" o "removeAfter" separados, porque en una lista doblemente enlazada podemos simplemente usar "remove(node.prev)" o "remove(node.next)" cuando sean válidos. Esto también supone que se garantiza que el nodo que se está eliminando existe. Si el nodo no existe en esta lista, entonces se requerirá algún manejo 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á):

Adelante

node:= someNode
doHaz algo con nodo. valor
nodo:= nodo.next
mientras nodo י some Node

Hacia atrás

node:= someNode
doHaz algo con nodo. valor
nodo:= nodo.prev
mientras nodo י some Node

Observe que la prueba se pospone hasta el final del bucle. Esto es importante en el caso en que la lista contiene únicamente el nodo someNode.

Esta función simple inserta un nodo en una lista circular enlazada doblemente después de un elemento dado:

función insertarDespués(Node nodo, Node newNode)
newNode.next:= node.next
newNode.prev:= node
node.next.prev:= newNode
nodo.next:= newNode

Para hacer un "insertBefore", podemos simplemente hacer un "insertAfter(node.prev, newNode)".

Para insertar un elemento en una lista que posiblemente esté vacía se necesita una función especial:

función insertEnd(Lista lista, Node nodo)
 si list.lastNode == nulonode.prev:= node
nodo.next:= nodos
 másinsert After(list.lastNode, node)
list.lastNode:= node

Para insertar al principio simplemente hacemos "insertAfter(list.lastNode, node)".

Por último, al eliminar un nodo se debe solucionar el caso en el que la lista se vacía:

función quitar(Lista lista, Node nodo);
 si nodo.next == nodos
list.lastNode:= nulo másnode.next.prev:= node.prev
node.prev.next:= node.next
 si node == list.lastNode
list.lastNode:= node.prev;
 destruir nodos

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).

Es 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 firstNode fácilmente.

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 anterior, utilizando el enlace prev; luego, configuramos el enlace next del nuevo nodo para que apunte al nodo anterior y cambiamos el enlace prev de ese nodo en consecuencia.

función insérteseAntesNode nodo, Node newNode)
 si nodo.prev == nulo error "El nodo no está en una lista"
newNode.prev:= node.prev
atAddress(newNode.prev):= newNode
newNode.next:= nodos
node.prev = direcciónOf(newNode.next)

función insertarDespués(Node nodo, Node newNode)
newNode.next:= node.next
 si newNode.next!= nulonewNode.next.prev = addressOf(newNode.next)
nodo.next:= newNode
newNode.prev:= addressOf(node.next)

Para eliminar un nodo, simplemente modificamos el enlace apuntado por prev, independientemente de si el nodo era el primero de la lista.

función quitar(Node nodo)
atAddress(node.prev):= node.next
 si node.next!= nulonodo.next.prev = node.prev
 destruir nodos

• Lista de enlaces XOR
• SLIP (lengua de programación)