Estructura de Datos: Introducción a Listas Secuenciales con Guía Práctica

1. Conceptos Básicos de Estructuras de Datos

Antes de profundizar en las listas secuenciales, es importante entender qué son las estructuras de datos.

1.1 ¿Qué son las Estructuras de Datos?

Una estructura de datos combina "datos" y "estructura". Los datos incluyen números, información de usuarios o contenido multimedia. La estructura organiza estos datos para facilitar su manejo. Por ejemplo, un corral organiza ovejas de manera eficiente, mientras que encontrar una oveja específica en un prado sería difícil.

Definición: Las estructuras de datos son formas en que los computadores almacenan y organizan datos. Reflejan cómo se componen los datos, sus relaciones y cómo interactúan entre sí.

1.2 ¿Por Qué Necesitamos Estructuras de Datos?

Imagina un restaurante sin un sistema de colas. Esto causaría confusión, largas esperas y insatisfacción. De forma similar, gestionar grandes cantidades de datos sin organización puede llevar a errores y baja eficiencia. Las estructuras de datos permiten manipular datos de manera efectiva.

Aunque las matrices (arrays) son simples y útiles, tienen limitaciones cuando el tamaño de los datos cambia dinámicamente. Por eso existen otras estructuras más avanzadas.

2. Listas Secuenciales

2.1 Concepto y Estructura

Una lista lineal es una secuencia finita de elementos del mismo tipo. A nivel lógico, siempre sigue una línea continua, pero físicamente puede almacenarse de varias maneras, como mediante matrices o estructuras enlazadas.

Las listas secuenciales son específicamente continuas tanto en la estructura lógica como física.

2.2 Clasificación

• Lista Secuencial Estática: Usa una matriz de tamaño fijo. Limitada por su capacidad inicial.
• Lista Secuencial Dinámica: Permite expandir su capacidad según sea necesario.

Nos enfocaremos en implementar una lista secuencial dinámica.

3. Implementación de Lista Secuencial Dinámica en C

Creamos tres módulos:

// Estructura.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int ElemType;

typedef struct DynamicList {
    ElemType* data;
    int count; // Número de elementos
    int max_size; // Capacidad máxima
} DL;

void DLInit(DL* list);
void DLDestroy(DL* list);
void DLPrint(DL* list);
void DLCapacityCheck(DL* list);
void DLAddFront(DL* list, ElemType value);
void DLAddBack(DL* list, ElemType value);
void DLRemoveFront(DL* list);
void DLRemoveBack(DL* list);
void DLInsertAt(DL* list, int index, ElemType value);
void DLDeleteAt(DL* list, int index);
int DLSearch(DL* list, ElemType value);

Implementación:

// Estructura.c
#include "Estructura.h"

void DLInit(DL* list) {
    list->data = NULL;
    list->count = list->max_size = 0;
}

void DLDestroy(DL* list) {
    free(list->data);
    list->data = NULL;
    list->count = list->max_size = 0;
}

void DLPrint(DL* list) {
    for (int i = 0; i < list->count; i++) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

void DLCapacityCheck(DL* list) {
    if (list->count == list->max_size) {
        int new_size = (list->max_size == 0) ? 4 : list->max_size * 2;
        ElemType* temp = realloc(list->data, sizeof(ElemType) * new_size);
        if (!temp) {
            perror("realloc failed");
            exit(1);
        }
        list->data = temp;
        list->max_size = new_size;
    }
}

void DLAddFront(DL* list, ElemType value) {
    DLCapacityCheck(list);
    for (int i = list->count; i > 0; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[0] = value;
    list->count++;
}

void DLAddBack(DL* list, ElemType value) {
    DLCapacityCheck(list);
    list->data[list->count++] = value;
}

void DLRemoveFront(DL* list) {
    assert(list->count > 0);
    for (int i = 0; i < list->count - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->count--;
}

void DLRemoveBack(DL* list) {
    assert(list->count > 0);
    list->count--;
}

void DLInsertAt(DL* list, int index, ElemType value) {
    assert(index >= 0 && index <= list->count);
    DLCapacityCheck(list);
    for (int i = list->count; i > index; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[index] = value;
    list->count++;
}

void DLDeleteAt(DL* list, int index) {
    assert(index >= 0 && index < list->count);
    for (int i = index; i < list->count - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->count--;
}

int DLSearch(DL* list, ElemType value) {
    for (int i = 0; i < list->count; i++) {
        if (list->data[i] == value) return i;
    }
    return -1;
}

El archivo test.c permite probar estas funciones.

Conclusión

Las listas secuenciales son fundamentales para comprender cómo se almacenan y manipulan los datos. Esta guía cubre desde conceptos básicos hasta una implementación completa en C. Se recomienda practicar activamente para consolidar el aprendizaje.