lista dobles

El primer y el último nodo de una lista doblemente enlazada son accesibles inmediatamente (o sea, accesibles sin necesidad de recorrer la lista, y usualmente llamados cabeza y cola) y esto permite recorrerla desde el inicio o el final de la lista, respectivamente. Cualquier nodo de la lista doblemente enlazada, una vez obtenido, puede ser usado para empezar un nuevo recorrido de la lista, en cualquier dirección (hacia el principio o el final), desde el nodo dado.

Los enlaces de un nodo de una lista doblemente enlazada son frecuentemente llamados anterior y siguiente o antecesor y sucesor. Las referencias guardadas en los enlaces son usualmente implementadas como punteros,pero también podrían ser índices de un array donde están los nodos.

Algoritmos Básicos[editar]
lista doblemente enlazada[editar]
record NodoDoblementeEnlazado {
siguiente // Una referencia al nodo siguiente
anterior // Una referencia al nodo anterior
dato // dato o referencia al dato
}
record ListaDoblementeEnlazada {
NodoDoblementeEnlazado primerNodo // referencia al primer nodo de la lista
NodoDoblementeEnlazado ultimoNodo // referencia al último nodo de la lista
}
Recorriendo la lista[editar]
Recorrer una lista doblemente enlazada puede ser en cualquier dirección. De hecho, la dirección del recorrido puede cambiar muchas veces, si se desea. Recorrido es frecuentemente llamado iteración.

Hacia adelante

nodo := lista.primerNodo
while nodo ≠ null

nodo := nodo.siguiente
Hacia atrás

nodo := lista.ultimoNodo
while nodo ≠ null

nodo := nodo.anterior
Insertando un nodo[editar]
Estas funciones insertan un nodo ya sea adelante o atrás de un nodo dado:

function InsertaAdelante(Lista lista, Nodo nodo, Nodo nuevoNodo)
nuevoNodo.anterior := nodo
nuevoNodo.siguiente := nodo.siguiente
if nodo.siguiente == null
lista.ultimoNodo := nuevoNodo
else
nodo.siguiente.anterior := nuevoNodo
nodo.siguiente := nuevoNodo
function InsertaAtras(Lista lista, Nodo nodo, Nodo nuevoNodo)
nuevoNodo.anterior := nodo.anterior
nuevoNodo.siguiente := nodo
if nodo.anterior == null
lista.primerNodo := nuevoNodo
else
nodo.anterior.siguiente := nuevoNodo
nodo.anterior := nuevoNodo
También necesitamos una función para insertar un nodo al principio de una lista posiblemente vacía:

function InsertaAlPrincipio(Lista lista, Nodo nuevoNodo)
if lista.primerNodo == null
lista.primerNodo := nuevoNodo
lista.ultimoNodo := nuevoNodo
nuevoNodo.anterior := null
nuevoNodo.siguiente := null
else
InsertaAtras(lista, lista.primerNodo , nuevoNodo)
La siguiente función inserta al final:

function InsertaAlFinal(Lista lista, Nodo nuevoNodo)
if lista.ultimoNodo == null
InsertaAlPrincipio(lista, nuevoNodo)
else
InsertatAdelante(lista, lista.ultimoNodo, nuevoNodo)
Borrando un Nodo[editar]
Eliminar un nodo es más fácil que insertar, pero requiere un manejo especial si el nodo a eliminar es el primerNodo o el ultimoNodo:

function Elimina(Lista lista, Nodo nodo)
if nodo.anterior == null
lista.primerNodo := nodo.siguiente
else
nodo.anterior.siguiente := nodo.siguiente
if nodo.siguiente== null
lista.ultimoNodo := nodo.anterior
else
nodo.siguiente.anterior := nodo.anterior
destroy nodo
Una sutil consecuencia del procedimiento de arriba es que eliminando el último nodo de una lista asigna a primerNodo y a ultimoNodo a null, y de esta forma maneja correctamente eliminar el último nodo de una lista de un solo elemento. Tampoco necesitamos separar los métodos "EliminarAtras" o "EliminarAdelante", porque en una lista doblemente enlazada podemos usar "Elimina(nodo.anterior)" o "Elimina(nodo.siguiente)" cuando sea válido. También se asume que está garantizado que el nodo siendo eliminado existe. Si el nodo no existe en la lista, entonces algún manejo de error será requerido.

lista Doblemente Enlazada Circular[editar]
Recorriendo la lista[editar]
Asumir que algunNodo es algún nodo en una lista no vacía, este código recorre la lista empezando por' 'algunNodo:

Hacia delante

nodo := algunNodo
do

nodo := nodo.siguiente
while nodo ≠ algunNodo
Hacia atrás

nodo := algunNodo
do

nodo := nodo.anterior
while nodo ≠ algunNodo
Notar que la condición se ejecuta al final del ciclo. Esto es importante para el caso en que la lista contiene el único nodo algunNodo.

Insertar un Nodo[editar]
Esta simple función inserta un nodo en una lista doblemente enlazada circular delante de un elemento dado:

function InsertaDelante(Nodo nodo, Nodo nuevoNodo)
nuevoNodo.siguiente := nodo.siguiente
nuevoNodo.anterior := nodo
nodo.siguiente.anterior := nuevoNodo
nodo.siguiente := nuevoNodo
Para hacer un "InsertaAtras" podemos hacer simplemente "InsertaDelante(nodo.anterior, nuevoNodo)".

Insertar un elemento en una lista posiblemente vacía requiere una función especial:

function InsertaAlFinal(Lista lista, Nodo nodo)
if lista.ultimoNodo == null
nodo.anterior := nodo
nodo.siguiente := nodo
else
InsertaDelante(lista.ultimoNodo, nodo)
lista.ultimoNodo:= nodo
Para insertar en el principio simplemente hacemos "InsertaDelante(lista.ultimoNodo , nodo)".

Finalmente para eliminar un nodo debemos lidiar con el caso donde la lista es vacía:

function Elimina(Lista lista, Nodo nodo)
if nodo.siguiente == nodo
lista.ultimoNodo := null
else
nodo.siguiente.anterior := nodo.anterior
nodo.anterior.siguiente := nodo.siguiente
if nodo == lista.ultimoNodo
lista.ultimoNodo:= nodo.anterior;
destroy nodo