on enero 19, 2026

COMPARTE ESTE ARTÍCULO

1) Qué es una lista enlazada y por qué existe

Una lista enlazada es una estructura de datos lineal compuesta por nodos conectados mediante punteros. Cada nodo almacena:

Un dato (payload).
Un puntero al siguiente nodo (next) y, según el tipo de lista, opcionalmente al anterior (prev).

A diferencia de un array:

No requiere memoria contigua.
Crece/decrece dinámicamente con malloc/free.
El acceso por “índice” no es O(1); requiere recorrido O(n).

Idea clave: en C la lista enlazada es un ejercicio directo de punteros, memoria dinámica e invariantes estructurales.

2) Tipos principales de listas enlazadas

2.1 Lista simplemente enlazada (Singly Linked List)

Cada nodo apunta solo al siguiente.

head -> [data|next] -> [data|next] -> [data|null]

Ventajas: simple, menos memoria.
Limitaciones: no puedes retroceder sin volver a empezar.

2.2 Lista doblemente enlazada (Doubly Linked List)

Cada nodo apunta al siguiente y al anterior.

null <- [prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> null

Ventajas: recorrido bidireccional, borrado local más cómodo si ya tienes el nodo.
Coste: más memoria y más actualizaciones de punteros.

2.3 Lista circular

El último nodo enlaza con el primero (en simple o doble).
Útil para rondas/turnos/buffers, pero exige condiciones de parada cuidadosas para evitar bucles infinitos.

3) Operaciones típicas y complejidad temporal

Sea n el número de nodos:

Recorrer / imprimir: O(n)
Buscar por valor: O(n)
Insertar al inicio: O(1)
Insertar al final:
- Sin tail: O(n) (hay que llegar al último)
- Con tail: O(1)
Borrar por valor: O(n) (hay que encontrar y reconectar)
Acceso por posición i: O(i) (≈ O(n) en promedio)

Conclusión práctica: listas enlazadas son apropiadas si predominan inserciones/borrados y no se requiere acceso aleatorio constante por índice.

4) Casos borde (los que rompen implementaciones)

En C, la mayoría de fallos vienen de:

Lista vacía (head == NULL)
Un solo nodo
Insertar/borrar en cabeza
Borrar el último nodo (si mantienes tail, hay que actualizarlo)
No encontrar el elemento buscado
Errores de memoria: free omitido, doble free, uso tras free (use-after-free)

5) Implementación en C: lista simplemente enlazada (con tail opcional)

5.1 Diseño de estructuras

Vamos a implementar una lista genérica para int (en un blog es didáctico). En ingeniería, lo normal es generalizar con void* y callbacks, pero para empezar es mejor fijar el tipo y dominar la mecánica.

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
    Node* tail;   // opcional, pero útil para push_back O(1)
    size_t size;
} LinkedList;

Invariantes recomendados:

Si size == 0 ⇒ head == NULL y tail == NULL
Si size > 0 ⇒ head != NULL y tail != NULL y tail->next == NULL

5.2 Inicialización y creación de nodos

static Node* node_create(int value) {
    Node* n = (Node*)malloc(sizeof(Node));
    if (!n) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    n->data = value;
    n->next = NULL;
    return n;
}

