verkettete-liste

LinkedList

In short: A list where every element (node) contains a reference to the next (and often also the previous) element, instead of sitting contiguously in memory as with an array.

In more detail: This makes inserting and removing very fast, once you already know the right spot — only the references have to be relinked, no block of memory has to be shifted. Access via an index, by contrast, is slow, because the list has to be walked node by node from the start to reach a specific position — unlike the direct access of a dynamic array.

In Depth

Every node of a linked list typically consists of two parts: the actual value and a reference to the next node (for a doubly linked list, additionally to the previous one):

Node {
    value
    next: Node | null
}
 
# List 1 -> 2 -> 3 -> null
head = Node(1, Node(2, Node(3, null)))

To insert a new element in the middle, only two references have to be relinked — regardless of how long the list already is:

# Insert a new element between "current" and "current.next"
newNode.next = current.next
current.next = newNode

That’s exactly the decisive advantage over a dynamic array: for an array, inserting in the middle would have to shift ALL subsequent elements by one position (effort proportional to list length), for a linked list it’s always equally fast regardless of the total length — provided you already have the insertion point as a reference (finding this point itself, by contrast, is slow for a linked list, since it requires sequentially walking from the start).

A doubly linked list (every node also knows its predecessor) allows traversing backwards as well and removing an element with no need to separately search for the previous node first — but costs somewhat more memory per node for the additional reference.

In practice, a dynamic array is the significantly more commonly used default list (faster index access, better cache locality, because the elements sit contiguously in memory) — a linked list is worthwhile especially when insertion/removal at arbitrary positions happens very frequently and index access is rarely needed, such as for certain queue or editor implementations.

See also: List, ArrayList, Index