liste-datenstruktur

List

In short: An ordered data structure that holds elements in a fixed order and allows duplicates — every element can be addressed via its position (index).

In more detail: Unlike a classic array, a list can dynamically grow and shrink in most languages. Common implementations are the dynamic array (fast index access, slower insertion in the middle) and the linked list (fast insertion/removal, slower index access).

In Depth

Choosing the right list implementation is a classic example of there being no single best data structure — only the best one for a specific use case:

# Dynamic array: good for read access by index
list[500]              # O(1) - direct jump to the memory position
 
# Linked list: good for inserting/removing in the middle
list.insertAt(500, newElement)  # O(1), once you're at the spot

For a dynamic array, all elements sit consecutively in memory, which is why access by index is lightning fast (the memory address can be calculated directly). If the capacity is exceeded, a larger block of memory has to be reserved internally and ALL existing elements copied there — this happens rarely, but costs more time briefly when it does.

For a linked list, every element is its own standalone “node”, which additionally contains a reference to the next (and, for a doubly linked list, also the previous) node. Inserting a new element just means relinking a few references — no copying needed. The downside: to access the 500th element, you have to follow EVERY single reference in sequence starting from the beginning, there’s no direct jump.

Rule of thumb for choosing: mostly read by index, rarely insert/remove in the middle → dynamic array. Frequently insert/remove at arbitrary positions, rarely random access by index → linked list. In practice, the dynamic array (in most languages simply “the list” as such) is by far the more common default case.

See also: ArrayList, LinkedList, Collections