Estructuras de datos fundamentales: Stack, Queue, Heap, Array, Árbol, Grafo

Las estructuras de datos son conceptos fundamentales de la informática que organizan y gestionan los datos. La elección de la estructura de datos correcta influye significativamente en la eficiencia de los algoritmos.

¿Qué son las estructuras de datos?

Las estructuras de datos definen cómo se almacenan, organizan y acceden los datos. Determinan la complejidad de operaciones como inserción, eliminación y búsqueda.

Clasificación de estructuras de datos

Estructuras lineales: Array, Stack, Queue, Linked List
Estructuras jerárquicas: Árbol, Heap
Estructuras de red: Grafo
Estructuras basadas en hash: Hash Table, Hash Set

Array

Fundamentos

Los arrays son la estructura de datos más simple con acceso directo por índice.

public class ArrayDemo {
    public static void main(String[] args) {
        // Array estático
        int[] numbers = new int[5];
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;
        
        // Array dinámico (ArrayList)
        List<Integer> dynamicArray = new ArrayList<>();
        dynamicArray.add(10);
        dynamicArray.add(20);
        dynamicArray.add(30);
        
        // Operaciones en array
        System.out.println("Elemento en índice 2: " + numbers[2]); // O(1)
        
        // Búsqueda lineal
        int index = linearSearch(numbers, 30); // O(n)
        System.out.println("30 encontrado en índice: " + index);
        
        // Ordenar con búsqueda binaria
        Arrays.sort(numbers); // O(n log n)
        int sortedIndex = Arrays.binarySearch(numbers, 30); // O(log n)
        System.out.println("30 (ordenado) en índice: " + sortedIndex);
    }
    
    // Búsqueda lineal en array
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // No encontrado
    }
}

Implementación de array dinámico

public class DynamicArray<T> {
    private Object[] data;
    private int size;
    private int capacity;
    
    public DynamicArray() {
        this.capacity = 10;
        this.data = new Object[capacity];
        this.size = 0;
    }
    
    public void add(T element) {
        if (size >= capacity) {
            resize();
        }
        data[size++] = element;
    }
    
    @SuppressWarnings("unchecked")
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return (T) data[index];
    }
    
    public void set(int index, T element) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        data[index] = element;
    }
    
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        
        // Desplazar elementos hacia la izquierda
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size--;
    }
    
    private void resize() {
        capacity *= 2;
        data = Arrays.copyOf(data, capacity);
    }
    
    public int size() { return size; }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i < size - 1) sb.append(", ");
        }
        sb.append("]");
        return sb.toString();
    }
}

Stack

Principio LIFO

Los stacks siguen el principio Last-In-First-Out (LIFO).

public class StackDemo {
    public static void main(String[] args) {
        // Stack en Java
        Stack<Integer> stack = new Stack<>();
        
        // Operaciones push
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Stack: " + stack);
        System.out.println("Elemento superior: " + stack.peek()); // 30
        
        // Operación pop
        int popped = stack.pop(); // Elimina 30
        System.out.println("Sacado: " + popped);
        System.out.println("Stack después de pop: " + stack);
        
        // Aplicación práctica: validación de paréntesis
        String expression = "{[()]}";
        boolean isBalanced = isBalancedParentheses(expression);
        System.out.println("Expresión balanceada: " + isBalanced);
    }
    
    // Validación de paréntesis con stack
    public static boolean isBalancedParentheses(String expression) {
        Stack<Character> stack = new Stack<>();
        
        for (char c : expression.toCharArray()) {
            switch (c) {
                case '(':
                case '[':
                case '{':
                    stack.push(c);
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') return false;
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') return false;
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') return false;
                    break;
            }
        }
        
        return stack.isEmpty();
    }
}

Implementación de stack

public class ArrayStack<T> {
    private Object[] data;
    private int top;
    private int capacity;
    
    public ArrayStack() {
        this.capacity = 10;
        this.data = new Object[capacity];
        this.top = -1;
    }
    
    public void push(T element) {
        if (isFull()) {
            resize();
        }
        data[++top] = element;
    }
    
    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) data[top--];
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (T) data[top];
    }
    
    public boolean isEmpty() {
        return top == -1;
    }
    
    public boolean isFull() {
        return top == capacity - 1;
    }
    
    private void resize() {
        capacity *= 2;
        data = Arrays.copyOf(data, capacity);
    }
    
    public int size() {
        return top + 1;
    }
}

