Estructuras de Datos

0x0042 INICIALIZANDO...
0x7ffe-stack
*p = malloc(sizeof(Node))
0x3b2a - heap
ptr -> next = NULL
Unidad 07

Listas Enlazadas

A diferencia de los arreglos, donde los datos deben estar juntos en memoria (contiguos), una Lista Enlazada permite que los datos estén dispersos por toda la RAM. El "pegamento" que mantiene el orden lógico son los punteros.

7.1 El Nodo: Tu primer bloque de construcción
Mirar en YouTube

Una lista simplemente enlazada se define por un solo puntero: la "cabeza" (head). Si pierdes la referencia a la cabeza, pierdes la lista completa. Cada nodo conoce al siguiente, pero nadie conoce al anterior.

7.2 (Parte 1) Lista Simple: Inserción y Recorrido
Mirar en YouTube
main.cpp
void push(struct Nodo** head_ref, int new_data) {
    // 1. Reservar memoria
    struct Nodo* new_node = (struct Nodo*) malloc(sizeof(struct Nodo));
    // 2. Asignar dato
    new_node->dato = new_data;
    // 3. El nuevo apunta a la antigua cabeza
    new_node->siguiente = (*head_ref);
    // 4. Mover la cabeza al nuevo nodo
    (*head_ref) = new_node;
}
void push(struct Nodo** head_ref, int new_data) {
    // 1. Reservar memoria
    struct Nodo* new_node = (struct Nodo*) malloc(sizeof(struct Nodo));
    // 2. Asignar dato
    new_node->dato = new_data;
    // 3. El nuevo apunta a la antigua cabeza
    new_node->siguiente = (*head_ref);
    // 4. Mover la cabeza al nuevo nodo
    (*head_ref) = new_node;
}
Imagen 29. Inserción y eliminación lógica de nodos

Imagen 29. Inserción y eliminación lógica de nodos

Visualización de enlaces: Pasos críticos para "reconectar" los cables (punteros) al insertar o eliminar un nodo intermedio.

7.2 (Parte 2) Lista Simple: Eliminación de Nodos
Mirar en YouTube

Las listas simples tienen un defecto: no pueden volver atrás. Las Listas Doblemente Enlazadas solucionan esto añadiendo un puntero "prev" (anterior) en cada nodo. Esto permite recorrer la lista en ambas direcciones, a cambio de usar más memoria.

Imagen 30. Estructura de una Lista Doblemente Enlazada

Imagen 30. Estructura de una Lista Doblemente Enlazada

Anatomía del nodo doble: Observa los dos punteros salientes. El "prev" del primer nodo y el "next" del último siempre apuntan a NULL.

main.cpp
struct NodoDoble {
    int dato;
    struct NodoDoble* next; // Siguiente
    struct NodoDoble* prev; // Anterior
};
struct NodoDoble {
    int dato;
    struct NodoDoble* next; // Siguiente
    struct NodoDoble* prev; // Anterior
};
7.3 Listas Doblemente Enlazadas
Mirar en YouTube

En una lista circular, no existe el final (NULL). El último nodo apunta de nuevo al primero. Esto es ideal para aplicaciones que requieren turnos rotativos, como el "Round Robin" en la planificación de procesos de un Sistema Operativo.

7.4 Listas Circulares: El anillo infinito
Mirar en YouTube
Imagen 31. Lista Circular Simplemente Enlazada

Imagen 31. Lista Circular Simplemente Enlazada

Representación gráfica: La flecha de retorno que convierte una línea en un círculo. Puede ser simple o doblemente enlazada.

main.cpp
void printCircular(struct Nodo* head) {
    struct Nodo* temp = head;
    if (head != NULL) {
        do {
            printf("%d ", temp->dato);
            temp = temp->next;
        } while (temp != head);
    }
}
void printCircular(struct Nodo* head) {
    struct Nodo* temp = head;
    if (head != NULL) {
        do {
            printf("%d ", temp->dato);
            temp = temp->next;
        } while (temp != head);
    }
}
Volver al nivel