Linked list
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
which stores the contents of the node, and .next
which is 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.
Adding nodes
To add a new node with data
to the start of a linked list:
- Create a new node containing
data
- Point the
.next
of the new node to the current first node - Point the start of the list
first
to the new node
This runs in time.
Removing nodes
To remove data from a linked list:
- If the first node
.data
is equal to data:- Point the start of the list to the node after the first node
- Otherwise:
- Find a node
prev
just before a node with.data
equal to data - Point
prev.next
toprev.next.next
, skipping the node being removed
- Find a node
Finding the node to remove runs in time. Removing the node runs in time. If the previous node to the node to be removed is already available, for example during iteration, then removing the node always runs in 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.