Queue

Principio FIFO

Las colas siguen el principio First-In-First-Out (FIFO).

public class QueueDemo {
    public static void main(String[] args) {
        // Queue en Java con LinkedList
        Queue<Integer> queue = new LinkedList<>();
        
        // Operaciones enqueue
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        
        System.out.println("Queue: " + queue);
        System.out.println("Elemento frontal: " + queue.peek()); // 10
        
        // Operación dequeue
        int dequeued = queue.poll(); // Elimina 10
        System.out.println("Sacado de la cola: " + dequeued);
        System.out.println("Queue después de dequeue: " + queue);
        
        // Aplicación práctica: Breadth-First Search
        Graph graph = createSampleGraph();
        List<Integer> bfsResult = bfs(graph, 0);
        System.out.println("Recorrido BFS: " + bfsResult);
    }
    
    // BFS con queue
    public static List<Integer> bfs(Graph graph, int startNode) {
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.getVertexCount()];
        Queue<Integer> queue = new LinkedList<>();
        
        visited[startNode] = true;
        queue.offer(startNode);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            
            for (int neighbor : graph.getNeighbors(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        
        return result;
    }
    
    private static Graph createSampleGraph() {
        // Implementación para grafo de ejemplo
        return new Graph(6);
    }
}

Implementación de Cola

public class ArrayQueue<T> {
    private Object[] data;
    private int front;
    private int rear;
    private int size;
    private int capacity;
    
    public ArrayQueue() {
        this.capacity = 10;
        this.data = new Object[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }
    
    public void enqueue(T element) {
        if (isFull()) {
            resize();
        }
        rear = (rear + 1) % capacity;
        data[rear] = element;
        size++;
    }
    
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        
        T element = (T) data[front];
        front = (front + 1) % capacity;
        size--;
        return element;
    }
    
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return (T) data[front];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
    
    private void resize() {
        int newCapacity = capacity * 2;
        Object[] newData = new Object[newCapacity];
        
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % capacity];
        }
        
        data = newData;
        front = 0;
        rear = size - 1;
        capacity = newCapacity;
    }
    
    public int size() {
        return size;
    }
}

Heap

Cola de Prioridad

Los heaps son estructuras de árbol especializadas para implementar colas de prioridad.

public class HeapDemo {
    public static void main(String[] args) {
        // Min-Heap (Priority Queue)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(50);
        minHeap.offer(20);
        minHeap.offer(30);
        minHeap.offer(10);
        minHeap.offer(40);
        
        System.out.println("Min-Heap: " + minHeap);
        System.out.println("Elemento mínimo: " + minHeap.peek()); // 10
        
        System.out.println("Elementos en orden:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // 10 20 30 40 50
        }
        
        // Max-Heap
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.offer(50);
        maxHeap.offer(20);
        maxHeap.offer(30);
        maxHeap.offer(10);
        maxHeap.offer(40);
        
        System.out.println("\nMax-Heap: " + maxHeap);
        System.out.println("Elemento máximo: " + maxHeap.peek()); // 50
        
        // Heap Sort
        int[] array = {50, 20, 30, 10, 40};
        heapSort(array);
        System.out.println("Resultado Heap Sort: " + Arrays.toString(array));
    }
    
    // Algoritmo Heap Sort
    public static void heapSort(int[] array) {
        int n = array.length;
        
        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        
        // Extract elements from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            
            // heapify root element
            heapify(array, i, 0);
        }
    }
    
    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        
        if (largest != i) {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            
            heapify(array, n, largest);
        }
    }
}

Implementación de Min-Heap

public class MinHeap<T extends Comparable<T>> {
    private List<T> heap;
    
    public MinHeap() {
        this.heap = new ArrayList<>();
    }
    
    public void insert(T element) {
        heap.add(element);
        heapifyUp(heap.size() - 1);
    }
    
    public T extractMin() {
        if (heap.isEmpty()) {
            throw new NoSuchElementException();
        }
        
        T min = heap.get(0);
        T last = heap.remove(heap.size() - 1);
        
        if (!heap.isEmpty()) {
            heap.set(0, last);
            heapifyDown(0);
        }
        
        return min;
    }
    
