A linked list is, quite simply, a list in which each element is linked to the next, much like a chain. A linked list commonly keeps pointers to the first and last element, with elements pointing to the next one. Then, one can quickly add elements to the end or remove elements from the front. For this reason, linked lists are very useful in implementing queues. However, since there is no structure in memory, accessing an arbitrary element of the list is very slow.
| Operation | Complexity | Description |
|---|---|---|
| push_back |  |
appends an item to the end of the list |
| pop_front | |
removes an item from the front of the list |
| access_element |  |
access the  element of the list |
| iterate | |
iterate through every element of the list (each step is ) |
Doubly linked lists
A doubly linked list is a linked list in which every node also keeps a pointer to the previous node. This is useful when you want to be able to add and remove items from both ends, rather than just one. However, this comes at a cost of memory space required to hold all the pointers.
| Operation | Complexity | Description |
|---|---|---|
| push_back | |
appends an item to the end of the list |
| push_front | |
appends an item to the front of the list |
| pop_back | |
removes an item from the end of the list |
| pop_front | |
removes an item from the front of the list |
| access_element | |
access the element of the list |
| iterate | |
iterate through every element of the list (each step is ) |
| iterate_reverse | |
iterate through every element of the list in reverse order (each step is ) |
Circular linked lists
A circular linked list is a linked list or a doubly linked list where the node after the last node is the first node. That is, you get a circle if you keep going to the next one. These have the same runtimes as the normal versions, but have their own uses, notably in fibonacci heaps.
