Estructura de Datos: Lista Simplemente Enlazada

En programación, una lista simplemente enlazada es una estructura de datos, similar a los arreglos, pero contando con importantes diferencias que la convierten en una mejor opción a utilizar en determinadas situaciones.

Asímismo, la lista simplemente enlazada es una de las estructuras de datos básicas con la que después podremos crear otras estructuras de datos más complejas, como la lista circular o la pila.

A continuación te mostraré que son las listas enlazadas y sus ventajas, sus funciones base y como programarlas en C.

¿Qué es una lista enlazada?

Lista simplemente enlazada - Diagrama

Una lista simplemente enlazada es una estructura de datos lineal, como los arreglos, aunque a diferencia de estos, sus elementos se encuentran relacionados (enlazados) por medio de punteros, mientras que en los arreglos sus elementos se encuentran en espacios de memoria consecutivos.

Gracias a lo anterior, la lista simplemente enlazada es una estructura de datos de tamaño dinámico, es decir, no esta limitada a un tamaño inicial y puede crecer indefinidamente mientras haya espacio de memoria disponible en el equipo.

Otra ventaja es su fácilidad para añadir nuevos elementos en partes intermedias de la lista, ya que sólo es necesario cambiar el apuntador que sirve de enlace entre el elemento anterior y el elemento siguiente al insertado; mientras que en un arreglo, tendríamos que recolocar todos los elementos que le siguen a la posición que queramos agregar.

Lista Simplemente Enlazada - Insertar nodos

Listas enlazadas vs arreglos:

Ventajas de las listas enlazadas:

  • Tamaño dinámico
  • Es sencillo agregar y eliminar elementos

Gracias a su tamaño dinámico y fácilidad de gestión de los elementos, las listas simplemente enlazadas requieren de menos poder de procesamiento para efectuar sus operaciones frente a los arreglos.

Desventajas de las listas enlazadas:

  • Los elementos deben ser accedidos secuencialmente
  • Requiere de más espacio en memoria al requerir almacenar un valor + el puntero de la siguiente posición

Al tener que ser accedidas de forma secuencial, algoritmos como Quicksort o búsqueda binaria no pueden aplicarse a las listas enlazadas.

Operaciones básicas de la lista simplemente enlazada

Las operaciones básicas con las que debe contar una lista enlazada son las siguientes:

  • Insertar nodos
  • Eliminar nodos
  • Ver lista
  • Buscar un valor

A continuación te mostraré como programar cada una de estas funciones en una lista simplemente enlazada usando C.

Lista simplemente enlazada en C

La lista enlazada consiste en la unión de varios “nodos” mediante enlaces, cada uno cuenta con la siguiente estructura:

  • Datos o valores que almacenará el nodo
  • Puntero hacía el siguiente nodo

De esta forma, la estructura de un nodo en C queda de la siguiente forma:

Ejemplo Lista simplemente enlazada en C

Un ejemplo de lista enlazada simple es el siguiente, donde existen tres nodos apuntando hacía el siguiente nodo en la lista:

Operaciones básicas de la lista enlazada simple en C

Imprimir el contenido de la lista

Esta operación, como su nombre lo indica, consiste en una función que permita mostrar todos los elementos dentro de la lista enlazada a partir de un punto de inicio sin alterar el orden de sus elementos.

Una forma de lograr lo anterior es definir un nodo n que ciclicamente tome el valor de cada nodo de la lista para después imprimir su contenido.

En el código anterior, la función imprimir recibe como argumento un nodo, el cual será tomado como punto de inicio de la lista y a partir de donde se comenzará a imprimir el contenido de todos los nodos restantes.

Dentro del cuerpo de la función, se define un ciclo que imprimirá los datos, donde un nodo n es inicializado en la primera posicion de la lista, y que continuará iterando mientras n no sea igual a NULL (Ya que NULL marcará el final de la lista). Con cada iteración, el valor de n cambiará para pasar al siguiente nodo de la lista.

Busquéda

La operación de búsqueda consiste en buscar un dato dentro de la lista enlazada, como los elementos de la línea están unidos por medio de punteros, sólo es posible realizar una búsqueda secuencial en la lista.

La siguiente función realiza lo anterior, retornando el índice donde se encuentra el valor en caso de ser encontrado.

En el código anterior, la función buscar recibe como argumento el nodo que será tomado como punto de inicio de la lista y el valor a buscar dentro de esta.

Posteriormente inicializamos una variable i que nos indicará el índice donde se encuentra el valor dentro de la lista.

El ciclo inicializa un nodo n que permite recorrer la lista desde el inicio, y que continuará haciendolo hasta que llegue al final de la lista (NULL). Con cada iteración n pasará a ser el siguiente elemento dentro de la lista y i aumentará en uno su valor.

Dentro del cuerpo del ciclo, se compara el valor buscado con los datos almacenados en cada nodo, en caso de encontrarse, se regresa el valor del índice donde se encuentra el valor. Si el valor no es encontrado, se retorna -1.

Insertar nodos

Añadir nodos a una lista enlazada requiere que estos elementos puedan insertarse en cualquier punto de la lista, por lo que utilizaremos tres funciones para esto:

  • Insertar nodo al frente de la lista
  • Insertar nodo dentro de la lista
  • Insertar nodo al final de la lista
Insertar nodo al frente de la lista

Esta función nos permitirá insertar un nodo al inicio de la lista, reemplazando al frente de esta. Esta operación también es conocida como PUSH, y queda ilustrada en el siguiente diagrama:

A continuación, puedes ver el código con los pasos necesarios para desarrollar esta función:

Habrás notado que en la función anterior he utilizado un puntero a un puntero (struct Nodo** frente), esto es necesario para poder modificar el valor del puntero que es pasado a la función como argumento; pasar el puntero struct Nodo** frente a la función nos permite modificar el puntero struct Nodo* frente.

Insertar nodo dentro de la lista

Para insertar un nodo dentro de la lista, será necesario recorrer la lista secuencialmente hasta llegar a la posición donde insertaremos el nodo, posteriormente cambiar el apuntador del nodo previo y el nuevo nodo.

Puedes ver una representación visual en el siguiente diagrama:

En código:

Insertar nodo al final de la lista

Insertar un nodo al final de la lista no es muy diferente a las otras funciones; de nuevo necesitaremos un nodo de referencia para comenzar a recorrer la lista y un valor que almacenará nuestro nuevo nodo.

Para insertar al final de la lista nuestro último nodo deberá apuntar hacía nuestro nuevo nodo, y este último hacía NULL para marcar el final de la lista.

Diagrama:

Código:

Eliminar nodos

Eliminar nodos en una lista simplemente enlazada es un proceso en el que debemos encontrar el nodo previo al que queremos eliminar, cambiar su apuntador y liberar la memoria del nodo que vamos a eliminar.

Utilizando una sola función, lo podemos realizar de la siguiente manera:

De esta forma, ya contaremos con las operaciones básicas de una lista simplemente enlazada, a continuación una función utilizando las funciones de inserción y eliminación de nodos:

Fuente parcial: Geeksforgeeks.com

Archivo completo en Github.com

Share Post :

More Posts