En informática , una lista doblemente enlazada es una estructura de datos enlazados 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 ganglio centinela, la lista se enlaza circularmente a través del ganglio centinela. Puede conceptualizarse como dos listas enlazadas individualmente formadas a partir de los mismos elementos de datos, pero en órdenes secuenciales opuestos.
Los dos enlaces de nodo permiten recorrer la lista en cualquier dirección. Si bien agregar o eliminar un nodo en una lista de enlaces dobles requiere cambiar más enlaces que las mismas operaciones en una lista de enlaces individuales, las operaciones son más simples y potencialmente más eficientes (para nodos que no sean los primeros) porque no hay necesidad de realizar un seguimiento de el nodo anterior durante el recorrido o no es necesario recorrer la lista para encontrar el nodo anterior, de modo que se pueda modificar su enlace.
Nomenclatura e implementación
El primer y último nodos de una lista doblemente enlazada son inmediatamente accesibles (es decir, accesibles sin recorrido, y generalmente se denominan cabeza y cola ) y, por lo tanto, permiten recorrer la lista desde el principio o el final de la lista, respectivamente: p. Ej., Atravesar la lista. de principio a fin, o de final a 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 usarse 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 enlazado a menudo se denominan siguiente y anterior o adelante y atrás . Las referencias almacenadas en los campos de enlace generalmente se implementan como punteros , pero (como en cualquier estructura de datos vinculados) también pueden ser compensaciones de direcciones o índices en una matriz donde viven los nodos.
Algoritmos basicos
Considere los siguientes algoritmos básicos escritos en Ada:
Abrir listas doblemente enlazadas
record DoublyLinkedNode { siguiente // Una referencia al siguiente nodo anterior // Una referencia a los datos del nodo anterior // Datos o una referencia a los datos}
record DoublyLinkedList { DoubleLinkedNode firstNode // apunta al primer nodo de la lista DoublyLinkedNode lastNode // apunta al último nodo de la lista}
Atravesando la lista
El recorrido de una lista doblemente enlazada puede realizarse en cualquier dirección. De hecho, la dirección de recorrido puede cambiar muchas veces, si se desea. El recorrido a menudo se denomina 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 al recorrido .
Hacia adelante
nodo: = list.firstNode mientras nodo ≠ nulonodo: = nodo.siguiente
Hacia atrás
nodo: = list.lastNode mientras nodo ≠ nulonodo: = nodo.prev
Insertar un nodo
Estas funciones simétricas insertan un nodo antes o después de un nodo determinado:
función insertAfter ( lista de lista, nodo nodo, nodo nuevo nodo ) newNode.prev: = nodo if node.next == null newNode.next: = null - (no siempre es necesario) list.lastNode: = newNode demás newNode.next: = nodo.next node.next.prev: = newNode node.next: = newNode
función insertBefore ( lista de lista, nodo nodo, nodo nuevo nodo ) newNode.next: = nodo if node.prev == null newNode.prev: = null - (no siempre es necesario) list.firstNode: = newNode demás newNode.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 insertBeginning ( Lista lista, Nodo newNode) if list.firstNode == null list.firstNode: = newNode list.lastNode: = newNode newNode.prev: = nulo newNode.next: = nulo demás insertBefore (lista, list.firstNode, newNode)
Una función simétrica inserta al final:
función insertEnd ( Lista lista, Nodo newNode) if list.lastNode == null insertBeginning (lista, newNode) demás insertAfter (lista, list.lastNode, newNode)
Eliminar un nodo
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 eliminará es el primer nodo o el último nodo :
función eliminar ( lista de lista, nodo de nodo) si node.prev == null list.firstNode: = nodo.next demás node.prev.next: = node.next si node.next == null list.lastNode: = node.prev demás node.next.prev: = node.prev
Una consecuencia sutil del procedimiento anterior es que eliminar el último nodo de una lista establece tanto firstNode como lastNode en nulos , por lo que se maneja la eliminación del último nodo de una lista de un elemento correctamente. Tenga en cuenta que tampoco necesitamos métodos separados "removeBefore" o "removeAfter", 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 la existencia del nodo que se está eliminando. Si el nodo no existe en esta lista, entonces se requeriría algún manejo de errores.
Listas circulares doblemente enlazadas
Atravesando la lista
Suponiendo que someNode es algún nodo en una lista no vacía, este código atraviesa esa lista comenzando con someNode (cualquier nodo servirá):
Hacia adelante
nodo: = someNode hacer hacer algo con node.value nodo: = nodo.siguientewhile nodo ≠ someNode
Hacia atrás
nodo: = someNode hacer hacer algo con node.value nodo: = nodo.prevwhile nodo ≠ someNode
Observe el aplazamiento de la prueba hasta el final del ciclo. Esto es importante para el caso en el que la lista contiene solo el nodo único someNode .
Insertar un nodo
Esta función simple inserta un nodo en una lista enlazada circularmente enlazada doblemente después de un elemento dado:
función insertAfter ( nodo nodo, nodo nuevo nodo ) newNode.next: = nodo.next newNode.prev: = nodo node.next.prev: = newNode node.next: = newNode
Para hacer un "insertBefore", podemos simplemente "insertAfter (node.prev, newNode)".
Insertar un elemento en una lista posiblemente vacía requiere una función especial:
función insertEnd ( lista de lista, nodo de nodo) if list.lastNode == null node.prev: = nodo node.next: = nodo demás insertAfter (list.lastNode, nodo) list.lastNode: = nodo
Para insertar al principio simplemente "insertAfter (list.lastNode, node)".
Finalmente, eliminar un nodo debe lidiar con el caso en el que la lista se vacía:
función eliminar ( lista de lista, nodo de nodo); si node.next == nodo list.lastNode: = null else node.next.prev: = node.prev node.prev.next: = node.next if nodo == list.lastNode list.lastNode: = node.prev; destruir nodo
Eliminar un nodo
Como en las listas doblemente enlazadas, "removeAfter" y "removeBefore" se pueden implementar con "remove (list, node.prev)" y "remove (list, node.next)".
Conceptos avanzados
Lista asimétrica doblemente enlazada
Una lista asimétrica doblemente enlazada se encuentra en algún lugar entre la lista enlazada individualmente y la lista doble enlazada normal. Comparte algunas características con la lista enlazada individualmente (recorrido en una sola dirección) y otras de la lista enlazada doble (facilidad de modificación)
Es una lista donde el enlace anterior de cada nodo apunta no al nodo anterior, sino al enlace a sí mismo. Si bien esto hace poca diferencia entre los nodos (que sólo apunta a un desplazamiento dentro del nodo anterior), cambia la cabeza de la lista: Permite que el primer nodo para modificar el firstNode enlace fácilmente. [1] [2]
Mientras un nodo esté en una lista, su enlace anterior nunca es nulo.
Insertar un nodo
Para insertar un nodo antes que otro, cambiamos el enlace que apuntaba al nodo antiguo, usando el enlace anterior ; a continuación, configure el enlace siguiente del nuevo nodo para que apunte al nodo anterior y cambie el enlace anterior de ese nodo en consecuencia.
función insertBefore ( nodo nodo, nodo nuevo nodo ) si nodo.prev == error nulo "El nodo no está en una lista" newNode.prev: = node.prev atAddress (newNode.prev): = newNode newNode.next: = nodo node.prev = addressOf (newNode.next)
función insertAfter ( nodo nodo, nodo nuevo nodo ) newNode.next: = nodo.next if newNode.next! = null newNode.next.prev = addressOf (newNode.next) node.next: = newNode newNode.prev: = addressOf (nodo.siguiente)
Eliminar un nodo
Para eliminar un nodo, simplemente modificamos el enlace señalado por prev , independientemente de si el nodo fue el primero de la lista.
función eliminar ( nodo nodo) atAddress (node.prev): = node.next if node.next! = null node.next.prev = node.prev destruir nodo