Listas con encadenación sencilla
Hemos visto que un arreglo almacena elementos del mismo tipo en posiciones de memoria contiguas. Las listas, por otro lado, constituyen una de las estructuras lineales más flexibles, porque pueden crecer y acortarse según se requiera. La implementación mediante celdas enlazadas por punteros permite esta flexibilidad.
En una lista dinámica con encadenación sencilla (o lista simplemente enlazada), los datos no necesitan estar en posiciones contiguas de la memoria. Cada elemento está contenido en una celda o estructura (o nodo) que se aloja dinámicamente. Cada celda contiene dos partes: el dato y un apuntador que enlaza a la siguiente celda en la lista.
El orden de los elementos en la lista se define por la secuencia de estos apuntadores, desde la primera celda hasta la última. Para acceder a la lista, solo necesitamos un apuntador a la primera celda (llamado cabeza, primero, inicio o first). La última celda se distingue porque su apuntador a la siguiente es NULL.
Apuntadores y memoria dinámica
Los apuntadores son variables que guardan direcciones de memoria. La memoria puede verse como un vector donde cada posición tiene una dirección. La asignación dinámica permite obtener bloques de memoria en tiempo de ejecución. Las funciones malloc, calloc, realloc y free gestionan esta memoria.
En este contexto, se utilizan funciones como new_cell() y delete_cell() para crear y eliminar celdas dinámicamente.
Ejemplo de implementación en C
typedef struct def_Celda {
int dato; // El dato que almacena la celda
struct def_Celda *siguiente; // Apuntador a la siguiente celda
} tipoCelda;
tipoCelda *cabeza = NULL;
El typedef crea un alias tipoCelda para la estructura. El campo dato almacena el valor, y siguiente apunta a la próxima celda.
Inserción en listas enlazadas
1. Insertar al inicio (O(1))
- Crear una nueva celda dinámicamente.
- Asignar el dato a la nueva celda.
- Apuntar su campo
siguientea la celda que apuntacabeza. - Actualizar
cabezapara que apunte a la nueva celda.
2. Insertar al final (O(n))
- Crear una nueva celda con
siguiente = NULL. - Si la lista está vacía,
cabezaapunta a la nueva celda. - Si no está vacía, recorrer la lista hasta encontrar la última celda.
- Hacer que la última celda apunte a la nueva celda.
3. Insertar en medio (O(1) si se tiene la celda anterior)
- Encontrar la celda después de la cual se insertará.
- Crear la nueva celda y asignarle el dato.
- Apuntar su
siguientea la celda siguiente de la anterior. - Actualizar el
siguientede la celda anterior para que apunte a la nueva.
Eliminación de celdas
Es fundamental liberar memoria con free para evitar fugas. La operación erase(p) libera una celda dada, y clear() recorre toda la lista liberando cada celda. La complejidad es:
- erase(p): O(1) si se tiene el apuntador a la celda anterior.
- clear(): O(n) por recorrer toda la lista.
Comprender los apuntadores es clave para manejar listas enlazadas: se manipulan direcciones de memoria para modificar la estructura en tiempo de ejecución, a diferencia de los arreglos que son estructuras de tamaño fijo.