Definición de Lista Lineal

Una lista lineal representa una colección finita y ordenada de $n$ elemantos ($n \geq 0$), denotada comúnmente como $(a_1, a_2, \dots, a_n)$. Esta estructura de datos se fundamenta en las siguientes propiedades lógicas:

• Cada componente de la lista, a excepción del primero y el último, posee un único predecesor y un único sucesor.
• El elemento inicial no cuenta con un predecesor.
• El elemento terminal carece de sucesor.

Operaciones Fundamentales

Para manipular una lista lineal, se definen habitualmente las siguientes operaciones básicas:

1. Inicialización: Crear una lista vacía.
2. Cálculo de longitud: Determinar el número total de elementos presentes.
3. Acceso: Recuperar el contenido de una posición específica.
4. Búsqueda: Localizar la posición de un valor determinado.
5. Inserción: Añadir un nuevo elemento en una ubicación dada.
6. Eliminación: Remover un elemento de una posición específica.
7. Visualización: Recorrer y mostrar el contenido de la estructura.

Estructuras de Almacenamiento

1. Representación Secuencial

Utiliza un espacio contiguo en memoria, generalmente implementado mediante arreglos estáticos.

#define TAM_MAX 100
typedef char Dato;

typedef struct {
    Dato elementos[TAM_MAX];
    int cantidad;
} ListaSecuencial;

2. Representación Enlazada

Gestiona la memoria de forma dinámica mediante nodos conectados por punteros.

• Lista Enlazada Simple: Cada nodo apunta al siguiente elemento.

typedef struct NodoSimple {
    Dato info;
    struct NodoSimple *sig;
} NodoS;

• Lista Doblemente Enlazada: Cada nodo contiene punteros hacia el elemento anterior y el posterior.

typedef struct NodoDoble {
    Dato info;
    struct NodoDoble *prev;
    struct NodoDoble *sig;
} NodoD;

Implemetnación de una Lista Secuencial en C

Inicialización

void crearLista(ListaSecuencial *L) {
    L->cantidad = 0;
}

Obtención de Longitud

int longitud(ListaSecuencial L) {
    return L.cantidad;
}

Acceso por Índice

int obtenerDato(ListaSecuencial L, int pos, Dato *item) {
    if (pos < 1 || pos > L.cantidad) {
        return 0; // Posición fuera de rango
    }
    *item = L.elementos[pos - 1];
    return 1;
}

Búsqueda por Valor

int buscarValor(ListaSecuencial L, Dato objetivo) {
    int idx = 0;
    while (idx < L.cantidad && L.elementos[idx] != objetivo) {
        idx++;
    }
    if (idx >= L.cantidad) {
        return 0; // No encontrado
    }
    return idx + 1;
}

Inserción de Elementos

int insertar(ListaSecuencial *L, Dato nuevo, int pos) {
    if (pos < 1 || pos > L->cantidad + 1 || L->cantidad == TAM_MAX) {
        return 0;
    }
    for (int j = L->cantidad; j >= pos; j--) {
        L->elementos[j] = L->elementos[j - 1];
    }
    L->elementos[pos - 1] = nuevo;
    L->cantidad++;
    return 1;
}

Eliminación de Elementos

int eliminar(ListaSecuencial *L, int pos) {
    if (pos < 1 || pos > L->cantidad) {
        return 0;
    }
    for (int j = pos; j < L->cantidad; j++) {
        L->elementos[j - 1] = L->elementos[j];
    }
    L->cantidad--;
    return 1;
}

Impresión de la Lista

#include <stdio.h>

void mostrarLista(ListaSecuencial L) {
    for (int i = 0; i < L.cantidad; i++) {
        printf("%c ", L.elementos[i]);
    }
    printf("\n");
}

Ejemplo de Ejecución

int main() {
    ListaSecuencial miLista;
    Dato aux;
    
    crearLista(&miLista);
    
    insertar(&miLista, 'X', 1);
    insertar(&miLista, 'Y', 2);
    insertar(&miLista, 'Z', 3);
    
    printf("Estado de la lista: ");
    mostrarLista(miLista);
    
    printf("Tamaño actual: %d\n", longitud(miLista));
    
    if (obtenerDato(miLista, 2, &aux)) {
        printf("Elemento en pos 2: %c\n", aux);
    }
    
    printf("El valor 'X' está en la posición: %d\n", buscarValor(miLista, 'X'));
    
    eliminar(&miLista, 1);
    printf("Lista tras eliminar el primer elemento: ");
    mostrarLista(miLista);
    
    return 0;
}