Please enable JavaScript.
Coggle requires JavaScript to display documents.
UF4 – Estructuras de datos enlazadas - Coggle Diagram
UF4 – Estructuras de datos enlazadas
Introducción a estructuras dinámicas
Diferencia con estructuras estáticas
Tamaño fijado en compilación
No se adaptan en tiempo de ejecución
Características de estructuras dinámicas
Crecen y se reducen durante la ejecución
Usan punteros y memoria dinámica
Ejemplo principal: listas enlazadas
Colecciones de elementos conectados
Cada nodo apunta al siguiente
Listas enlazadas – Fundamentos teóricos
Concepto de nodo
Dos partes:
Campo dato (tipo genérico)
Enlace → puntero al siguiente nodo
Representación típica:
Caja con dato + puntero
El último nodo apunta a:
NULL
Estructura en memoria
Nodos no necesariamente contiguos
Flechas representan direcciones de memoria
Tipos de listas enlazadas
Lista simplemente enlazada
Cada nodo apunta solo al siguiente
Recorrido eficiente hacia adelante
Lista doblemente enlazada
Dos enlaces:
Nodo anterior
Nodo siguiente
Permite recorridos en ambas direcciones
Lista circular simplemente enlazada
Último nodo enlaza al primero
Recorrido circular
Lista circular doblemente enlazada
Último ↔ primero
Recorridos circulares en ambas direcciones
TAD Lista – Especificación formal
Definición matemática
Secuencia ordenada de 0..n elementos
Orden explícito por posiciones
Operaciones básicas
ListaVacia(L) → inicializa como vacía
EsVacia(L) → true/false
Insertar(L, x, p) → inserta antes de p
Localizar(L, x) → devuelve puntero a x
Suprimir(L, x) → elimina nodo con dato x
Anterior(L, p) → puntero al anterior
Primero(L) → puntero al primer nodo
Anula(L) → vacía la lista
Variantes útiles
InsertarPrimero(L, x)
InsertarFinal(L, x)
Implementación del TAD Lista
Clase Nodo
Contenido:
dato
enlace
Constructor simple
Nodo(dato)
Constructor enlazado
Nodo(dato, nodo_siguiente)
Métodos:
datoNodo()
enlaceNodo()
ponerEnlace()
Nodo Genérico (templates)
Permite listas de cualquier tipo T
Mismos métodos que nodo entero
Clase Lista
Atributo principal:
primero (puntero a cabeza)
Constructor
primero = NULL
Función crearLista()
Inserción repetida por cabeza
Termina con valor -1
Ejemplo de construcción
Inserción en cabeza:
primero = new Nodo(x, primero)
Inserción en listas enlazadas
Tipos de inserción
En la cabeza
En la cola
Entre dos nodos
Insertar en cabeza
Más eficiente
Proceso:
Crear nodo nuevo
nuevo.enlace = primero
primero = nuevo
Insertar en cola
Requiere recorrer la lista
Pasos:
Buscar último → enlace NULL
ultimo.enlace = nuevo
Insertar entre dos nodos
Pasos:
nuevo.enlace = nodo_siguiente
nodo_anterior.enlace = nuevo
Búsqueda en listas enlazadas
Idea general
Recorrer nodo a nodo con puntero índice
Algoritmo
índice = primero
Comparar dato
Si coincide → devolver nodo
Si no → avanzar al siguiente
Resultado posible
Puntero al nodo encontrado
NULL si no existe
Eliminación de nodos en listas enlazadas
Proceso
Buscar nodo y su anterior
Reenlazar:
anterior.enlace = nodo.siguiente
Casos:
Eliminación en cabeza:
primero = primero.siguiente
Liberar memoria:
delete nodo
Consideraciones
Cuidado con lista vacía
Controlar punteros NULL
UF4 – Bloque 2: Adaptadores de listas (Pilas y Colas)
Pilas (Stacks)
Concepto
Estructura LIFO
Last In, First Out
Solo se accede por un extremo: cima
Operaciones básicas
Insertar (push)
Quitar (pop)
Estados:
Pila llena → overflow
Pila vacía → underflow
Comprobaciones típicas
pilaVacia()
Pila mediante listas enlazadas
Estructura
Cada nodo = elemento + puntero siguiente
cima apunta al último nodo insertado
Clase PilaGenerica
Clase interna NodoPila
elemento
siguiente
Atributo principal:
cima
Métodos principales
pilaVacia() → comprobar estado
insertar(x)
nuevo → siguiente = cima
cima = nuevo
quitar()
devuelve cima.elemento
cima = cima.siguiente
cimaPila() → devuelve elemento sin quitarlo
limpiarPila()
Recorrer y borrar nodos
Colas (Queues)
Concepto
Estructura FIFO
First In, First Out
Inserción por final
Extracción por frente
Operaciones básicas
Insertar (enqueue)
Quitar (dequeue)
frenteCola() → primer elemento
colaVacia()
Cola mediante listas enlazadas
Estructura
Dos punteros:
frente → inicio
final → último nodo
Clase colaGenerica
Clase interna nodoCola
elemento
siguiente
Variables:
frente
final
Métodos principales
insertar(x)
Crear nuevo nodo
Si cola vacía:
frente = nuevo
Si no:
final.siguiente = nuevo
final = nuevo
quitar()
Obtener elemento de frente
frente = frente.siguiente
frenteCola()
devuelve frente.elemento
borrarCola()
Liberar todos los nodos
colaVacia()
Ejercicios importantes de la UF4
Listas enlazadas
Crear clase punto + nodos de puntos
Crear lista de 5 enteros
Insertar cabeza / cola / entre nodos
Lista aleatoria → insertar en el centro → mostrar impares
Pilas
Determinar si una palabra es palíndromo
Copiar pila usando solo operaciones del TAD
Manejo de 5 pilas según reglas (i, j)
Colas
Clonar cola
Comparar dos colas para comprobar si son idénticas