static void list_init(LinkedList* list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

5.3 Insertar al inicio (push_front) — O(1)

static void list_push_front(LinkedList* list, int value) {
    Node* n = node_create(value);
    n->next = list->head;
    list->head = n;

    if (list->tail == NULL) { // lista estaba vacía
        list->tail = n;
    }
    list->size++;
}

5.4 Insertar al final (push_back) — O(1) con tail

static void list_push_back(LinkedList* list, int value) {
    Node* n = node_create(value);

    if (list->tail == NULL) { // vacía
        list->head = n;
        list->tail = n;
    } else {
        list->tail->next = n;
        list->tail = n;
    }
    list->size++;
}

5.5 Recorrer / imprimir — O(n)

static void list_print(const LinkedList* list) {
    const Node* cur = list->head;
    printf("[");
    while (cur) {
        printf("%d", cur->data);
        cur = cur->next;
        if (cur) printf(" -> ");
    }
    printf("]\n");
}

5.6 Buscar — O(n)

static Node* list_find(LinkedList* list, int value) {
    Node* cur = list->head;
    while (cur) {
        if (cur->data == value) return cur;
        cur = cur->next;
    }
    return NULL;
}

5.7 Insertar después de un valor (insert_after) — O(n)

Se busca el nodo “objetivo” y se engancha el nuevo detrás.

static bool list_insert_after(LinkedList* list, int target, int value) {
    Node* t = list_find(list, target);
    if (!t) return false;

    Node* n = node_create(value);
    n->next = t->next;
    t->next = n;

    if (list->tail == t) { // si insertamos después del último
        list->tail = n;
    }
    list->size++;
    return true;
}

5.8 Borrar por valor (remove_first) — O(n)

En lista simple, para borrar un nodo necesitas conocer su anterior.

static bool list_remove_first(LinkedList* list, int value) {
    if (!list->head) return false;

    // caso: borrar head
    if (list->head->data == value) {
        Node* victim = list->head;
        list->head = list->head->next;
        if (list->tail == victim) { // era el único nodo
            list->tail = list->head; // NULL si quedó vacía
        }
        free(victim);
        list->size--;
        return true;
    }

    // caso general: buscar anterior
    Node* prev = list->head;
    Node* cur  = list->head->next;
    while (cur) {
        if (cur->data == value) {
            prev->next = cur->next;
            if (list->tail == cur) {
                list->tail = prev;
            }
            free(cur);
            list->size--;
            return true;
        }
        prev = cur;
        cur = cur->next;
    }
    return false;
}

5.9 Invertir la lista (reverse) — O(n)

Clásico de entrevistas y de estructuras de datos.

static void list_reverse(LinkedList* list) {
    Node* prev = NULL;
    Node* cur  = list->head;
    list->tail = list->head; // la vieja head pasa a ser tail

    while (cur) {
        Node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    list->head = prev;
}

5.10 Liberar toda la memoria (free_list) — O(n)

Obligatorio en C (y evaluable).

static void list_clear(LinkedList* list) {
    Node* cur = list->head;
    while (cur) {
        Node* next = cur->next;
        free(cur);
        cur = next;
    }
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

6) Programa de prueba (main)

int main(void) {
    LinkedList list;
    list_init(&list);

    list_push_back(&list, 10);
    list_push_back(&list, 20);
    list_push_front(&list, 5);
    list_print(&list); // [5 -> 10 -> 20]

    list_insert_after(&list, 10, 15);
    list_print(&list); // [5 -> 10 -> 15 -> 20]

    list_remove_first(&list, 5);
    list_print(&list); // [10 -> 15 -> 20]

    list_reverse(&list);
    list_print(&list); // [20 -> 15 -> 10]

    printf("size = %zu\n", list.size);

    list_clear(&list);
    list_print(&list); // []

    return 0;
}

7) Debug y verificación (nivel Ingeniería)

7.1 Valgrind (Linux)

Para detectar fugas y usos indebidos de memoria:

Compila con símbolos:gcc -Wall -Wextra -Wpedantic -O0 -g list.c -o list
Ejecuta:valgrind --leak-check=full --track-origins=yes ./list

7.2 Sanitizers (GCC/Clang)

Muy recomendables en prácticas:

gcc -Wall -Wextra -O0 -g -fsanitize=address,undefined list.c -o list
./list

8) Comparativa técnica: lista enlazada vs array (visión de rendimiento)

Arrays: mejor localidad de caché, acceso por índice O(1), menos overhead.
Listas enlazadas: overhead de punteros y peor caché (saltos de memoria), pero inserciones/borrados pueden evitar realocaciones.

En rendimiento real, si no necesitas inserciones/borrados frecuentes, un array/vector suele ser superior.

9) Ejercicios propuestos (con enfoque universitario)

Implementa list_pop_front y list_pop_back (este último es O(n) en lista simple sin prev).
Implementa list_remove_all(value) que elimine todas las ocurrencias.
Implementa list_insert_sorted(value) suponiendo lista ordenada ascendente.
Implementa list_has_cycle() (detección de ciclos con Floyd “tortuga-liebre”).
Generaliza la lista para void* y usa callbacks para:
- imprimir
- comparar
- liberar datos (si se reservan dinámicamente)
Implementa versión doblemente enlazada y compara complejidad y facilidad de borrado.

10) Cierre

Dominar listas enlazadas en C implica dominar:

punteros y aliasing,
gestión de memoria dinámica,
invariantes y casos borde,
y la relación entre complejidad teórica y rendimiento real por caché.

Es una base excelente para estructuras superiores: pilas, colas, árboles, grafos y asignadores de memoria.

Photo by Pavel Danilyuk on Pexels.com
Photo by RealToughCandy.com on Pexels.com
Photo by Andrea Piacquadio on Pexels.com

¿QUÉ TE HA PARECIDO EL ARTÍCULO? Danos tu opinión al final de la página.
Deja tu comentario y ayúdanos a crecer.

¡SÍGUENOS EN TUS REDES FAVORITAS!
AYUDANOS A CRECER Y QUE LLEGUEMOS A TODAS LAS PERSONAS QUE NOS NECESITANA. SÍGUENOS EN TUS REDES.
Entra AQUÍ y elíge donde seguirnos.