LISTAS ENLAZADAS

Una lista enlazada o estructura ligada, es una estructura lineal que almacena una colección de elementos generalmente llamados nodos, en donde cada nodo puede almacenar datos y ligas a otros nodos. De esta manera los nodos pueden localizarse en cualquier parte de la memoria, utilizando la referencia que lo relaciona con otro nodo dentro de la estructura.

Las listas enlazadas son estructuras dinámicas que se utilizan para almacenar datos que están cambiando constante mente. A diferencia de los vectores, las estructuras dinámicas se expanden y se contraen haciéndolas más flexibles a la hora de añadir o eliminar información.

 Las listas enlazadas permiten almacenar información en posiciones de memoria que no sean contiguas; y se almacena en los elementos nodos. Estos nodos poseen dos campos uno para almacenar la información o valor del elemento y otro para el enlace que determina la posición del siguiente elemento o nodo de la lista. 

Ilustración 1.  Estructura de un nodo

Se compone de dos partes: una que contiene la información en sí y la segunda es un puntero y q su función es apuntar al siguiente nodo que haya.

Listas enlazadas simples

Una lista enlazada simple es una colección de nodos que tienen una sola dirección y que en conjunto forman una estructura de datos lineal. Cada nodo es un objeto compuesto que guarda una referencia a un elemento (dato) y una referencia a otro nodo (dirección).

La referencia que guarda un nodo a otro nodo se puede considerar un enlace o un puntero hacia el segundo nodo y el salto que los relaciona recibe el nombre de salto de enlace o salto de puntero. El primer nodo de una lista recibe el nombre de cabeza, cabecera o primero y el último es llamado final, cola o último (es el único nodo con la referencia a otro objeto como nula).

Un nodo de una lista enlazada simple puede determinar quien se encuentra después de él, pero no puede determinar quien se encuentra antes, ya que solo cuenta con la dirección del nodo siguiente pero no del anterior.

Ilustración 2.  Se observa un puntero que va a apuntar al primer elemento que se ingresa y otro puntero que apuntara al último que será NULO.

Cuando tenemos una lista de la siguiente manera cada puntero apuntara al nodo siguiente y el puntero de la última lista como no tiene a donde apuntar entonces apuntara a NULO.

Para acceder a un nodo se utiliza la anterior con excepción del primero (no tiene a nadie antes) al que se tiene que acceder a través de un puntero externo a la lista, entonces se usa los punteros INICIO que es el que apunta constantemente al primero y el puntero ultimo q es el q apunta constantemente al último.

Ilustración 3. Esquema de una lista simple enlazada.

 

Listas doblemente enlazadas

Una lista doblemente ligada es una colección de nodos, en la cual cada uno de ellos tiene dos apuntadores (fig. 3.1a), uno apuntando a su predecesor (LIGAIZQ) y otro a su sucesor (LIGADER). Por medio de estos punteros se podrá entonces avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntador. La figura 3.1b) representa una lista doblemente ligada que almacena apellidos.

Para tener un fácil acceso a la información de la lista es recomendable usar dos apuntadores, P y F, que apunten al principio y al final de esta, respectivamente.

Ilustración 4. a) Estructura de un nodo.  b) lista doblemente ligada.

  

Listas circulares doblemente enlazadas

Las listas circulares son estructuras de datos en la que el último nodo apunta al primero lo cual la convierte en una lista sin fin, cada nodo siempre tiene uno anterior y uno siguiente, su estructura es muy similar a las listas simples por lo cual comparten características tanto en su implementación como en su manejo aunque requiere un mayor entendimiento del manejo de los punteros.

Tiene las siguientes características:

•          No existe ningún nodo que apunte a null.
•          La lista no tiene fin ya que al llegar al último nodo empieza de nuevo la lista.
•          Se accede a la lista mediante el primer nodo o también llamado inicio de la lista.
•          Si no se tiene cuidado al manejar la lista circular se pueden crear bucles infinitos.
•          No tiene acceso aleatorio es decir para acceder a un valor se debe recorrer toda la lista.

Ilustración 5. Estructura de una lista circular.