Listas Ligadas

Una lista ligada es un artificio de programación utilizado como estructura de datos, donde cada elemento de la lista es un conjunto de datos q apunta o esta enlazado al siguiente y/o anterior elemento de la lista. Si bien en un arreglo pueden agregarse, eliminarse, ordenarse (entre otras operaciones) los elementos de una lista a través de la re asignación dinámica de memoria, estas tareas son complejas y poco prácticas, por lo tanto los arreglos son utilizados generalmente sólo como estructuras de datos estáticas. Por el contrario las listas ligadas son estructuras dinámicas donde las operaciones sobre los elementos de la lista son más faciles de llevar acabo. En el tipo más básico de listas ligadas cada elemento apunta o contiene la dirección del siguiente elemento de la lista. El siguiente diagrama muestra una conceptualización de esta estructura de datos:



Esta es una lista unidireccional donde cada elemento de la misma apunta solo al siguiente elemento, el ultimo apunta a nada, ademas de que se debe tener un apuntador al primer elemento de la lista, siendo útil contar con un apuntador para almacenar algún elemento o item de la lista como actual o activo.

En C++ la implementación de una lista podría ser de la siguiente manera:

1. Para administrar la lista, como la creación de nodos, la eliminación de nodos, el ordenamiento, la destrucción de la lista, etc. puede llavarse a cabo mediante la definición de una clase y sus métodos.

2. Como elemento de la lista se puede definir una estructura, una clase, o una clase + una estructura, en este último paradigma la clase podría servirnos para llevar a acabo operaciones sobre los datos del nodo de la lista, mientras q la estrucutura se ocuparía sólo para almacenar los datos del nodo. A continuación se muestra la creación de una lista ligada fundamental en C++ donde usaremos una clase para la administración de la lista y una estructura para los datos del nodo, posteriormente se mencionaran otro tipo de listas ligadas.

Primero definimos la clase, en este ejemplo la llamaremos CLista y definiremos los métodos para crear un nodo, eliminar un nodo, limpiar la lista, ir al primer elemento, ir al último elemento, ir al siguiente elemento e ir a un elemento deseado. No olvidemos declarar antes la estructura para almacenar los datos del nodo, la llamaremos SDatos y posteriormente definiremos sus campos pero por el momento diremos que serán necesario un campo numérico para almacenar el ID secuencial del nodo y el apuntador de tipo SDato para almacenar la dirección del elemento contiguo o siguiente de la lista.

Bien, la declaración de la clase sería:

struct SDatos;

class CLista{
public:
SDatos *Nodo;  //Contendra, digamoslo asi, el nodo actual de la lista
void CreaNodo();
void EliminaNodo();
void Siguiente();
void Anterior();
void Primero();
void Ultimo();
void DameNodo(unsigned long);
void LimpiarLista();
unsigned long TotalNodos();  //Encapsulamos el numero total de nodos de tal forma que no se pueda fuera de la clase sobreescribir este dato solamente leer
CLista();
~CLista();
private:
unsigned long TotNod;
SDatos *Lista;  //Almacena el inicio o primer nodo de la lista
void Renumera();
};

Y la definición de cada uno de sus métodos:

CLista::CLista()
{
Lista = NULL;
Nodo = NULL;
TotNod = 0;
}

CLista::~CLista()
{
LimpiarLista();
}

void CLista::CreaNodo()
{
UltimoNodo();
if(Nodo)
{
Nodo->Sig = new SDatos;
Nodo = Nodo->Sig;
}
else
{ 

//Es el primer nodo de la lista
Lista = new SDatos;
Nodo = Lista;
}
Nodo->Sig = NULL;
TotNod++;
Nodo->No = TotNod;
}

void CLista::EliminaNodo()
{
SDatos *Act = Nodo;
if(Nodo)
{
if(Nodo==Lista)
{
Lista = Nodo->Sig;
Nodo = Lista;
}
else
{
Anterior();
Nodo->Sig = Act->Sig;
}
delete Act;
TotNod--;
Renumera();
}
}

void CLista::Siguiente()
{
if(Nodo)
Nodo = Nodo->Sig;
}

void CLista::Anterior()
{
unsigned long QueNodo = 0;
if(Lista)
if(Nodo != Lista)
{
if(!Nodo)
QueNodo = TotNod;
else
QueNodo = Nodo->No-1;
DameNodo(QueNodo);
}
}

void CLista::Primero()
{
Nodo = Lista;
}

void CLista::Ultimo()
{
DameNodo(TotNod);
}

void CLista::DameNodo(unsigned long ANo)
{
if(ANo<1)
ANo = 1;
if(ANo > TotNod)
ANo = TotNod;
Primero();
while(Nodo && Nodo->No != ANo)
Siguiente();
}

void CLista::LimpiarLista()
{
Primero();
while(Nodo)
{
Lista = Nodo->Sig;
delete Nodo;
Nodo = Lista;
}
TotNod = 0;
}

unsigned long CLista::TotalNodos()
{
return TotNod;
}

void CLista::Renumera()
{
SDatos *Act = Nodo;
unsigned long Cont = 0;
Primero();
while(Nodo)
{
Cont++;
Nodo->No = Cont;
Siguiente();
}
TotNod = Cont;
Nodo = Act;
}

La definición de la estructura para almacenar los datos puede contener los campos que sean necesarios para la aplicación, la lista ligada funcionara igual, pero al menos debe contener un apuntador de la misma estructura y un campo entero como ID del nodo.

struct SDatos{
.
.
.
unsigned long No;
SDatos *Sig;
SDatos
{
:
:
No = 0;
Sig = NULL;
}
};

Este es el tipo de lista ligada básica, entre otros tipos de lista podemos mencionar:

1. Lista bidireccional



2. Lista circular unidireccional



3. Lista circular bidireccional



Las listas bidireccionales requeriran un apuntador extra en la estructura de datos para apuntar al elemento adyacente anterior de la lista, aunque si bien hablamos de adyacencia de elementos de la lista esta es puramente lógica ya q en memoria los nodos podrían estar dispersos en cierta región de la misma. Este es un caso contrario a los arreglos cuyos elementos ocupan regiones adyacentes de memoria.