    public T peek() {
        if (heap.isEmpty()) {
            throw new NoSuchElementException();
        }
        return heap.get(0);
    }
    
    private void heapifyUp(int index) {
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap.get(index).compareTo(heap.get(parentIndex)) >= 0) {
                break;
            }
            
            swap(index, parentIndex);
            index = parentIndex;
        }
    }
    
    private void heapifyDown(int index) {
        int size = heap.size();
        
        while (true) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int smallest = index;
            
            if (leftChild < size && heap.get(leftChild).compareTo(heap.get(smallest)) < 0) {
                smallest = leftChild;
            }
            
            if (rightChild < size && heap.get(rightChild).compareTo(heap.get(smallest)) < 0) {
                smallest = rightChild;
            }
            
            if (smallest == index) {
                break;
            }
            
            swap(index, smallest);
            index = smallest;
        }
    }
    
    private void swap(int i, int j) {
        T temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
    
    public boolean isEmpty() {
        return heap.isEmpty();
    }
    
    public int size() {
        return heap.size();
    }
}

Estructuras de Árbol

Árbol de Búsqueda Binaria

public class BinarySearchTree<T extends Comparable<T>> {
    private class Node {
        T data;
        Node left;
        Node right;
        
        Node(T data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
    
    private Node root;
    
    public void insert(T data) {
        root = insert(root, data);
    }
    
    private Node insert(Node node, T data) {
        if (node == null) {
            return new Node(data);
        }
        
        if (data.compareTo(node.data) < 0) {
            node.left = insert(node.left, data);
        } else if (data.compareTo(node.data) > 0) {
            node.right = insert(node.right, data);
        }
        
        return node;
    }
    
    public boolean search(T data) {
        return search(root, data);
    }
    
    private boolean search(Node node, T data) {
        if (node == null) {
            return false;
        }
        
        if (data.compareTo(node.data) == 0) {
            return true;
        } else if (data.compareTo(node.data) < 0) {
            return search(node.left, data);
        } else {
            return search(node.right, data);
        }
    }
    
    public void inorderTraversal() {
        inorderTraversal(root);
        System.out.println();
    }
    
    private void inorderTraversal(Node node) {
        if (node != null) {
            inorderTraversal(node.left);
            System.out.print(node.data + " ");
            inorderTraversal(node.right);
        }
    }
    
    public void preorderTraversal() {
        preorderTraversal(root);
        System.out.println();
    }
    
    private void preorderTraversal(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorderTraversal(node.left);
            preorderTraversal(node.right);
        }
    }
    
    public void postorderTraversal() {
        postorderTraversal(root);
        System.out.println();
    }
    
    private void postorderTraversal(Node node) {
        if (node != null) {
            postorderTraversal(node.left);
            postorderTraversal(node.right);
            System.out.print(node.data + " ");
        }
    }
    
    public int height() {
        return height(root);
    }
    
    private int height(Node node) {
        if (node == null) {
            return 0;
        }
        
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        
        return Math.max(leftHeight, rightHeight) + 1;
    }
    
    public T findMin() {
        if (root == null) {
            throw new NoSuchElementException();
        }
        
        Node current = root;
        while (current.left != null) {
            current = current.left;
        }
        
        return current.data;
    }
    
    public T findMax() {
        if (root == null) {
            throw new NoSuchElementException();
        }
        
        Node current = root;
        while (current.right != null) {
            current = current.right;
        }
        
        return current.data;
    }
}

Demo de Traversal de Árboles

public class TreeTraversalDemo {
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        
        // Einfügen
        bst.insert(50);
        bst.insert(30);
        bst.insert(70);
        bst.insert(20);
        bst.insert(40);
        bst.insert(60);
        bst.insert(80);
        
        System.out.print("In-Order: ");
        bst.inorderTraversal(); // 20 30 40 50 60 70 80
        
        System.out.print("Pre-Order: ");
        bst.preorderTraversal(); // 50 30 20 40 70 60 80
        
        System.out.print("Post-Order: ");
        bst.postorderTraversal(); // 20 40 30 60 80 70 50
        
