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)$)

# 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 $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)$)

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

# Using linked lists

How to use or build the structure in Java

page revision: 0, last edited: 22 Nov 2007 02:22