Estructuras de Datos No LinealesNO LINEALES

Es una colección de nodos donde cada nodo contiene un valor y una referencia (o enlace) al siguiente nodo en la secuencia. A diferencia de los arrays, las listas enlazadas permiten una inserción y eliminación más eficiente de elementos, ya que no requieren mover otros elementos en memoria.

Operaciones Principales:

• push_front: Insertar un elemento al inicio — O(1).
• push_back: Insertar un elemento al final — O(n).
• pop_front: Eliminar y devolver el primer elemento — O(1).
• read: Obtener un elemento por índice — O(n).
• insert_at_index: Insertar en una posición específica — O(n).

Uso Común:

• Implementación de pilas y colas.
• Listas de reproducción de música.
• Historial de navegación del navegador.
• Listas de tareas con inserción frecuente.

Implementación en Rust:

use std::fmt;

// Un nodo contiene un dato y un puntero al siguiente nodo.
// Box<Node> permite que la recursión funcione en la estructura.
// Option<Box<Node>> es None cuando no hay siguiente nodo (último de la lista).

#[derive(Debug)]
struct Node {
    data: String,
    next: Option<Box<Node>>,  // Enlace al siguiente nodo (None = fin)
}

impl Node {
    fn new(data: &str) -> Self {
        Node {
            data: data.to_string(),
            next: None,  // Nuevo nodo no tiene siguiente
        }
    }
}

// Lista enlazada simple: mantiene una referencia al primer nodo (cabeza).
// Las operaciones al inicio son O(1), al final son O(n) por que hay que recorrer.

#[derive(Debug)]
struct LinkedList {
    first_node: Option<Box<Node>>,  // Referencia al primer nodo
}

impl LinkedList {
    fn new() -> Self {
        LinkedList { first_node: None }  // Lista vacía
    }

    // PUSH_FRONT: Inserta al inicio — O(1)
    // El nuevo nodo apunta al actual primero, y se convierte en la nueva cabeza.
    fn push_front(&mut self, data: &str) {
        let mut new_node = Box::new(Node::new(data));
        new_node.next = self.first_node.take();  // take() extrae y deja None
        self.first_node = Some(new_node);
    }

    // PUSH_BACK: Inserta al final — O(n)
    // Recorre hasta el último nodo y enlaza el nuevo después de él.
    fn push_back(&mut self, data: &str) {
        let new_node = Box::new(Node::new(data));
        let mut current = &mut self.first_node;
        while let Some(node) = current {
            current = &mut node.next;
        }
        *current = Some(new_node);
    }

    // POP_FRONT: Elimina y devuelve el primero — O(1)
    // Extrae el nodo actual, y su siguiente se convierte en la nueva cabeza.
    fn pop_front(&mut self) -> Option<String> {
        self.first_node.take().map(|node| {
            self.first_node = node.next;  // El siguiente es el nuevo primero
            node.data
        })
    }

    // PEEK: Consulta el primero sin eliminarlo
    fn peek_front(&self) -> Option<&str> {
        self.first_node.as_ref().map(|node| node.data.as_str())
    }

    // READ: Acceso por índice — O(n)
    // Recorre la lista nodo por nodo hasta llegar al índice solicitado.
    fn read(&self, index: usize) -> Option<&str> {
        let mut current = &self.first_node;
        let mut current_index = 0;
        while current_index < index {
            current = &current.as_ref()?.next;
            current_index += 1;
        }
        current.as_ref().map(|node| node.data.as_str())
    }

    // INDEX_OF: Busca un valor y retorna su posición — O(n)
    fn index_of(&self, value: &str) -> Option<usize> {
        let mut current = &self.first_node;
        let mut current_index = 0;
        while let Some(node) = current {
            if node.data == value {
                return Some(current_index);
            }
            current = &node.next;
            current_index += 1;
        }
        None
    }

    // TO_VEC: Convierte la lista a un Vector para iterar fácilmente
    fn to_vec(&self) -> Vec<String> {
        let mut result = Vec::new();
        let mut current = &self.first_node;
        while let Some(node) = current {
            result.push(node.data.clone());
            current = &node.next;
        }
        result
    }

    fn len(&self) -> usize {
        let mut count = 0;
        let mut current = &self.first_node;
        while let Some(node) = current {
            count += 1;
            current = &node.next;
        }
        count
    }

    fn is_empty(&self) -> bool {
        self.first_node.is_none()
    }
}

// Implementa Display para imprimir la lista como [a -> b -> c]
impl fmt::Display for LinkedList {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut current = &self.first_node;
        write!(f, "[")?;
        while let Some(node) = current {
            write!(f, "{}", node.data)?;
            current = &node.next;
            if current.is_some() {
                write!(f, " -> ")?;
            }
        }
        write!(f, "]")
    }
}

