Estructuras de datos - Lista enlazada

Una lista enlazada (Linked List) es una estructura de datos lineal formada por varios nodos conectados secuencialmente mediante punteros.

A diferencia de los arrays, los elementos de una lista enlazada no necesitan almacenarse de forma contigua en la memoria.


Conceptos básicos y estructura de nodos de la lista enlazada

Cada nodo de la lista enlazada consta de dos partes:Campo de datos (data)Almacena los datos reales,Campo de puntero (next)Apunta al siguiente nodo.

链表节点结构与内存中的链式关系

La figura anterior muestra la apariencia real de la lista enlazada en memoria. Cada nodo semallocasigna de forma independiente en el heap, por lo que en memoria pueden no ser contiguos. Entre los nodos, mediantenextpunteros en serie; el next del último nodo apunta a NULL, lo que indica el final de la lista.

En C, el nodo de una lista enlazada se define mediante una estructura:

Ejemplo

#include <stdio.h>
#include <stdlib.h>  /* malloc, free */

/* Estructura de nodo de lista enlazada
data: campo de datos, almacena datos enteros
next: campo de puntero, apunta al siguiente nodo del mismo tipo */

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

/* Crear un nuevo nodo
Parámetro value: valor de datos del nodo
Valor de retorno: puntero al nuevo nodo, devuelve NULL si falla la asignación */

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Error de asignación de memoria\n");
        return NULL;
    }
    newNode->data = value;   /* Establecer datos */
    newNode->next = NULL;    /* El next del nuevo nodo se inicializa a NULL */
    return newNode;
}

struct Node* nextEs una estructura autorreferencial, es decir, la estructura contiene internamente un puntero a una estructura del mismo tipo. Esta es la tecnología clave para construir todas las estructuras de datos encadenadas (listas enlazadas, árboles, grafos).


Operaciones básicas de una lista enlazada simple

Creación y recorrido de una lista enlazada

Ejemplo

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

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

/* Recorrer e imprimir todos los nodos de la lista
Comenzando desde el nodo cabeza, visitar uno a uno a lo largo del puntero next hasta NULL */

void traverse(struct Node* head) {
    struct Node* current = head;  /* Comenzar desde la cabeza */
    printf("Contenido de la lista: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;  /* Moverse al siguiente nodo */
    }
    printf("NULL\n");
}

/* Crear una lista con n nodos (1, 2, 3, ..., n) */
struct Node* createList(int n) {
    if (n <= 0) return NULL;

    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    struct Node* tail = head;  /* tail siempre apunta al último nodo */
    for (int i = 2; i <= n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = NULL;
        tail->next = newNode;  /* Conectar el nuevo nodo al final de la lista */
        tail = newNode;           /* Actualizar el puntero tail */
    }
    return head;
}

int main() {
    struct Node* head = createList(5);
    traverse(head);
    /* Salida: Contenido de la lista: 1 -> 2 -> 3 -> 4 -> 5 -> NULL */
    return 0;
}

Operación de inserción

链表插入与删除操作的指针调整过程

La figura anterior muestra el proceso completo de cambios de punteros durante la inserción y eliminación en una lista enlazada. Comprender el orden de ajuste de los punteros es crucial: si el orden es incorrecto, puede provocar que la lista se rompa o una fuga de memoria.

Ejemplo

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

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

/* Insertar un nuevo nodo al principio de la lista (inserción por cabeza)
Complejidad temporal: O(1)
Valor de retorno: puntero al nuevo nodo cabeza */

struct Node* insertAtHead(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = head;  /* El nuevo nodo apunta al nodo cabeza original */
    return newNode;         /* El nuevo nodo se convierte en la nueva cabeza */
}

/* Insertar un nuevo nodo al final de la lista (inserción por cola)
Complejidad temporal: O(n), hay que recorrer hasta el final */

struct Node* insertAtTail(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        return newNode;  /* Lista vacía, el nuevo nodo es el nodo cabeza */
    }

    struct Node* current = head;
    while (current->next != NULL) {
        current = current->next;  /* Recorrer hasta el último nodo */
    }
    current->next = newNode;  /* El nodo final apunta al nuevo nodo */
    return head;
}

/* Insertar un nuevo nodo después de una posición dada
Complejidad temporal: O(n), primero hay que encontrar prevNode */

