5. Listas Ligadas

#estructuraDeDatos #universidad

a. Listas Enlazadas

Una lista enlazada es una estructura de datos dinámica compuesta por nodos, donde cada nodo contiene datos y una referencia (puntero) al siguiente nodo en la secuencia. A diferencia de los arreglos, las listas enlazadas permiten inserciones y eliminaciones eficientes en cualquier posición.

Ventajas de las Listas Enlazadas:

• Inserciones y eliminaciones eficientes: No requieren desplazar elementos.
• Tamaño dinámico: Pueden crecer y decrecer según sea necesario.

Desventajas de las Listas Enlazadas:

• Acceso secuencial: No permiten acceso aleatorio eficiente.
• Mayor uso de memoria: Requieren almacenamiento adicional para los punteros.

b. Clasificación de las Listas Enlazadas

1. Listas Enlazadas Simples:
   • Cada nodo tiene un único puntero al siguiente nodo.
   • Navegación unidireccional.

[Dato | Siguiente] → [Dato | Siguiente] → NULL

2. Listas Enlazadas Dobles:
   • Cada nodo tiene dos punteros: uno al siguiente y otro al nodo anterior.
   • Navegación bidireccional.

NULL ← [Anterior | Dato | Siguiente] ↔ [Anterior | Dato | Siguiente] ↔ NULL

3. Listas Enlazadas Circulares:

• El último nodo apunta al primero, formando un ciclo.
• Puede ser simple o doble.

Lista Enlazada Simple Circular:

[Dato | Siguiente] → [Dato | Siguiente] → ... → [Dato | Siguiente] ─┐
└───────────────────────────────────────────────────────────────────────┘

Lista Enlazada Doble Circular:

... ↔ [Anterior | Dato | Siguiente] ↔ ...
↔ NULL ← [Anterior | Dato | Siguiente] ↔ NULL

c. Insertar un Elemento en una Lista

Insertar al Inicio (Listas Enlazadas Simples)

#include <stdio.h>
#include <stdlib.h>

// Definición del nodo
typedef struct Nodo {
    int dato;
    struct Nodo *siguiente;
} Nodo;

// Función para crear un nuevo nodo
Nodo* crearNodo(int valor) {
    Nodo *nuevo = (Nodo*)malloc(sizeof(Nodo));
    if (!nuevo) {
        printf("Error en la asignación de memoria.\n");
        exit(1);
    }
    nuevo->dato = valor;
    nuevo->siguiente = NULL;
    return nuevo;
}

// Insertar al inicio
Nodo* insertarInicio(Nodo *cabeza, int valor) {
    Nodo *nuevo = crearNodo(valor);
    nuevo->siguiente = cabeza;
    return nuevo;
}

// Función para imprimir la lista
void imprimirLista(Nodo *cabeza) {
    Nodo *actual = cabeza;
    while (actual != NULL) {
        printf("%d -> ", actual->dato);
        actual = actual->siguiente;
    }
    printf("NULL\n");
}

// Ejemplo de uso
int main() {
    Nodo *cabeza = NULL;
    
    cabeza = insertarInicio(cabeza, 30);
    cabeza = insertarInicio(cabeza, 20);
    cabeza = insertarInicio(cabeza, 10);
    
    imprimirLista(cabeza); // Imprime: 10 -> 20 -> 30 -> NULL
    
    return 0;
}

Insertar al Final (Listas Enlazadas Simples)

// Insertar al final
Nodo* insertarFinal(Nodo *cabeza, int valor) {
    Nodo *nuevo = crearNodo(valor);
    if (cabeza == NULL) {
        return nuevo;
    }
    Nodo *actual = cabeza;
    while (actual->siguiente != NULL) {
        actual = actual->siguiente;
    }
    actual->siguiente = nuevo;
    return cabeza;
}

d. Búsqueda de un Elemento en una Lista

// Buscar un elemento en la lista
Nodo* buscarElemento(Nodo *cabeza, int valor) {
    Nodo *actual = cabeza;
    while (actual != NULL) {
        if (actual->dato == valor) {
            return actual;
        }
        actual = actual->siguiente;
    }
    return NULL; // No encontrado
}

// Ejemplo de uso
int main() {
    Nodo *cabeza = NULL;
    
    cabeza = insertarInicio(cabeza, 30);
    cabeza = insertarInicio(cabeza, 20);
    cabeza = insertarInicio(cabeza, 10);
    
    imprimirLista(cabeza); // Imprime: 10 -> 20 -> 30 -> NULL
    
    int valor = 20;
    Nodo *resultado = buscarElemento(cabeza, valor);
    if (resultado != NULL) {
        printf("Elemento %d encontrado.\n", valor);
    } else {
        printf("Elemento %d no encontrado.\n", valor);
    }
    
    return 0;
}

e. Borrar un Elemento de la Lista

// Borrar un elemento de la lista
Nodo* borrarElemento(Nodo *cabeza, int valor) {
    Nodo *actual = cabeza;
    Nodo *anterior = NULL;
    
    while (actual != NULL && actual->dato != valor) {
        anterior = actual;
        actual = actual->siguiente;
    }
    
    if (actual == NULL) {
        printf("Elemento %d no encontrado.\n", valor);
        return cabeza;
    }
    
    if (anterior == NULL) {
        // El elemento está en la cabeza
        Nodo *temp = cabeza;
        cabeza = cabeza->siguiente;
        free(temp);
    } else {
        anterior->siguiente = actual->siguiente;
        free(actual);
    }
    
    return cabeza;
}

// Ejemplo de uso
int main() {
    Nodo *cabeza = NULL;
    
    cabeza = insertarInicio(cabeza, 30);
    cabeza = insertarInicio(cabeza, 20);
    cabeza = insertarInicio(cabeza, 10);
    
    imprimirLista(cabeza); // Imprime: 10 -> 20 -> 30 -> NULL
    
    cabeza = borrarElemento(cabeza, 20);
    imprimirLista(cabeza); // Imprime: 10 -> 30 -> NULL
    
    cabeza = borrarElemento(cabeza, 10);
    imprimirLista(cabeza); // Imprime: 30 -> NULL
    
    cabeza = borrarElemento(cabeza, 40); // Elemento no encontrado
    
    return 0;
}

f. Resumen de Listas Ligadas

• Listas Enlazadas Simples: Navegación unidireccional.
• Listas Enlazadas Dobles: Navegación bidireccional.
• Listas Enlazadas Circulares: Forman ciclos, pueden ser simples o dobles.
• Operaciones Clave: Insertar, buscar y borrar elementos.

Ejercicios

1. Lista Enlazada Doble:

   • Implementa una lista enlazada doble en C que permita insertar y eliminar elementos tanto al inicio como al final de la lista.

2. Eliminar Duplicados:

   • Escribe una función en C que elimine todos los elementos duplicados de una lista enlazada simple.

3. Revertir una Lista Enlazada:

   • Implementa una función en C que invierta una lista enlazada simple sin utilizar memoria adicional.