The Self-Taught Computer Scientist

Chapter 10 Linked Lists
103
You can iterate through a singly linked list only by starting at the head and moving to the end. 
You can iterate through a doubly linked list from the head to the end, but you can also go backward 
between nodes.
In a circular linked list, the last node points back to the first node, which allows you to go from 
the last element of the list back to the front of the list (Figure 10.6). This type of data structure is 
useful in applications that repeatedly cycle through data that doesn’t have a clear beginning or ending 
point. For example, you could use a circular linked list to track players in a round- robin online game, 
or you could use a circular list in a resource pooling environment where users take turns using allo-
cated slices of CPU time. A linked list contains a cycle when any node points back to a previous node.
Linked List Performance
In an array, you can access an item in constant time if you know its index. However, the only way to 
access an element in a linked list is to do a linear search for it, which is O(
n) (Figure 10.7). Adding 
and removing a node in a linked list, on the other hand, is O(1), whereas inserting and deleting items 
from an array is O(
n). This difference is the most significant advantage of using a linked list over an 
array. Finally, searching a linked list, like an array, is also O(
n).
0x41860
“a”
“f”
0x41861 0x41862 0x41863 0x41864 0x41865
“b”
“c”
“d”
“e”
Figure 10.6: A circular linked list points from the 
end back to the head.
Data 
Structure
Time Complexity
Average
Worst
Access
Search
Insertion Deletion
Access
Search
Insertion Deletion
Array
O(1)
O(n)
O(n)
O(n)
O(1)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Queue
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Linked 
List
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Hash 
Table
N/A
O(1)
O(1)
O(1)
N/A
O(n)
O(n)
O(n)
Binary 
Search 
Tree
O(log n)
O(log n)
O(log n)
O(log n)
O(n)
O(n)
O(n)
O(n)