fn main() {
    let mut lista = LinkedList::new();
    lista.push_front("time");    // [time]
    lista.push_front("a");       // [a -> time]
    lista.push_front("upon");    // [upon -> a -> time]
    lista.push_front("once");    // [once -> upon -> a -> time]

    println!("{}", lista);           // [once -> upon -> a -> time]
    println!("Longitud: {}", lista.len());  // 4
    println!("Pop: {:?}", lista.pop_front());  // Some("once")
}

Es una estructura de datos jerárquica donde cada nodo tiene un valor, un hijo izquierdo (menores) y un hijo derecho (mayores). Permite búsquedas eficientes en O(log N) cuando el árbol está balanceado.

Características:

• Nodos: Cada nodo contiene un valor y enlaces a sus hijos.
• Raíz: El nodo superior del árbol, que no tiene padre.
• Hojas: Nodos que no tienen hijos.
• Altura: La longitud del camino más largo desde la raíz hasta una hoja.
• Grado: El número de hijos que tiene un nodo.

Tipos:

• Árbol Binario: Cada nodo tiene máximo dos hijos.
• BST: Nodos izquierdos menores, derechos mayores.
• AVL: Árbol balanceado que mantiene altura equilibrada.
• Rojo-Negro: Árbol balanceado con reglas de coloración.

Implementación en Rust:

// Un BST (Binary Search Tree) organiza datos en jerarquía:
// - Izquierda = valores menores al nodo padre
// - Derecha = valores mayores al nodo padre
// Esto permite búsquedas en O(log N) cuando el árbol está balanceado.
// Box permite recursión: cada nodo "posee" sus hijos.

#[derive(Debug)]
struct TreeNode {
    value: i32,
    left: Option<Box<TreeNode>>,   // Subárbol izquierdo (menores)
    right: Option<Box<TreeNode>>,  // Subárbol derecho (mayores)
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode {
            value: val,
            left: None,   // Sin hijo izquierdo al crear
            right: None,  // Sin hijo derecho al crear
        }
    }

    // SEARCH: Búsqueda recursiva — O(log N) promedio
    // Si el objetivo es igual, lo encontramos.
    // Si es menor, buscamos en el subárbol izquierdo.
    // Si es mayor, buscamos en el subárbol derecho.
    fn search(&self, target: i32) -> Option<&TreeNode> {
        if self.value == target {
            return Some(self);  // Encontrado
        }
        if target < self.value {
            self.left.as_ref().and_then(|child| child.search(target))
        } else {
            self.right.as_ref().and_then(|child| child.search(target))
        }
    }

    // INSERT: Inserta un valor manteniendo la propiedad BST — O(log N)
    // Recorre hasta encontrar la posición correcta (hoja) y lo inserta.
    // Si el valor ya existe, no hace nada (no duplicados).
    fn insert(&mut self, value: i32) {
        if value < self.value {
            match &mut self.left {
                None => self.left = Some(Box::new(TreeNode::new(value))),
                Some(node) => node.insert(value),  // Recurse a la izquierda
            }
        } else if value > self.value {
            match &mut self.right {
                None => self.right = Some(Box::new(TreeNode::new(value))),
                Some(node) => node.insert(value),  // Recurse a la derecha
            }
        }
        // Si value == self.value, no se inserta (duplicado)
    }

    // DELETE: Elimina un valor — O(log N)
    // Tres casos: 1) hoja (sin hijos), 2) un hijo, 3) dos hijos.
    // Para dos hijos, usa el sucesor in-order (mínimo de la rama derecha).
    fn delete(
        node: Option<Box<TreeNode>>,
        value_to_delete: i32,
    ) -> Option<Box<TreeNode>> {
        let mut current = node?;

        if value_to_delete < current.value {
            current.left = Self::delete(current.left, value_to_delete);
            Some(current)
        } else if value_to_delete > current.value {
            current.right = Self::delete(current.right, value_to_delete);
            Some(current)
        } else {
            // Nodo encontrado — caso 1 y 2: sin hijos o un hijo
            if current.left.is_none() {
                return current.right;
            } else if current.right.is_none() {
                return current.left;
            }

            // Caso 3: dos hijos — buscar sucesor in-order (mínimo de la derecha)
            let mut successor = current.right.as_ref().unwrap();
            while let Some(left_child) = &successor.left {
                successor = left_child;
            }
            let successor_value = successor.value;

            // Reemplazar con el sucesor y eliminar el sucesor de la rama derecha
            current.value = successor_value;
            current.right = Self::delete(current.right, successor_value);
            Some(current)
        }
    }
}

// Wrapper del árbol que mantiene la raíz
struct BinarySearchTree {
    root: Option<Box<TreeNode>>,
}

impl BinarySearchTree {
    fn new() -> Self {
        BinarySearchTree { root: None }
    }

    fn search(&self, target: i32) -> Option<&TreeNode> {
        self.root.as_ref().and_then(|node| node.search(target))
    }

    fn insert(&mut self, value: i32) {
        match &mut self.root {
            None => self.root = Some(Box::new(TreeNode::new(value))),
            Some(node) => node.insert(value),
        }
    }

