This is an old revision of the document!
A linked list is a data structure composed of a group of nodes, each node linking to the next node in the sequence. Each node consist of two elements,
.data storing the contents of the node and
.next a reference to the next node.
Linked lists are one of the simplest data structures. They allow for efficient insertion or removal of elements from any position in the sequence.
To add a new node with
data to the start of a linked list:
.nextof the new node to the current first node
This runs in $O(1)$ time.
To remove data from a linked list:
.datais equal to data:
prevjust before a node with
.dataequal to data
prev.next.nextskipping the node being removed
Finding the node to remove runs in $O(n)$ time. Removing the node runs in $O(1)$ time. If the previous node to the node to be removed is already available then removing the node always runs in $O(1)$ time.
This visualisation allows the adding or removal of nodes to a linked list. Use the buttons on the right of the code to trigger running the commands on the list.