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

Datenstrukturen sind fundamentale Konzepte der Informatik, die Daten organisieren und verwalten. Die Wahl der richtigen Datenstruktur beeinflusst die Effizienz von Algorithmen maßgeblich.

Was sind Datenstrukturen?

Datenstrukturen definieren, wie Daten gespeichert, organisiert und zugegriffen werden. Sie bestimmen die Komplexität von Operationen wie Einfügen, Löschen und Suchen.

Klassifikation von Datenstrukturen

1. Lineare Strukturen: Array, Stack, Queue, Linked List
2. Hierarchische Strukturen: Baum, Heap
3. Netzwerkstrukturen: Graph
4. Hash-basierte Strukturen: Hash Table, Hash Set

Array (Feld)

Grundlagen

Arrays sind die einfachste Datenstruktur mit direktem Indexzugriff.

public class ArrayDemo {
    public static void main(String[] args) {
        // Statisches Array
        int[] numbers = new int[5];
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;
        
        // Dynamisches Array (ArrayList)
        List<Integer> dynamicArray = new ArrayList<>();
        dynamicArray.add(10);
        dynamicArray.add(20);
        dynamicArray.add(30);
        
        // Array Operationen
        System.out.println("Element bei Index 2: " + numbers[2]); // O(1)
        
        // Lineare Suche
        int index = linearSearch(numbers, 30); // O(n)
        System.out.println("30 gefunden bei Index: " + index);
        
        // Sortieren mit Binary Search
        Arrays.sort(numbers); // O(n log n)
        int sortedIndex = Arrays.binarySearch(numbers, 30); // O(log n)
        System.out.println("30 (sortiert) bei Index: " + sortedIndex);
    }
    
    // Lineare Suche im 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; // Nicht gefunden
    }
}

Dynamisches Array Implementierung

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();
        }
        
        // Elemente nach links verschieben
        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 (Stapel)

LIFO Prinzip

Stacks folgen dem Last-In-First-Out (LIFO) Prinzip.

public class StackDemo {
    public static void main(String[] args) {
        // Java Stack
        Stack<Integer> stack = new Stack<>();
        
        // Push Operationen
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Stack: " + stack);
        System.out.println("Top Element: " + stack.peek()); // 30
        
        // Pop Operation
        int popped = stack.pop(); // Entfernt 30
        System.out.println("Ge-poppt: " + popped);
        System.out.println("Stack nach pop: " + stack);
        
        // Praktische Anwendung: Klammerprüfung
        String expression = "{[()]}";
        boolean isBalanced = isBalancedParentheses(expression);
        System.out.println("Ausdruck balanciert: " + isBalanced);
    }
    
    // Klammerprüfung mit 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 Implementierung

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 (Warteschlange)

FIFO Prinzip

Queues folgen dem First-In-First-Out (FIFO) Prinzip.

public class QueueDemo {
    public static void main(String[] args) {
        // Java Queue mit LinkedList
        Queue<Integer> queue = new LinkedList<>();
        
        // Enqueue Operationen
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        
        System.out.println("Queue: " + queue);
        System.out.println("Front Element: " + queue.peek()); // 10
        
        // Dequeue Operation
        int dequeued = queue.poll(); // Entfernt 10
        System.out.println("Dequeued: " + dequeued);
        System.out.println("Queue nach dequeue: " + queue);
        
        // Praktische Anwendung: Breadth-First Search
        Graph graph = createSampleGraph();
        List<Integer> bfsResult = bfs(graph, 0);
        System.out.println("BFS Traversal: " + bfsResult);
    }
    
    // BFS mit 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() {
        // Implementierung für Beispielgraph
        return new Graph(6);
    }
}

Queue Implementierung

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 (Haufen)

Priority Queue

Heaps sind spezielle Baumstrukturen für Priority Queues.

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

Min-Heap Implementierung

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

Baumstrukturen

Binary Search Tree

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

Baum Traversal Demo

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("Baumhöhe: " + bst.height()); // 3
        System.out.println("Minimum: " + bst.findMin()); // 20
        System.out.println("Maximum: " + bst.findMax()); // 80
        
        // Suchen
        System.out.println("40 gefunden: " + bst.search(40)); // true
        System.out.println("90 gefunden: " + bst.search(90)); // false
    }
}

