Es una estructura dinámica, donde el número de nodos puede variar dependiendo de las necesidades del proceso: agregando nodos por inserciones o disminuyendo nodos por eliminación.
La lista de enlace doble está caracterizada por tener únicamente dos enlaces: uno al siguiente nodo y otro al anterior nodo. Cuenta con un nodo cabeza y un nodo al final de la lista.
Se accede a la lista mediante el primer nodo de la lista llamado “cabeza” o “cabecera” y el último nodo llamado “cola”, cada enlace del nodo apuntará al siguiente y al anterior nodo.
Se debe contar con un apuntador que se encargar de referenciar al primer nodo de la lista y otro apuntador al nodo final de la lista.
Complejidad
En LDE, el recorrido se puede realizar utilizando el enlace de nodo anterior o el enlace de nodo siguiente. Por lo tanto, el recorrido es posible en ambas direcciones (hacia adelante y hacia atrás). Además la LDE ocupa más memoria que LSD ya que tiene 3 campos.
La complejidad de inserción y eliminación en una posición dada es O(n / 2) = O(n) porque el recorrido se puede realizar desde el principio o desde el final.
La complejidad de la eliminación con un nodo dado es O (1) porque se puede acceder fácilmente al nodo anterior.