Lista unicamente enlazada vs lista doblemente enlazada
La lista vinculada es una estructura de datos lineal que se utiliza para almacenar una colección de datos. Una lista vinculada asigna memoria a sus elementos por separado en su propio bloque de memoria y la estructura general se obtiene vinculando 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 de la secuencia. Una lista doblemente enlazada contiene una secuencia de nodos en la que cada nodo contiene una referencia al siguiente nodo así como al nodo anterior.
Lista individualmente vinculada
Cada elemento en una lista enlazada 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 vinculada se almacena como el encabezado de la lista vinculada.
La Figura 2 muestra una lista enlazada individualmente con tres elementos. Cada elemento almacena sus datos y todos los elementos excepto el último almacenan una referencia al siguiente elemento. El último elemento tiene un valor nulo en su siguiente campo. Se puede acceder a cualquier elemento de la lista comenzando por el encabezado y siguiendo el siguiente puntero hasta encontrar el elemento requerido.
Lista doblemente vinculada
Cada elemento en una lista doblemente enlazada tiene tres campos como se muestra en la Figura 3. Similar a la lista enlazada individualmente, 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 vinculada se almacena como el encabezado de la lista vinculada.
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 enlazada individualmente y la lista doblemente enlazada?
Cada elemento de la lista enlazada individualmente contiene una referencia al siguiente elemento de la lista, mientras que cada elemento de la lista enlazada doble contiene referencias al elemento siguiente, 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 el borrado son más complejas ya que tienen que lidiar con dos referencias. Pero las listas de doble enlace permiten una manipulación más sencilla, ya que permiten recorrer la lista en direcciones hacia adelante y hacia atrás.