Graphen

Graph Repräsentationen

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<>());
        }
    }
    
    // Gerichteter Graph
    public void addEdge(int source, int destination) {
        if (source >= 0 && source < vertexCount && 
            destination >= 0 && destination < vertexCount) {
            adjacencyList.get(source).add(destination);
        }
    }
    
    // Ungerichteter Graph
    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();
    }
}

Graph Algorithmen

public class GraphAlgorithms {
    
    // Depth-First Search (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);
            }
        }
    }
    
    // Breadth-First Search (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's Algorithmus (kürzeste Wege)
    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;
    }
    
    // Topological Sort
    public static List<Integer> topologicalSort(Graph graph) {
        int n = graph.getVertexCount();
        int[] inDegree = new int[n];
        
        // In-Degree berechnen
        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;
    }
}

Graph Demo

public class GraphDemo {
    public static void main(String[] args) {
        // Graph erstellen
        Graph graph = new Graph(6);
        
        // Kanten hinzufügen
        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("Graph:");
        System.out.println(graph);
        
        // Traversierungen
        System.out.println("DFS: " + GraphAlgorithms.dfs(graph, 0));
        System.out.println("BFS: " + GraphAlgorithms.bfs(graph, 0));
        
        // Dijkstra Algorithmus
        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("Kürzeste Wege von Knoten 0: " + shortestPaths);
        
        // Topological Sort für 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("Topologische Sortierung: " + topologicalOrder);
    }
}

Komplexitätsanalyse

Zeitkomplexität Vergleich

Datenstruktur	Zugriff	Einfügen	Löschen	Suchen
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)*

*Amortisierte Komplexität oder Durchschnittsfall

Speicherkomplexität

Datenstruktur	Speicher	Bemerkungen
Array	O(n)	Feste Größe
Dynamic Array	O(n)	Mit Overhead
Linked List	O(n)	Zusätzliche Pointer
Binary Search Tree	O(n)	Rekursive Struktur
Graph	O(V + E)	V = Knoten, E = Kanten

Best Practices

1. Richtige Datenstruktur wählen

// Häufige Suchoperationen -> HashSet/HashMap
Set<String> uniqueNames = new HashSet<>();
Map<String, Integer> wordCount = new HashMap<>();

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

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

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

// Prioritätsverarbeitung -> PriorityQueue
PriorityQueue<Event> eventQueue = new PriorityQueue<>();

2. Performance Überlegungen

// Schlecht: O(n²) für große Datenmengen
List<Integer> list = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
    for (int j = 0; j < list.size(); j++) {
        // O(n²) Operation
    }
}

// Gut: O(n) mit HashSet
Set<Integer> set = new HashSet<>();
for (int item : list) {
    set.add(item); // O(1) durchschnittlich
}

Prüfungsrelevante Fragen

Typische Aufgaben

1. Implementieren Sie einen Stack mit Array
2. Vergleichen Sie BFS und DFS
3. Erklären Sie Heap Sort
4. Implementieren Sie Binary Search
5. Berechnen Sie die Komplexität von Algorithmen

Wichtige Konzepte

• Amortisierte Analyse: Durchschnittliche Kosten über Operationen
• Best-Case/Worst-Case/Average-Case: Verschiedene Szenarien
• Space-Time Tradeoff: Speicher vs. Geschwindigkeit
• Recursion vs Iteration: Implementierungsvarianten

Zusammenfassung

Datenstrukturen sind fundamental für effiziente Algorithmen:

• Arrays: Direkter Zugriff, feste Größe
• Stack/Queue: Spezielle Zugriffsreihenfolgen
• Heaps: Priority Queues, effiziente Min/Max Operationen
• Bäume: Hierarchische Organisation, effizientes Suchen
• Graphen: Netzwerkbeziehungen, komplexe Algorithmen

Die Wahl der richtigen Datenstruktur ist entscheidend für die Performance und beeinflusst die Komplexität von Operationen maßgeblich.