Lista Simplemente Enlazada

Concepto

Una lista es tipo de estructura de datos en programación, que permite organizar y almacenar múltiples datos (nodos), en un orden secuencial. Cada nodo se encuentra enlazado a otro y tiene una o más referencias (punteros) al elemento anterior o posterior. Las listas permiten almacenar y procesar datos de manera ordenada y dinámica, sin necesidad de conocer inicialmente el tamaño de su estructura.

A continuación, un ejemplo del concepto dado.

Al representar una lista simplemente enlazada mediante estas cajas, es fácil darse cuenta que para agregar más datos, es cuestión de agregar una nueva caja sea al principio, al final o en cualquier parte y hacerle su correspondiente enlace. Además, es posible modificar los datos almacenados en las cajas, también eliminar/quitar cualquier caja en caso de no necesitarla (ej. Si se quita caja 2, caja 1 se enlaza con caja 3 y esta ultima pasa a ser la nueva caja 2), por ultimo, cada caja tiene un numero (posición en la lista) así que es posible buscar datos ubicándolos según su posición correspondiente.

Declaración

Para declarar una lista en C++, es necesario crear una estructura Nodo. Dicha estructura esta constituida por dos partes, la primera corresponde al dato o los datos que se vayan a almacenar en la lista, y la segunda corresponde a la referencia, es decir, un apuntador al Nodo siguiente.

struct Nombre{

//dato(s)

tipo_dato nombre;

…

//apuntador al nodo siguiente

Nombre *siguiente;

};

Debajo de la estructura Nodo, es común que algunos programadores declaren dos punteros referenciales tales que *inicio y *final; *primero y *ultimo entre otros, más que nada para controlar si la lista está vacía o no al determinar cuál elemento se encuentra al principio o al final de esta. En cualquier caso, ambos punteros referenciales se igualan a NULL, esto es, una palabra reservada del lenguaje utilizada para indicar que una variable/apuntador no tiene ningún valor (es nulo) y en este caso NULL indica además el final de la lista.

El resultado quedaría así:

struct Nodo{

//dato(s)

int edad;

string nombre;

//apuntador al nodo siguiente

Nodo *siguiente;

};

Nodo *primero = NULL;

Nodo *ultimo = NULL;

Operaciones Básicas

Una lista simplemente enlazada admite 5 operaciones básicas: insertar, eliminar, imprimir, buscar y modificar. En cuanto a primera operación, insertar, existen tres distintas formas de agregar un elemento a una lista: al principio, al final o en cualquier parte.

Importante: ya que las listas utilizan memoria dinámica, durante la explicación de las operaciones básicas verá palabras como:

new - palabra reservada de C++ para asignar espacio en memoria a una variable/apuntador. Y

delete - palabra reservada de C++ para liberar el espacio en memoria ocupado por una variable/apuntador que ya no se utilizará más.

Insertar al Principio

1. Para insertar un elemento al principio de la lista, Crea un nuevo nodo y asigna el elemento que deseas insertar al miembro correspondiente del nodo.

2. Verifica si la lista está vacía. Puedes hacer esto comprobando si el puntero primero es igual a NULL.

3. Si la lista está vacía, asigna el nuevo nodo al puntero primero y establece su puntero siguiente (sig) en NULL.

4. Si la lista no está vacía, asigna el nodo actualmente apuntado por primero como el nodo siguiente del nuevo nodo. Luego, actualiza el puntero primero para que apunte al nuevo nodo.

Insertar al Final

1. Crea un nuevo nodo y asigna el elemento que deseas insertar al miembro correspondiente del nodo.

2. Verifica si la lista está vacía. Puedes hacer esto comprobando si el puntero primero es igual a NULL.

3. Si la lista está vacía, asigna el nuevo nodo tanto al puntero primero como al puntero ultimo, y establece su puntero siguiente (sig) en NULL.

4. Si la lista no está vacía, asigna el nuevo nodo al puntero siguiente (sig) del nodo actualmente apuntado por ultimo. Luego, actualiza el puntero ultimo para que apunte al nuevo nodo.

Insertar en Cualquier Parte

1. Crea un nuevo nodo y asigna el elemento que deseas insertar al miembro correspondiente del nodo.

2. Se verifica si la lista está vacía. Esto se comprueba verificando si el puntero "primero" es igual a NULL.

3. Si la lista esta vacía, el nuevo nodo se convierte en el primer y último nodo de la lista. Se establece el puntero siguiente (sig) del nuevo nodo en NULL y se asigna el nuevo nodo tanto al puntero "primero" como al puntero "ultimo".

4. Si la lista no está vacía, se muestra un menú de opciones al usuario para elegir dónde insertar el nuevo nodo: al inicio, en una posición específica o al final.

5. Si se elige la opción 1, se inserta el nuevo nodo al inicio de la lista. Se asigna el puntero "primero" como el siguiente nodo del nuevo nodo y se actualiza el puntero "primero" para que apunte al nuevo nodo.

