datenstrukturen

Data Structures

In short: An umbrella term for standardised ways of organising and storing data so that certain operations (searching, inserting, sorting) are possible efficiently.

In more detail: The choice of the right data structure has a big influence on a program’s performance — an array, for example, is fast for direct access via an index, but slow for inserting in the middle; a linked list is the reverse. Collections bundle the most common data structures (lists, sets, mappings) into a shared, reusable library.

In Depth

The core idea: there’s no “best” data structure — each makes a deliberate trade-off between different operations, and the right choice depends on which operation occurs most frequently in the specific use case.

                    Access by index     Insert (middle)     Search (unsorted)
Array               O(1) fast           O(n) slow           O(n)
Linked list         O(n) slow           O(1) fast           O(n)
Hash set/map        -                   O(1) fast           O(1) fast (hashing)
Balanced tree       -                   O(log n)            O(log n), also sorted

This table shows the fundamental pattern: a structure that shines in one column is often especially poor in another. An array reads fast, because the memory address of an element can be calculated directly from its index — but inserting an element in the middle means shifting all subsequent elements in memory. A linked list instead links elements via pointers/references, which makes inserting lightning-fast (just relinking two pointers), but direct access to the nth element means working your way through from the start.

Choosing the right data structure therefore always starts with the question: “Which operation do I perform most often?”

• Frequently accessing by index/key, rarely inserting → array or hash map.
• Frequently inserting or removing at the start/end, rarely random access → linked list, queue, or stack.
• Frequently checking for duplicates or testing membership → set.
• Order/sorting has to be preserved and be efficiently searchable → balanced tree (e.g. TreeSet/TreeMap).

A data structure mismatch usually only becomes noticeable with growing amounts of data — for 100 elements, practically any structure is “fast enough”, for 10 million the difference between O(n) and O(log n) or O(1) becomes the decisive factor in whether a program responds in milliseconds or minutes.

See also: Arrays, Collections, Algorithms