Lista con enlace único frente a lista con enlace doble
Lista enlazada es una estructura de datos lineal que se utiliza para almacenar una colección de datos. Una lista enlazada asigna memoria a sus elementos por separado en su propio bloque de memoria y la estructura general se obtiene enlazando estos elementos como eslabones en una cadena. Una lista enlazada individualmente se compone de una secuencia de nodos y cada nodo tiene una referencia al siguiente nodo en la secuencia. Una lista doblemente enlazada contiene una secuencia de nodos en la que cada nodo contiene una referencia tanto al nodo siguiente como al nodo anterior.
Lista de enlaces individuales
Cada elemento en una lista enlazada individualmente tiene dos campos, como se muestra en la Figura 1. El campo de datos contiene los datos reales almacenados y el siguiente campo contiene la referencia al siguiente elemento de la cadena. El primer elemento de la lista enlazada se almacena como el encabezado de la lista enlazada.
La figura 2 muestra una lista enlazada de forma sencilla con tres elementos. Cada elemento almacena sus datos y todos los elementos excepto el último almacenan una referencia al siguiente elemento. El último elemento contiene un valor nulo en su siguiente campo. Se puede acceder a cualquier elemento de la lista comenzando en el encabezado y siguiendo el siguiente puntero hasta encontrar el elemento requerido.
Lista doblemente enlazada
Cada elemento en una lista doblemente enlazada tiene tres campos como se muestra en la Figura 3. De manera similar a la lista de enlaces individuales, el campo de datos contiene los datos reales almacenados y el siguiente campo contiene la referencia al siguiente elemento de la cadena. Además, el campo anterior contiene la referencia al elemento anterior de la cadena. El primer elemento de la lista enlazada se almacena como el encabezado de la lista enlazada.
La figura 4 muestra una lista doblemente enlazada con tres elementos. Todos los elementos intermedios almacenan referencias al primer elemento y al anterior. El último elemento de la lista tiene un valor nulo en su siguiente campo y el primer elemento de la lista tiene un valor nulo en su campo anterior. La lista doblemente enlazada se puede recorrer hacia adelante siguiendo las siguientes referencias en cada elemento y, de manera similar, se puede recorrer hacia atrás utilizando las referencias anteriores en cada elemento.
¿Cuál es la diferencia entre la lista con enlace simple y la lista con enlace doble?
Cada elemento de la lista enlazada individualmente contiene una referencia al siguiente elemento de la lista, mientras que cada elemento de la lista doblemente enlazada contiene referencias al siguiente elemento así como al elemento anterior de la lista. Las listas doblemente enlazadas requieren más espacio para cada elemento de la lista y las operaciones elementales como la inserción y la eliminación son más complejas ya que tienen que tratar con dos referencias. Pero las listas de enlaces dobles permiten una manipulación más fácil, ya que permiten recorrer la lista hacia adelante y hacia atrás.