        System.out.println("Altura del árbol: " + bst.height()); // 3
        System.out.println("Mínimo: " + bst.findMin()); // 20
        System.out.println("Máximo: " + bst.findMax()); // 80
        
        // Búsqueda
        System.out.println("40 encontrado: " + bst.search(40)); // true
        System.out.println("90 encontrado: " + bst.search(90)); // false
    }
}

Grafos

Representaciones de Grafos

public class Graph {
    private int vertexCount;
    private List<List<Integer>> adjacencyList;
    
    public Graph(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjacencyList = new ArrayList<>();
        
        for (int i = 0; i < vertexCount; i++) {
            adjacencyList.add(new ArrayList<>());
        }
    }
    
    // Grafo dirigido
    public void addEdge(int source, int destination) {
        if (source >= 0 && source < vertexCount && 
            destination >= 0 && destination < vertexCount) {
            adjacencyList.get(source).add(destination);
        }
    }
    
    // Grafo no dirigido
    public void addUndirectedEdge(int source, int destination) {
        addEdge(source, destination);
        addEdge(destination, source);
    }
    
    public List<Integer> getNeighbors(int vertex) {
        if (vertex >= 0 && vertex < vertexCount) {
            return new ArrayList<>(adjacencyList.get(vertex));
        }
        return new ArrayList<>();
    }
    
    public int getVertexCount() {
        return vertexCount;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < vertexCount; i++) {
            sb.append(i).append(": ");
            for (int neighbor : adjacencyList.get(i)) {
                sb.append(neighbor).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

Algoritmos de Grafos

public class GraphAlgorithms {
    
    // Búsqueda en Profundidad (DFS)
    public static List<Integer> dfs(Graph graph, int startNode) {
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.getVertexCount()];
        dfsHelper(graph, startNode, visited, result);
        return result;
    }
    
    private static void dfsHelper(Graph graph, int node, boolean[] visited, List<Integer> result) {
        visited[node] = true;
        result.add(node);
        
        for (int neighbor : graph.getNeighbors(node)) {
            if (!visited[neighbor]) {
                dfsHelper(graph, neighbor, visited, result);
            }
        }
    }
    
    // Búsqueda en Anchura (BFS)
    public static List<Integer> bfs(Graph graph, int startNode) {
        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.getVertexCount()];
        Queue<Integer> queue = new LinkedList<>();
        
        visited[startNode] = true;
        queue.offer(startNode);
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            
            for (int neighbor : graph.getNeighbors(current)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        
        return result;
    }
    
    // Algoritmo de Dijkstra (caminos más cortos)
    public static Map<Integer, Integer> dijkstra(int[][] graph, int startNode) {
        int n = graph.length;
        int[] distances = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[startNode] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{startNode, 0});
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int distance = current[1];
            
            if (visited[node]) continue;
            visited[node] = true;
            
            for (int neighbor = 0; neighbor < n; neighbor++) {
                if (graph[node][neighbor] > 0 && !visited[neighbor]) {
                    int newDistance = distance + graph[node][neighbor];
                    if (newDistance < distances[neighbor]) {
                        distances[neighbor] = newDistance;
                        pq.offer(new int[]{neighbor, newDistance});
                    }
                }
            }
        }
        
        Map<Integer, Integer> result = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (distances[i] != Integer.MAX_VALUE) {
                result.put(i, distances[i]);
            }
        }
        
        return result;
    }
    
    // Ordenamiento Topológico
    public static List<Integer> topologicalSort(Graph graph) {
        int n = graph.getVertexCount();
        int[] inDegree = new int[n];
        
        // Calcular el grado de entrada
        for (int i = 0; i < n; i++) {
            for (int neighbor : graph.getNeighbors(i)) {
                inDegree[neighbor]++;
            }
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            
            for (int neighbor : graph.getNeighbors(current)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return result;
    }
}

Demo de Grafos

public class GraphDemo {
    public static void main(String[] args) {
        // Crear grafo
        Graph graph = new Graph(6);
        
        // Añadir aristas
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);
        
        System.out.println("Grafo:");
        System.out.println(graph);
        
        // Traversals
        System.out.println("DFS: " + GraphAlgorithms.dfs(graph, 0));
        System.out.println("BFS: " + GraphAlgorithms.bfs(graph, 0));
        
        // Algoritmo de Dijkstra
        int[][] weightedGraph = {
            {0, 4, 2, 0, 0, 0},
            {4, 0, 1, 5, 0, 0},
            {2, 1, 0, 8, 10, 0},
            {0, 5, 8, 0, 2, 6},
            {0, 0, 10, 2, 0, 3},
            {0, 0, 0, 6, 3, 0}
        };
        
        Map<Integer, Integer> shortestPaths = GraphAlgorithms.dijkstra(weightedGraph, 0);
        System.out.println("Caminos más cortos desde nodo 0: " + shortestPaths);
        
        // Ordenamiento topológico para DAG
        Graph dag = new Graph(4);
        dag.addEdge(0, 1);
        dag.addEdge(0, 2);
        dag.addEdge(1, 3);
        dag.addEdge(2, 3);
        
        List<Integer> topologicalOrder = GraphAlgorithms.topologicalSort(dag);
        System.out.println("Ordenamiento topológico: " + topologicalOrder);
    }
}

Análisis de complejidad

Comparación de complejidad temporal

Estructura de datos	Acceso	Inserción	Eliminación	Búsqueda
Array	O(1)	O(n)	O(n)	O(n)
Dynamic Array	O(1)	O(1)*	O(n)	O(n)
Linked List	O(n)	O(1)*	O(1)*	O(n)
Stack	O(1)	O(1)	O(1)	O(n)
Queue	O(1)	O(1)	O(1)	O(n)
Binary Search Tree	O(log n)*	O(log n)*	O(log n)*	O(log n)*
Heap	O(1)	O(log n)	O(log n)	O(n)
Hash Table	O(1)*	O(1)*	O(1)*	O(1)*

*Complejidad amortizada o caso promedio

Complejidad espacial

Estructura de datos	Memoria	Observaciones
Array	O(n)	Tamaño fijo
Dynamic Array	O(n)	Con overhead
Linked List	O(n)	Punteros adicionales
Binary Search Tree	O(n)	Estructura recursiva
Graph	O(V + E)	V = nodos, E = aristas

Mejores prácticas

1. Elegir la estructura de datos adecuada

// Búsquedas frecuentes -> HashSet/HashMap
Set<String> uniqueNames = new HashSet<>();
Map<String, Integer> wordCount = new HashMap<>();

// Datos ordenados -> TreeSet/TreeMap
Set<Integer> sortedNumbers = new TreeSet<>();
Map<String, Integer> sortedWordCount = new TreeMap<>();

// Procesamiento FIFO -> Queue
Queue<Task> taskQueue = new LinkedList<>();

// Procesamiento LIFO -> Stack
Stack<Operation> undoStack = new Stack<>();

// Procesamiento con prioridad -> PriorityQueue
PriorityQueue<Event> eventQueue = new PriorityQueue<>();

2. Consideraciones de rendimiento

// Malo: O(n²) para grandes volúmenes
List<Integer> list = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
    for (int j = 0; j < list.size(); j++) {
        // Operación O(n²)
    }
}

// Bien: O(n) con HashSet
Set<Integer> set = new HashSet<>();
for (int item : list) {
    set.add(item); // O(1) en promedio
}

Preguntas relevantes para el examen

Tareas típicas

Implementa un Stack con Array
Compara BFS y DFS
Explica Heap Sort
Implementa Binary Search
Calcula la complejidad de algoritmos

Conceptos importantes

Análisis amortizado: Costo promedio sobre operaciones
Best-Case/Worst-Case/Average-Case: Diferentes escenarios
Space-Time Tradeoff: Memoria vs velocidad
Recursion vs Iteration: Variantes de implementación

Resumen

Las estructuras de datos son fundamentales para los algoritmos eficientes:

Arrays: Acceso directo, tamaño fijo
Stack/Queue: Órdenes de acceso especializados
Heaps: Priority Queues, operaciones min/max eficientes
Árboles: Organización jerárquica, búsqueda eficiente
Grafos: Relaciones de red, algoritmos complejos

La selección de la estructura de datos correcta es decisiva para el rendimiento e influye significativamente en la complejidad de las operaciones.

Täglicher Artikel

Datenstrukturen: Stack, Queue, Heap, Array, Baum, Graph