# 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`

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.

### Adding

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 to the new node

This runs in $O(1)$ time.

### Removing

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`

to `prev.next.next`

skipping 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.

λ linked-list