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:
