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 $O(1)$ appends an item to the end of the list
pop_front $O(1)$ removes an item from the front of the list
access_element $O(n)$ access the $n^\text{th}$ element of the list
iterate $O(n)$ iterate through every element of the list (each step is $O(1)$)

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 $O(1)$ appends an item to the end of the list
push_front $O(1)$ appends an item to the front of the list
pop_back $O(1)$ removes an item from the end of the list
pop_front $O(1)$ removes an item from the front of the list
access_element $O(n)$ access the $n^\text{th}$ element of the list
iterate $O(n)$ iterate through every element of the list (each step is $O(1)$)
iterate_reverse $O(n)$ iterate through every element of the list in reverse order (each step is $O(1)$)