Estructuras de Datos y Algoritmos Esenciales: Ordenamiento, Búsqueda y Más

Ordenamientos

• Intercambio
• Inserción
• Selección
• Quicksort

Búsquedas

• Secuencial
• Binaria

Recursividad

• Directa
• Indirecta

Listas

Una lista es una colección de elementos o nodos que contienen datos y un enlace o liga al siguiente nodo.

Operaciones con Listas

• Recorrido
• Inserción
• Búsqueda
• Eliminación

Tipos de Listas

• Lineal
• Circular
• Doble

Lista Doble

Se refiere generalmente a la lista doblemente enlazada. En su variante circular, el último nodo se enlaza con el primero.

Lista Doblemente Enlazada

Es una colección de nodos donde cada uno tiene dos punteros: uno que apunta a su sucesor (derecha) y otro a su predecesor (izquierda).

Lista Doble Lineal

Sus punteros izquierdo (del primer nodo) y derecho (del último nodo) apuntan a nulo.

Lista Doble Circular

El puntero izquierdo del primer nodo apunta al último nodo, y el puntero derecho del último nodo apunta al primero.

Pilas (Stacks)

Una pila es una estructura de datos LIFO (Last-In, First-Out) donde la inserción y eliminación se restringen a un extremo (cima). Su condición es que si empieza vacía, debe terminar vacía.

Operaciones con Pilas

• Inserción de elementos (Push)
• Eliminación de elementos (Pop)
• Creación de la pila
• Recorridos
• Ordenamientos (menos común)

Colas (Queues)

Una cola es una estructura dinámica de almacenamiento FIFO (First-In, First-Out), considerada como una lista de elementos donde las inserciones se realizan por un extremo (final o tail) y las extracciones por el otro (frente o front).

Operaciones con Colas

• Inserción de elementos al final (Enqueue)
• Eliminación de elementos al principio (Dequeue)
• Creación de la cola
• Recorridos
• Búsquedas
• Ordenamientos (menos común)

Tipos de Colas

• Lineal
• Circular
• Bicolas (Deques)

Colas Circulares

Se puede insertar al final. El último elemento se enlaza lógicamente con el primer espacio disponible, optimizando el uso del espacio de memoria.

Bicolas (Deques)

Permiten la inserción y eliminación de elementos por ambos extremos (frente y final). Utilizan dos punteros para establecer enlaces con el nodo anterior y el nodo posterior si están implementadas como listas doblemente enlazadas.

Árboles

Tipos de Árboles

• Binario
• N-ario

Árbol Binario

Cada nodo tiene como máximo dos sucesores (hijos): izquierdo y derecho.

Recorridos en Árboles Binarios

Recorrido en Amplitud (Por Niveles - BFS)

Se visitan los nodos nivel por nivel, de izquierda a derecha.

Recorrido en Profundidad (DFS)

Se visitan los nodos recorriendo completamente los subárboles antes de pasar al siguiente hermano.

• Inorden: Subárbol Izquierdo - Raíz - Subárbol Derecho
• Preorden: Raíz - Subárbol Izquierdo - Subárbol Derecho
• Postorden: Subárbol Izquierdo - Subárbol Derecho - Raíz

Operaciones con Árboles

• Búsqueda
• Inserción
• Eliminación

Árbol Enhebrado (Threaded Tree)

Sus nodos hoja (o nodos con hijos nulos) utilizan los punteros nulos para enlazar con su sucesor o predecesor en un recorrido específico (ej. inorden), facilitando la navegación sin recursividad.

Árbol N-ario

Es una estructura de datos no lineal y dinámica, jerárquica, aplicada a nodos donde cada nodo puede tener hasta N hijos.

Grafos

Un grafo es un objeto matemático que representa relaciones (aristas) entre objetos (vértices). Se usan para modelar circuitos, redes, relaciones sociales, etc.

Componentes y Tipos de Grafos

• Vértices: Nodos o puntos del grafo.
• Aristas (o Arcos): Conexiones entre vértices.
• Aristas Paralelas: Múltiples aristas que conectan el mismo par de vértices.
• Grafo Dirigido (Digrafo): Cuando las transiciones (aristas) tienen una dirección específica, indicada por el sentido de la flecha.
• Grafo No Dirigido: Las aristas no tienen un sentido; cada arco existente representa una conexión bidireccional.
• Grafo Cíclico: Contiene por lo menos un ciclo (un camino que empieza y termina en el mismo vértice pasando por otros vértices).
• Grafo Acíclico: No contiene ciclos. Un grafo dirigido acíclico se conoce como DAG (Directed Acyclic Graph).
• Grafo Ponderado o Etiquetado: Una etiqueta (que puede ser un nombre, un valor numérico -peso, costo-, o cualquier tipo de dato) está asociada a las aristas y/o vértices.

Operaciones con Grafos

• Creación
• Inserción (vértices/aristas)
• Búsqueda (vértices/aristas, recorridos como BFS, DFS)
• Eliminación (vértices/aristas)