Las listas enlazadas y los arrays son estructuras de datos lineales esenciales. Una lista lineal presenta una estructura lógica continua, pero su representación física en memoria puede variar.

Un array, también conocido como lista secuencial, almacena elementos en direcciones de memoria contiguas. Esto se logra mediante un bloque de memoria asignado estáticamente o dinámicamente, permitiendo accceso directo a cualquier posición mediante índices.

En cambio, una lista enlazada consiste en nodos conectados por punteros. Cada nodo contiene datos y una referencia al nodo siguiente, lo que facilita inserciones y eliminaciones sin necesidad de desplazar elementos, aunque sacrifica el acceso aleatorio.

Implementación de Arrays

Un array dinámico se define con un puntero a los datos, un contador de elementos y la capacidad actual. A continuación, se muestra la estructura y operaciones básicas en C.

typedef int Elemento;
typedef struct {
    Elemento* datos;
    int cantidad;
    int capacidad;
} ArrayDinamico;

void InicializarArray(ArrayDinamico* arr) {
    assert(arr);
    arr->datos = NULL;
    arr->cantidad = 0;
    arr->capacidad = 0;
}

void RedimensionarArray(ArrayDinamico* arr) {
    assert(arr);
    int nuevaCapacidad = arr->capacidad == 0 ? 4 : arr->capacidad * 2;
    Elemento* temp = realloc(arr->datos, nuevaCapacidad * sizeof(Elemento));
    if (!temp) {
        perror("Error en redimensionamiento");
        return;
    }
    arr->datos = temp;
    arr->capacidad = nuevaCapacidad;
}

void InsertarAlFinal(ArrayDinamico* arr, Elemento valor) {
    assert(arr);
    if (arr->cantidad == arr->capacidad) {
        RedimensionarArray(arr);
    }
    arr->datos[arr->cantidad] = valor;
    arr->cantidad++;
}

void EliminarDelFinal(ArrayDinamico* arr) {
    assert(arr);
    if (arr->cantidad > 0) {
        arr->cantidad--;
    }
}

void DestruirArray(ArrayDinamico* arr) {
    assert(arr);
    free(arr->datos);
    arr->datos = NULL;
    arr->cantidad = 0;
    arr->capacidad = 0;
}

Estas operaciones ilustran cómo manejar un array dinámico, incluyendo redimensionamiento para evitar desbordamientos.

Implementación de Listas Enlazadas

Una lista enlazada simple se compone de nodos, cada uno con datos y un puntero al siguiente nodo. La implementación requiere punteros dobles para modificar la cabeza de la lista.

typedef int Dato;
typedef struct Nodo {
    Dato informacion;
    struct Nodo* siguiente;
} Nodo;

Nodo* CrearNodo(Dato valor) {
    Nodo* nuevo = malloc(sizeof(Nodo));
    assert(nuevo);
    nuevo->informacion = valor;
    nuevo->siguiente = NULL;
    return nuevo;
}

void InsertarAlInicio(Nodo** cabeza, Dato valor) {
    assert(cabeza);
    Nodo* nuevo = CrearNodo(valor);
    nuevo->siguiente = *cabeza;
    *cabeza = nuevo;
}

void InsertarAlFinal(Nodo** cabeza, Dato valor) {
    assert(cabeza);
    Nodo* nuevo = CrearNodo(valor);
    if (!*cabeza) {
        *cabeza = nuevo;
        return;
    }
    Nodo* actual = *cabeza;
    while (actual->siguiente) {
        actual = actual->siguiente;
    }
    actual->siguiente = nuevo;
}

void EliminarCabeza(Nodo** cabeza) {
    assert(cabeza && *cabeza);
    Nodo* temp = *cabeza;
    *cabeza = (*cabeza)->siguiente;
    free(temp);
}

Nodo* BuscarNodo(Nodo* cabeza, Dato objetivo) {
    Nodo* actual = cabeza;
    while (actual) {
        if (actual->informacion == objetivo) {
            return actual;
        }
        actual = actual->siguiente;
    }
    return NULL;
}

void DestruirLista(Nodo** cabeza) {
    assert(cabeza);
    Nodo* actual = *cabeza;
    while (actual) {
        Nodo* siguiente = actual->siguiente;
        free(actual);
        actual = siguiente;
    }
    *cabeza = NULL;
}

Esta lista enlazada simple no permite navegación hacia atrás y requiere recorridos para operaciones como inserción al final.

Comparación y Consideraciones

Los arrays ofrecen acceso rápido por índice y eficiencia en inserciones al final, pero su redimensionamiento puede ser costoso. Las listas enlazadas facilitan inserciones y eliminaciones en cualquier posición sin desplazamiento, pero carecen de acceso aleatorio y tienen sobred por los punteros.

En cuanto a rendimiento, los arrays aprovechan la localidad de memoria, mejorando el uso de caché del CPU. Las listas enlazadas son ideales para aplicaciones con operaciones frecuentes de inserción y eliminación, especialmente cuando el tamaño de los datos es dinámico.