Ejemplo simple de Lista Ligads (Linked List)

El objetivo de este post es dar una explicación lo más simple que me sea posible de qué es una Lista Ligada o Linked List y cómo crear una. La explicación e implementación de la Lista Ligada va a ser en C y C++ explicando las diferencias entre la implementación en cada uno de los lenguajes.

Una Lista Ligada (o lista enlazada) es tipo de estructura de datos y se utiliza para almacenar información. Una Lista Ligada está compuesta por dos partes principales, los datos y un apuntador del mismo tipo de la estructura. Una representación visual se muestra a continuación y le vamos a llamar "Nodo":

En nuestro nodo tenemos que "Datos" contiene el tipo de dato que queremos almacenar en nuestra lista ligada, por ejemplo un entero, un doble, un caracter, etc. y "Siguiente" es un apuntador a otro "Nodo" del mismo tipo. La definición en C y C++ se puede hacer mediante una estructura (en C++ también se puede crear con una clase):

// En C

struct nodo

{

 int dato;

 struct nodo *siguiente;

};

// En C++

struct nodo

{

 int dato;

 nodo *siguiente;

};

Y podemos representar a una lista ligada de manera gráfica como se muestra a continuación:

Primero se crea un nodo y se inicializa apuntando a una dirección nula.

struct nodo* A = NULL; // En C

nodo* A = NULL; // En C++

Y después tenemos que alojar en memoria el nodo que hemos creado, esto lo hacemos mediante "malloc" en C y con "new" en C++:

A = (struct nodo*)malloc(sizeof(struct nodo)); // En C

A = new nodo; // En C++

De esta manera ya tenemos creado un nodo y de esta misma manera se pueden crear varios nodos y enlazarlos mediante sus apuntadores y direcciones. A continuación se explica mediante la implementación en C:

#include

#include

struct nodo

{

 int dato;

 struct nodo *siguiente;

};

// En este ejemplo vamos a crear una lista ligada de tres nodos

int main()

{

 struct nodo* A = NULL;

 struct nodo* B = NULL;

 struct nodo* C = NULL;

 // Alojamos los tres nodos en memoria

 A = (struct nodo*)malloc(sizeof(struct nodo));

 B = (struct nodo*)malloc(sizeof(struct nodo));

 C = (struct nodo*)malloc(sizeof(struct nodo));

 A->dato = 100; //le asignamos un valor a "dato" del primer nodo

 A->siguiente = B; // Ligamos el apuntador "siguiente" al nodo "B"

 B->dato = 200; //le asignamos un valor al "dato" del segundo nodo

 B->siguiente = C; // Ligamos el apuntador "siguiente" al nodo "C"

 C->dato = 300; //le asignamos un valor al "dato" del tercer nodo

 C->siguiente = NULL; // Asignamos el apuntador "siguiente" a Null

                     // para indicar que es el final de la lista    

 return 0;

}

En el ejemplo anterior podemos observar que solamente necesitamos la saber la información de "A" para acceder a los demás elementos de nuestra lista.

Para demostrar esto, podemos crear una función que recibe como parámetro el primer

nodo de nuestra lista ligada e imprime en la consola el "dato" guardado en cada uno de los elementos de la lista.

La implementación completa sería:

#include

#include

struct nodo

{

 int dato;

 struct nodo *siguiente;

};

// Funcion que imprime en pantalla todos los datos de la lista a partir

// del primer elemento de la lista

void imprimir_lista(struct nodo *n)

{

 while (n != NULL)

 {

    printf(" %d ", n->dato);

    n = n->siguiente;

 }

}

// En este ejemplo vamos a crear una lista ligada de tres nodos

int main()

{

 struct nodo* A = NULL;

 struct nodo* B = NULL;

 struct nodo* C = NULL;

 // Alojamos los tres nodos en memoria

 A = (struct nodo*)malloc(sizeof(struct nodo));

 B = (struct nodo*)malloc(sizeof(struct nodo));

 C = (struct nodo*)malloc(sizeof(struct nodo));

 A->dato = 100; //le asignamos un valor a "dato" del primer nodo

 A->siguiente = B; // Ligamos el apuntador "siguiente" al nodo "B"

 B->dato = 200; //le asignamos un valor al "dato" del segundo nodo

 B->siguiente = C; // Ligamos el apuntador "siguiente" al nodo "C"

 C->dato = 300; //le asignamos un valor al "dato" del tercer nodo

 C->siguiente = NULL; // Asignamos el apuntador "siguiente" a Null

                     // para indicar que es el final de la lista    

 imprimir_lista(A);

 return 0;

}

La implementación de la lista anterior en C++ sería como se muestra a continuación:

#include

struct nodo

{

 int dato;

 nodo *siguiente;

};

// Funcion que imprime en pantalla todos los datos de la lista a partir

// del primer elemento de la lista

void imprimir_lista(struct nodo *n)

{

 while (n != NULL)

 {

    cout << n->dato << endl;

    n = n->siguiente;

 }

}

// En este ejemplo vamos a crear una lista ligada de tres nodos

int main()

{

 nodo* A = NULL;

 nodo* B = NULL;

 nodo* C = NULL;

 // Alojamos los tres nodos en memoria

 A = new nodo;

 B = new nodo;

 C = new nodo;

 A->dato = 100; //le asignamos un valor a "dato" del primer nodo

 A->siguiente = B; // Ligamos el apuntador "siguiente" al nodo "B"

  

 B->dato = 200; //le asignamos un valor al "dato" del segundo nodo

 B->siguiente = C; // Ligamos el apuntador "siguiente" al nodo "C"

 C->dato = 300; //le asignamos un valor al "dato" del tercer nodo

 C->siguiente = NULL; // Asignamos el apuntador "siguiente" a Null

                     // para indicar que es el final de la lista    

 imprimir_lista(A);

 return 0;

}

Y gráficamente podemos representar la lista creada de la siguiente manera: