Основные структуры данных: Stack, Queue, Heap, Array, Tree, Graph

Структуры данных лежат в основе информатики: они организуют и управляют данными. Правильный выбор структуры данных напрямую влияет на эффективность алгоритмов.

Что такое структуры данных?

Структуры данных определяют, как хранятся, организуются и к ним обращаются данные. Они задают сложность операций вставки, удаления и поиска.

Классификация структур данных

1. Линейные структуры: Array, Stack, Queue, Linked List
2. Иерархические структуры: Tree, Heap
3. Сетевые структуры: Graph
4. Хеш-структуры: Hash Table, Hash Set

Array

Основы

Array - это самая простая структура данных с прямым доступом по индексу.

public class ArrayDemo {
    public static void main(String[] args) {
        // Статический массив
        int[] numbers = new int[5];
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;
        
        // Динамический массив (ArrayList)
        List<Integer> dynamicArray = new ArrayList<>();
        dynamicArray.add(10);
        dynamicArray.add(20);
        dynamicArray.add(30);
        
        // Операции с массивом
        System.out.println("Element bei Index 2: " + numbers[2]); // O(1)
        
        // Линейный поиск
        int index = linearSearch(numbers, 30); // O(n)
        System.out.println("30 gefunden bei Index: " + index);
        
        // Сортировка и бинарный поиск
        Arrays.sort(numbers); // O(n log n)
        int sortedIndex = Arrays.binarySearch(numbers, 30); // O(log n)
        System.out.println("30 (sortiert) bei Index: " + sortedIndex);
    }
    
    // Линейный поиск
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // Не найдено
    }
}

Реализация динамического массива

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();
        }
        
        // Сдвигаем элементы влево
        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

Принцип LIFO

Stack работает по принципу Last-In-First-Out (LIFO) - последний пришедший, первый ушедший.

public class StackDemo {
    public static void main(String[] args) {
        // Java Stack
        Stack<Integer> stack = new Stack<>();
        
        // Операции push
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Stack: " + stack);
        System.out.println("Top Element: " + stack.peek()); // 30
        
        // Операция pop
        int popped = stack.pop(); // Удаляет 30
        System.out.println("Ge-poppt: " + popped);
        System.out.println("Stack nach pop: " + stack);
        
        // Практическое применение: проверка сбалансированности скобок
        String expression = "{[()]}";
        boolean isBalanced = isBalancedParentheses(expression);
        System.out.println("Ausdruck balanciert: " + isBalanced);
    }
    
    // Проверка сбалансированности скобок со 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();
    }
}

Реализация 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

Принцип FIFO

Queue работает по принципу First-In-First-Out (FIFO) - первый пришедший, первый ушедший.

public class QueueDemo {
    public static void main(String[] args) {
        // Java Queue с LinkedList
        Queue<Integer> queue = new LinkedList<>();
        
        // Операции enqueue
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        
        System.out.println("Queue: " + queue);
        System.out.println("Front Element: " + queue.peek()); // 10
        
        // Операция dequeue
        int dequeued = queue.poll(); // Удаляет 10
        System.out.println("Dequeued: " + dequeued);
        System.out.println("Queue nach dequeue: " + queue);
        
        // Практическое применение: обход в ширину (BFS)
        Graph graph = createSampleGraph();
        List<Integer> bfsResult = bfs(graph, 0);
        System.out.println("BFS Traversal: " + bfsResult);
    }
    
    // BFS с 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() {
        // Реализация примера графа
        return new Graph(6);
    }
}

Реализация очереди

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;
    }
}

Куча

Приоритетная очередь

Кучи это специальные древесные структуры, применяемые в приоритетных очередях.

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("Kleinstes Element: " + minHeap.peek()); // 10
        
        System.out.println("Elemente in Reihenfolge:");
        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("Größtes Element: " + maxHeap.peek()); // 50
        
        // Heap Sort
        int[] array = {50, 20, 30, 10, 40};
        heapSort(array);
        System.out.println("Heap Sort Ergebnis: " + Arrays.toString(array));
    }
    
    // Heap Sort Algorithmus
    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);
        }
    }
}

Реализация минимальной кучи

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();
    }
}

Древесные структуры

Бинарное дерево поиска

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;
    }
}

Демонстрация обхода дерева

public class TreeTraversalDemo {
    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        
        // Вставка элементов
        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("Высота дерева: " + bst.height()); // 3
        System.out.println("Минимум: " + bst.findMin()); // 20
        System.out.println("Максимум: " + bst.findMax()); // 80
        
        // Поиск элементов
        System.out.println("40 найдено: " + bst.search(40)); // true
        System.out.println("90 найдено: " + bst.search(90)); // false
    }
}

Графы

Представления графов

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<>());
        }
    }
    
    // Ориентированный граф
    public void addEdge(int source, int destination) {
        if (source >= 0 && source < vertexCount && 
            destination >= 0 && destination < vertexCount) {
            adjacencyList.get(source).add(destination);
        }
    }
    
    // Неориентированный граф
    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();
    }
}

Алгоритмы на графах

public class GraphAlgorithms {
    
    // Поиск в глубину (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);
            }
        }
    }
    
    // Поиск в ширину (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;
    }
    
    // Алгоритм Dijkstra (кратчайшие пути)
    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;
    }
    
    // Топологическая сортировка
    public static List<Integer> topologicalSort(Graph graph) {
        int n = graph.getVertexCount();
        int[] inDegree = new int[n];
        
        // Подсчёт входящих степеней
        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;
    }
}

Демонстрация работы с графами

public class GraphDemo {
    public static void main(String[] args) {
        // Создание графа
        Graph graph = new Graph(6);
        
        // Добавление рёбер
        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("Граф:");
        System.out.println(graph);
        
        // Обходы
        System.out.println("DFS: " + GraphAlgorithms.dfs(graph, 0));
        System.out.println("BFS: " + GraphAlgorithms.bfs(graph, 0));
        
        // Алгоритм 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("Кратчайшие пути из узла 0: " + shortestPaths);
        
        // Топологическая сортировка 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("Топологический порядок: " + topologicalOrder);
    }
}

Анализ сложности

Сравнение временной сложности

Структура данных	Доступ	Вставка	Удаление	Поиск
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)*

*Амортизированная сложность или средний случай

Пространственная сложность

Структура данных	Память	Примечания
Array	O(n)	Фиксированный размер
Dynamic Array	O(n)	С overhead
Linked List	O(n)	Дополнительные указатели
Binary Search Tree	O(n)	Рекурсивная структура
Graph	O(V + E)	V = вершины, E = рёбра

Рекомендации

1. Выбор правильной структуры данных

// Частые операции поиска -> HashSet/HashMap
Set<String> uniqueNames = new HashSet<>();
Map<String, Integer> wordCount = new HashMap<>();

// Упорядоченные данные -> TreeSet/TreeMap
Set<Integer> sortedNumbers = new TreeSet<>();
Map<String, Integer> sortedWordCount = new TreeMap<>();

// Обработка FIFO -> Queue
Queue<Task> taskQueue = new LinkedList<>();

// Обработка LIFO -> Stack
Stack<Operation> undoStack = new Stack<>();

// Обработка по приоритетам -> PriorityQueue
PriorityQueue<Event> eventQueue = new PriorityQueue<>();

2. Учёт производительности

// Плохо: O(n²) для больших объёмов данных
List<Integer> list = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
    for (int j = 0; j < list.size(); j++) {
        // O(n²) операция
    }
}

// Хорошо: O(n) с HashSet
Set<Integer> set = new HashSet<>();
for (int item : list) {
    set.add(item); // O(1) в среднем
}

Вопросы для подготовки

Типовые задачи

1. Реализуйте Stack с помощью Array
2. Сравните BFS и DFS
3. Объясните Heap Sort
4. Реализуйте Binary Search
5. Вычислите сложность алгоритмов

Ключевые концепции

• Амортизированный анализ: средние затраты на операции
• Best-Case/Worst-Case/Average-Case: различные сценарии
• Space-Time Tradeoff: память против скорости
• Recursion vs Iteration: варианты реализации

Основное

Структуры данных, выбранные правильно, определяют эффективность алгоритмов:

• Arrays: прямой доступ, фиксированный размер
• Stack/Queue: специальный порядок доступа
• Heaps: приоритетные очереди, быстрые операции с минимумом/максимумом
• Деревья: иерархическая организация, эффективный поиск
• Графы: сетевые отношения, сложные алгоритмы

Выбор подходящей структуры данных критичен для производительности и существенно влияет на сложность операций.