A Linked list is a linear collection of data elements.
Linked lists differ from arrays in that they can utilise non-contiguous blocks of memory, with each data element ('node') pointing to the next in the list.
With a Singly linked list each node points to the next node in the list, providing forwards-only access to nodes:
With a Doubly linked list each node points to the previous and next node in the list:
🔔 Complexity is considered in terms of worst case.
| Insertion | Removal | Retrieval | Notes | |
|---|---|---|---|---|
| Singly linked list | Θ(1) | Θ(n) | Θ(n) | |
| Doubly linked list | Θ(1) | Θ(1) | Θ(n) |
TODO
A doubly linked list does not have to be traversed to find the previous node as the node being removed includes a reference to it.