void insertAfter(struct Node* prevNode, int value) {
    if (prevNode == NULL) {
        printf("El nodo predecesor no puede ser nulo\n");
        return;
    }
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    /* Clave: primero el nuevo nodo apunta al sucesor, luego el predecesor apunta al nuevo nodo */
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

void printList(struct Node* head) {
    struct Node* cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 30);  /* Lista: 30 */
    head = insertAtHead(head, 20);  /* Lista: 20 -> 30 */
    head = insertAtHead(head, 10);  /* Lista: 10 -> 20 -> 30 */

    printf("Después de insertar por cabeza: "); printList(head);  /* Salida: 10 20 30 */

    head = insertAtTail(head, 40);  /* Lista: 10 -> 20 -> 30 -> 40 */
    printf("Después de insertar por cola: "); printList(head);  /* Salida: 10 20 30 40 */

    insertAfter(head->next, 25);    /* Insertar 25 después de 20 */
    printf("Después de inserción intermedia: "); printList(head);
    /* Salida: 10 20 25 30 40 */
    return 0;
}

Operación de eliminación

Ejemplo

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

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

/* Eliminar el nodo cabeza de la lista
Complejidad temporal: O(1)
Valor de retorno: puntero al nuevo nodo cabeza */

struct Node* deleteHead(struct Node* head) {
    if (head == NULL) return NULL;

    struct Node* temp = head;   /* Guardar el antiguo nodo cabeza */
    head = head->next;          /* Mover el puntero cabeza hacia adelante */
    free(temp);                 /* Liberar la memoria del antiguo nodo cabeza */
    return head;
}

/* Eliminar el primer nodo de la lista cuyo valor sea target
Complejidad temporal: O(n), hay que recorrer para encontrar el nodo objetivo */

struct Node* deleteByValue(struct Node* head, int target) {
    if (head == NULL) return NULL;

    /* Caso especial: el valor objetivo está en el nodo cabeza */
    if (head->data == target) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    /* Recorrer para encontrar el nodo predecesor del nodo objetivo */
    struct Node* current = head;
    while (current->next != NULL && current->next->data != target) {
        current = current->next;
    }

    /* Encontrar el nodo objetivo y eliminarlo */
    if (current->next != NULL) {
        struct Node* temp = current->next;
        current->next = current->next->next;  /* Saltar el nodo objetivo */
        free(temp);  /* Liberar memoria del nodo objetivo */
    }
    return head;
}

void printList(struct Node* head) {
    struct Node* cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    /* Construir lista: 10 -> 20 -> 30 -> 40 */
    struct Node* head = NULL;
    int vals[] = {10, 20, 30, 40};
    for (int i = 3; i >= 0; i--) {
        struct Node* n = (struct Node*)malloc(sizeof(struct Node));
        n->data = vals[i];
        n->next = head;
        head = n;
    }
    printf("Lista original: "); printList(head);  /* Salida: 10 20 30 40 */

    head = deleteHead(head);
    printf("Después de eliminar la cabeza: "); printList(head);  /* Salida: 20 30 40 */

    head = deleteByValue(head, 30);
    printf("Después de eliminar 30: "); printList(head);  /* Salida: 20 40 */
    return 0;
}

En la operación de eliminación de una lista enlazada,free()es crucial. Si solo se ajustan los punteros sin liberar la memoria del nodo eliminado, se producirá una fuga de memoria. En C, cada vezmallocdebe tener un correspondientefree。


Comparación entre lista enlazada y array

数组与链表全方位对比

Dimensión de comparaciónArrayLista enlazada
Distribución en memoriaAlmacenamiento contiguoAlmacenamiento disperso, conectado mediante punteros
Acceso aleatorioO(1)O(n)
Inserción/eliminación en la cabezaO(n)O(1)
Inserción/eliminación en la colaO(1)O(1) (con puntero de cola) / O(n) (sin puntero de cola)
Inserción/eliminación en el medioO(n)O(1)(posición conocida)
Sobrecarga de espacioSolo los datosDatos + puntero (8 bytes adicionales por nodo (64 bits))
Amabilidad con la cachéAlto(localidad espacial)bajo(nodos dispersos)
CapacidadFija (array estático)Crecimiento dinámico

Comprender estas compensaciones es una de las habilidades fundamentales para elegir la estructura de datos adecuada.

Si la cantidad de datos se conoce antes de la ejecución y no cambia con frecuencia, y se necesita un acceso aleatorio frecuente, el array es una mejor opción.

Si la cantidad de datos se modifica con frecuencia y su tamaño es incierto, estructuras dinámicas como la lista enlazada son más flexibles.

Otras extensiones