6. Si se elige la opción 2, se solicita al usuario que ingrese la posición en la que desea insertar el nuevo nodo. Se utiliza un bucle while para avanzar por la lista hasta llegar a la posición deseada. Si la posición es mayor que la longitud actual de la lista, el bucle se detiene y el nuevo nodo se inserta al final de la lista. De lo contrario, se inserta el nuevo nodo en la posición especificada. Para hacer esto, se asigna el puntero siguiente (sig) del nuevo nodo al puntero siguiente (sig) del nodo actual y se asigna el nuevo nodo como el siguiente nodo del nodo actual.

7. Si se elige la opción 3, se inserta el nuevo nodo al final de la lista. El puntero siguiente (sig) del nuevo nodo se establece en NULL y se asigna el nuevo nodo como el siguiente nodo del nodo actualmente apuntado por "ultimo". Luego, se actualiza el puntero "ultimo" para que apunte al nuevo nodo.

8. Si se elige una opción inválida (diferente de 1, 2 o 3), se muestra un mensaje de error y se elimina el nodo creado previamente utilizando el operador delete. Esto se hace para evitar fugas de memoria.

Eliminar

1. Crea dos punteros de tipo Nodo, actual y anterior, y los inicializa con los valores correspondientes: actual se inicializa apuntando al primer nodo de la lista (primero), mientras que anterior se inicializa como NULL.

2. Comienza un bucle while que continúa mientras el puntero actual no sea NULL, lo que significa que aún hay nodos por revisar en la lista.

3. En cada iteración del bucle:

Se compara el código del nodo apuntado por actual con el dato ingresado por el usuario.
Si los datos coinciden, significa que se ha encontrado el nodo a eliminar.
Se comprueba si anterior es NULL, para saber si nodo a eliminar es el primer nodo de la lista.
Si es así, se actualiza el puntero primero para que apunte al siguiente nodo de la lista (actual->siguiente), saltando así el nodo a eliminar.
Si anterior no es NULL, significa que el nodo a eliminar está en el medio o al final de la lista.
Entonces, se actualiza el puntero siguiente del nodo apuntado por anterior para que apunte al siguiente nodo después de actual, eliminando así actual de la lista.
Se libera la memoria ocupada por el nodo a eliminar utilizando el operador delete.
Se imprime un mensaje indicando que el registro se ha eliminado exitosamente.
Finaliza la función utilizando la instrucción return.
Si los datos no coinciden, se actualizan los punteros anterior y actual para pasar al siguiente nodo en la lista.

5. Si el bucle while se completa sin encontrar el nodo a eliminar, significa que no existe un nodo con el código proporcionado en la lista.

Colocar imagen acá...

Imprimir

1- Crea un nuevo nodo y asigna el elemento que deseas mostrar al miembro correspondiente del nodo.

2- Se verifica si el puntero "primero" es diferente de NULL para determinar si la lista está vacía. Si es NULL, significa que no hay nodos en la lista lo cual significa que la lista está vacía.

3- Si la lista no está vacía, muestra el elemento almacenado en el primer nodo.

4- Mueve el puntero al siguiente nodo en la lista. Esto se puede realizar asignando el puntero siguiente (siguiente) del nodo actual al puntero actual (es decir, asignando actual = actual->siguiente).

5- Verifica si el puntero actual ha alcanzado el final de la lista. Si el puntero actual es NULL, significa que has llegado al final de la lista y el proceso de mostrar termina. Si el puntero actual no es NULL, regresa al paso 2 y continúa mostrando los elementos en los nodos restantes de la lista.

Buscar

1- Crea un nuevo nodo y asigna el elemento que deseas buscar al miembro correspondiente del nodo.

2- Compara el valor buscado con el valor almacenado en el nodo actual.

3- Si los valores son iguales, significa que se ha encontrado el elemento que se busca.

4- Si los valores no son iguales, avanza al siguiente nodo de la lista. Esto se puede hacer actualizando el puntero al siguiente nodo.

5- Se verifica si se ha alcanzado el final de la lista. Si el puntero al siguiente nodo es NULL, significa que se ha recorrido toda la lista y no se ha encontrado el elemento buscado.

6- Si no se ha alcanzado el final de la lista, se repiten los pasos 2 a 5 hasta que se encuentre el elemento buscado o se llegue al final de la lista.

Modificar

1- Crea un nuevo nodo y asigna el elemento que deseas buscar al miembro correspondiente del nodo.

2- Se avanza a través de los nodos utilizando un puntero que apunte al primer nodo y se desplace a través de los punteros siguientes (sig) de cada nodo.

3-Mientras se avanza por la lista, se verifica si el elemento actual coincide con el elemento que deseas modificar.

4- Si se encuentra el elemento que se desea modificar, se actualiza el miembro correspondiente del nodo con el nuevo valor que se desea asignar.

5- Una vez que se haya realizado la modificación, se puede finalizar el procedimiento.

Ejemplo de lista simplemente enlazada en C++