    fn delete(&mut self, value_to_delete: i32) {
        self.root = TreeNode::delete(self.root.take(), value_to_delete);
    }
}

fn main() {
    let mut tree = BinarySearchTree::new();
    tree.insert(50);   //       50
    tree.insert(25);   //      /  \
    tree.insert(75);   //    25    75
    tree.insert(10);   //   / \   / \
    tree.insert(30);   //  10 30 60  80
    tree.insert(60);
    tree.insert(80);

    for &v in &[50, 25, 75, 10, 30, 99] {
        match tree.search(v) {
            Some(nodo) => println!("{} encontrado", nodo.value),
            None => println!("{} no encontrado", v),
        }
    }

    tree.delete(25);
    println!("Después de eliminar 25: {:?}", tree.search(25));
}

Es una estructura de datos que consiste en un conjunto de nodos (o vértices) conectados por aristas (o enlaces). Los grafos son utilizados para representar relaciones entre pares de elementos y son fundamentales en diversas aplicaciones.

Características:

• Vértices: Los nodos del grafo que representan entidades.
• Aristas: Las conexiones entre vértices, dirigidas o no.
• Grado: Número de aristas incidentes en un vértice.
• Camino: Secuencia de vértices conectados por aristas.

Tipos:

• Dirigidos: Las aristas tienen dirección específica.
• No Dirigidos: Conexión bidireccional.
• Ponderados: Las aristas tienen un peso asociado.
• Conectados: Existe camino entre cada par de vértices.

Uso Común:

• Redes de computadoras y redes sociales.
• Sistemas de navegación y mapas.
• Modelado de flujos en logística.
• Algoritmos como BFS y Dijkstra.

Implementación en Rust:

use std::collections::{HashMap, HashSet, VecDeque};

// Grafo implementado con lista de adyacencia usando HashMap.
// Cada vértice (String) mapea a una lista de sus vecinos (Vec<String>).
// Las amistades son bidireccionales: si A es amigo de B, B es amigo de A.

struct SocialGraph {
    network: HashMap<String, Vec<String>>,  // Vértice → lista de vecinos
}

impl SocialGraph {
    fn new() -> Self {
        SocialGraph {
            network: HashMap::new(),
        }
    }

    // Agrega una persona al grafo (vértice sin aristas)
    fn add_person(&mut self, name: &str) {
        self.network.entry(name.to_string()).or_insert(Vec::new());
    }

    // Agrega una amistad bidireccional (dos aristas: A→B y B→A)
    fn add_friendship(&mut self, a: &str, b: &str) {
        self.network
            .entry(a.to_string())
            .or_insert(Vec::new())
            .push(b.to_string());  // A → B
        self.network
            .entry(b.to_string())
            .or_insert(Vec::new())
            .push(a.to_string());  // B → A
    }

    // BFS (Breadth-First Search): Recorrido por niveles usando una cola FIFO.
    // Primero visita al nodo inicial, luego todos sus vecinos directos,
    // luego los vecinos de los vecinos, etc.
    fn display_network_bfs(&self, start_person: &str) {
        let mut queue: VecDeque<&str> = VecDeque::new();  // Cola FIFO
        let mut visited: HashSet<&str> = HashSet::new();  // Evita ciclos

        queue.push_back(start_person);
        visited.insert(start_person);

        while let Some(current_person) = queue.pop_front() {
            println!("Visitando: {}", current_person);

            if let Some(friends) = self.network.get(current_person) {
                for friend in friends {
                    if !visited.contains(friend.as_str()) {
                        visited.insert(friend.as_str());
                        queue.push_back(friend.as_str());  // Enqueue para visitar después
                    }
                }
            }
        }
    }

    // Retorna el orden de visita BFS como Vector
    fn bfs_order(&self, start_person: &str) -> Vec<String> {
        let mut queue: VecDeque<&str> = VecDeque::new();
        let mut visited: HashSet<&str> = HashSet::new();
        let mut order: Vec<String> = Vec::new();

        if !self.network.contains_key(start_person) {
            return order;
        }

        queue.push_back(start_person);
        visited.insert(start_person);

        while let Some(current_person) = queue.pop_front() {
            order.push(current_person.to_string());

            if let Some(friends) = self.network.get(current_person) {
                for friend in friends {
                    if !visited.contains(friend.as_str()) {
                        visited.insert(friend.as_str());
                        queue.push_back(friend.as_str());
                    }
                }
            }
        }
        order
    }
}

fn main() {
    let mut graph = SocialGraph::new();

    graph.add_friendship("Ana", "Carlos");
    graph.add_friendship("Ana", "Beatriz");
    graph.add_friendship("Carlos", "Beatriz");
    graph.add_friendship("Beatriz", "David");

    // BFS desde Ana: Ana → Carlos → Beatriz → David (por niveles)
    println!("--- BFS desde Ana ---");
    graph.display_network_bfs("Ana");
}