Intermediate · 30 minYou are hereRead
Singly linked lists
A linked list is a chain of nodes on the heap, each holding a key and the address of the next. Inserting means re-aiming two pointers, in the right order.
Lists, stacks and queues
Linked lists
Lessons on this topic
Intermediate · 25 minYou are hereRead
Removing from a linked list
To remove a node, make the link that points to it point past it, then free it. A pointer to that link treats the head like any other link.
Intermediate · 25 minYou are hereRead
Reversing a list
A list is reversed in place in one walk with three pointers, turning each arrow round. No node moves.
Intermediate · 25 minYou are hereRead
Merging sorted lists
Two sorted lists merge into one by re-aiming arrows, with no copying and no new nodes. A dummy node at the start removes the special case of the first link.
Intermediate · 30 minYou are hereRead
Circular lists
When the last node points back to the first, one pointer to the last node reaches both ends. A walk stops where it started, and a slow and a fast pointer tell whether a list loops.
Intermediate · 30 minYou are hereRead
Doubly linked lists
A second pointer to the previous node, and a sentinel node closing the ring, let a list insert or remove any node in a fixed number of steps with no special cases.
Intermediate · 30 minYou are hereRead
Skip lists
Stacking sparser lists above a sorted list, each node promoted by coin flips, gives searches that skip ahead and take about log₂ n steps on average, with no rebalancing.
Related topics