Stufe 5·Software-Handwerk

Data Structures & Algorithms

Big-O, arrays, lists, stacks, queues, trees, graphs, hashing, sorting, and searching.

26 Min. LesezeitExperte

Deutsche Übersetzung in Arbeit

Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.

Auf dieser Seite

Data structures and algorithms (DSA) are the foundation of efficient software - and a favorite in technical interviews. This lesson gives you the mental models: how to measure efficiency with Big-O, the core data structures, and the classic algorithms.

Big-O: measuring efficiency

Big-O notation describes how an algorithm's work grows as the input grows. It's not about seconds - it's about scaling.

Big-O is about how things scale, not raw speed

Finding a friend's name in a phone book: flipping page by page (linear) is fine for 10 names but agony for 10 million. Opening to the middle and halving each time (binary search) barely slows down even for billions. Big-O captures that difference in how the effort grows - which matters far more at scale than raw speed on tiny inputs.

Common complexities, best to worst:

Big-O	Name	Example
O(1)	Constant	Access an array element by index
O(log n)	Logarithmic	Binary search
O(n)	Linear	Scan every element once
O(n log n)	Linearithmic	Efficient sorting (mergesort)
O(n²)	Quadratic	Nested loops over the same data

Always aim for the lowest complexity your problem allows.

Core data structures

Array - fixed-size, O(1) index access, but resizing/inserting is costly.

Linked list - nodes chained by references. O(1) insert/remove at ends, but O(n) to reach an index.

Stack - Last-In-First-Out (LIFO). Think of a stack of plates.

Queue - First-In-First-Out (FIFO). Think of a line at a shop.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
System.out.println(stack.pop());   // 2  (last in, first out)

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
System.out.println(queue.poll());  // 1  (first in, first out)

Hash table - key → value with average O(1) lookup (Java's HashMap). Powered by hashing.

Tree - hierarchical nodes. A binary search tree keeps data sorted for O(log n) search. Trees model file systems, org charts, and more.

Graph - nodes connected by edges. Models networks: social graphs, maps, dependencies.

Choosing a data structure is choosing a tool

You wouldn't hammer a screw. Need fast lookup by key? A hash table. Need sorted order? A tree. Need last-in-first-out? A stack. Half of writing efficient code is picking the right structure for the job.

Searching

Linear search - check each element: O(n). Works on any list.

Binary search - on sorted data, repeatedly halve the search range: O(log n).

int[] sorted = { 1, 3, 5, 7, 9, 11 };
int index = Arrays.binarySearch(sorted, 7);   // 3

Sorting

Sorting is so common Java does it for you - usually an efficient O(n log n) algorithm:

int[] nums = { 5, 2, 8, 1 };
Arrays.sort(nums);                     // [1, 2, 5, 8]

List<String> names = new ArrayList<>(List.of("Bob", "Ada"));
names.sort(Comparator.naturalOrder()); // [Ada, Bob]
names.sort(Comparator.comparingInt(String::length));  // by length

Understanding the classics still matters:

Bubble/insertion sort - simple, O(n²), only for tiny or nearly-sorted data.
Merge sort - divide, sort halves, merge: reliable O(n log n).
Quick sort - partition around a pivot: fast O(n log n) average, used widely.

Know them, but use the library

In real code, call Arrays.sort or Collections.sort - they're highly optimized. Learn how sorting algorithms work to understand trade-offs and to pass interviews, but don't reinvent them in production.

Recursion

Many algorithms are elegant when a method calls itself, breaking a problem into smaller versions:

int factorial(int n) {
    if (n <= 1) return 1;          // base case - stops the recursion
    return n * factorial(n - 1);   // recursive case
}

Every recursion needs a base case to stop, or it recurses forever and throws StackOverflowError.

Quick check

An algorithm does a nested loop over the same list (for each element, scan all elements). What's its Big-O?

Key takeaways

Big-O describes how work grows with input size - focus on scaling, not raw speed.
Key structures: arrays, linked lists, stacks (LIFO), queues (FIFO), hash tables, trees, graphs.
Binary search is O(log n) but needs sorted data; linear search is O(n) on anything.
Efficient sorting is O(n log n); use Arrays.sort/Collections.sort in real code.
Recursion solves problems by calling itself - always include a base case to stop.

Next, we shift from efficiency to elegance: the principles of clean code.