Hispanopedia WikiEn informática , una lista doblemente enlazada es una estructura de datos enlazada que consta de un conjunto de registros enlazados secuencialmente, denominados nodos . Cada nodo contiene tres campos : dos campos de enlace ( referencias al nodo anterior y al siguiente en la secuencia) y un campo de datos. Los enlaces anterior y siguiente de los nodos inicial y final , respectivamente, apuntan a un terminador, generalmente un nodo centinela o un valor nulo , para facilitar el recorrido de la lista. Si solo hay un nodo centinela, la lista se enlaza circularmente a través de este. Puede conceptualizarse como dos listas enlazadas simples formadas a partir de los mismos elementos de datos, pero en orden secuencial opuesto.
Los dos enlaces entre nodos permiten recorrer la lista en cualquier dirección. Si bien agregar o eliminar un nodo en una lista doblemente enlazada requiere modificar más enlaces que las mismas operaciones en una lista simplemente enlazada, las operaciones son más sencillas y potencialmente más eficientes (para nodos distintos del primero) porque no es necesario mantener un registro del nodo anterior durante el recorrido ni recorrer la lista para encontrarlo y modificar su enlace.
Nomenclatura e implementación
En todas las aplicaciones prácticas, el primer y el último nodo de una lista doblemente enlazada son inmediatamente accesibles (es decir, accesibles sin necesidad de recorrerla, y generalmente se denominan cabeza y cola ), lo que permite recorrer la lista desde el principio o el final, respectivamente. Por ejemplo, se puede recorrer la lista desde el principio hasta el final, o desde el final hasta el principio, para buscar un nodo con un valor específico. Cualquier nodo de una lista doblemente enlazada, una vez obtenido, puede utilizarse para iniciar un nuevo recorrido de la lista, en cualquier dirección (hacia el principio o hacia el final), a partir de dicho nodo.
Los campos de enlace de un nodo de una lista doblemente enlazada suelen denominarse siguiente y anterior , o adelante y atrás . 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 dentro de un arreglo donde se encuentran los nodos.
Algoritmos básicos
Consideremos los siguientes algoritmos básicos escritos en Ada:
Listas doblemente enlazadas abiertas
registro Nodo Doblemente Vinculado { next // Una referencia al siguiente nodo prev // Una referencia al nodo anterior data // Datos o una referencia a datos }registro ListaDoblementeEnlazada { NodoDoblementeEnlazado primerNodo // apunta al primer nodo de la lista NodoDoblementeEnlazado últimoNodo // apunta al último nodo de la lista }Recorriendo la lista
El recorrido de una lista doblemente enlazada puede realizarse en cualquier dirección. De hecho, la dirección del recorrido puede cambiar varias veces, si se desea. A menudo se denomina iteración al recorrido , pero esta 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 := 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
Insertar un nodo
Estas funciones simétricas insertan un nodo después o antes de un nodo dado:
función insertarDespués( Lista lista , Nodo nodo , Nodo nuevoNodo) nuevoNodo.prev := nodo Si node.next es nulo , newNode.next es nulo (no siempre es necesario). lista.últimoNodo := nuevoNodo demás nuevoNodo.siguiente := nodo.siguiente nodo.siguiente.anterior := nuevoNodo nodo.siguiente := nuevoNodo
función insertarAntes( 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.anterior.siguiente := nuevoNodo nodo.prev := nuevoNodo
También necesitamos una función para insertar un nodo al principio de una lista posiblemente vacía:
función insertarInicio( Lista lista , Nodo nuevoNodo) si lista.primerNodo == null lista.primerNodo := nuevoNodo lista.últimoNodo := nuevoNodo newNode.prev := null newNode.next := null de lo contrario insertBefore(lista, lista.firstNode, newNode)
Una función simétrica se inserta al final:
función insertEnd( Lista lista , Nodo nuevoNodo) si lista.últimoNodo == null insertarInicio(lista, nuevoNodo) de lo contrario insertarDespués(lista, lista.últimoNodo, nuevoNodo)
Eliminar un nodo
Eliminar un nodo es más fácil que insertarlo, pero requiere un tratamiento especial si el nodo que se va a eliminar es el primer nodo o el último nodo :
función remove( Lista lista , Nodo nodo ) si nodo.prev == null lista.primerNodo := nodo.siguiente demás nodo.anterior.siguiente := nodo.siguiente Si node.next == null lista.últimoNodo := nodo.anterior de lo contrario node.next.prev := node.prev
Una consecuencia sutil del procedimiento anterior es que al eliminar el último nodo de una lista, tanto firstNode como lastNode se establecen en nulo , lo que permite eliminar correctamente el último nodo de una lista de un solo elemento. Cabe destacar que tampoco necesitamos métodos separados como "removeBefore" o "removeAfter", ya que en una lista doblemente enlazada podemos usar simplemente "remove(node.prev)" o "remove(node.next)" cuando sean válidos. Esto también presupone que el nodo que se está eliminando existe. Si el nodo no existe en esta lista, se requeriría algún tipo de manejo de errores.
Listas circulares doblemente enlazadas
Recorriendo la lista
Suponiendo que someNode es algún 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 Haz algo con node.value nodo := nodo.siguiente mientras nodo ≠ algúnNodo
Hacia atrás
nodo := algúnNodo hacer Haz algo con node.value nodo := nodo.prev mientras nodo ≠ algúnNodo
Nótese que la prueba se pospone hasta el final del bucle. Esto es importante para el caso en que la lista contiene solo el nodo único someNode .
Insertar un nodo
Esta sencilla función inserta un nodo en una lista circular doblemente enlazada después de un elemento dado:
función insertarDespués( Nodo nodo , Nodo nuevoNodo) nuevoNodo.siguiente := nodo.siguiente nuevoNodo.prev := nodo nodo.siguiente.anterior := nuevoNodo nodo.siguiente := nuevoNodo
Para hacer un "insertarAntes", simplemente podemos "insertarDespués(nodo.prev, nuevoNodo)".
Insertar un elemento en una lista posiblemente vacía requiere una función especial:
función insertarEnd( Lista lista , Nodo nodo ) si lista.últimoNodo == null nodo.prev := nodo nodo.siguiente := nodo demás insertarDespués(lista.últimoNodo,nodo) lista.últimoNodo := nodo
Para insertar al principio, simplemente "insertAfter(list.lastNode, node)".
Finalmente, al eliminar un nodo hay que tener en cuenta el caso en que la lista quede vacía:
función remove( Lista lista , Nodo nodo ); si nodo.next == nodo lista.últimoNodo := null de lo contrario nodo.siguiente.anterior := nodo.anterior nodo.anterior.siguiente := nodo.siguiente si nodo == lista.últimoNodo lista.últimoNodo := nodo.anterior; destruir nodo
Eliminar un 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)".
Conceptos avanzados
Lista doblemente enlazada asimétrica
Una lista doblemente enlazada asimétrica se sitúa entre la lista enlazada simple y la lista doblemente enlazada convencional. Comparte algunas características con la lista enlazada simple (recorrido unidireccional) y otras con la lista doblemente enlazada (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 no supone una gran diferencia entre los nodos (simplemente apunta a un desplazamiento dentro del nodo anterior), sí cambia el encabezado de la lista: permite que el primer nodo modifique fácilmente el enlace firstNode . [ 1 ] [ 2 ]
Mientras un nodo esté en una lista, su enlace anterior nunca será nulo.
Insertar un nodo
Para insertar un nodo antes que otro, cambiamos el enlace que apuntaba al nodo anterior, usando 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 insertBefore( Nodo nodo , Nodo nuevoNodo) si nodo.prev == null error "El nodo no está en una lista" nuevoNodo.prev := nodo.prev atAddress(newNode.prev) := newNode nuevoNodo.siguiente := nodo nodo.prev = direcciónDe(nuevoNodo.siguiente)
función insertarDespués( Nodo nodo , Nodo nuevoNodo) nuevoNodo.siguiente := nodo.siguiente si newNode.next != null nuevoNodo.siguiente.anterior = direcciónDe(nuevoNodo.siguiente) nodo.siguiente := nuevoNodo nuevoNodo.prev := direcciónDe(nodo.siguiente)
Eliminar un nodo
Para eliminar un nodo, simplemente modificamos el enlace al que apunta prev , independientemente de si el nodo era el primero de la lista.
función remove( Nodo nodo ) atAddress(node.prev) := node.next si node.next != null nodo.siguiente.anterior = nodo.anterior destruir nodo
Véase también
Referencias
- Listas enlazadas