In this part of the book, we explored the most used linear data structures such as Arrays, Linked Lists, Stacks, and Queues. We implemented them and discussed the runtime of their operations.
-
You need to access data in random order fast (using an index).
-
Your data is multi-dimensional (e.g., matrix, tensor).
-
You will access your data sequentially.
-
You want to save memory and only allocate memory as you need it.
-
You want constant time to remove/add from extremes of the list.
-
You need to access your data on a first-come, first-served basis (FIFO).
-
You need to implement a Breadth-First Search
-
You need to access your data as last-in, first-out (LIFO).
-
You need to implement a Depth-First Search
Data Structure |
Searching By |
Inserting at the |
Deleting from |
Space |
|||||
Index/Key |
Value |
beginning |
middle |
end |
beginning |
middle |
end |
||
O(1) |
O(n) |
O(n) |
O(n) |
O(1) |
O(n) |
O(n) |
O(1) |
O(n) |
|
O(n) |
O(n) |
O(1) |
O(n) |
O(n) |
O(1) |
O(n) |
O(n) |
O(n) |
|
O(n) |
O(n) |
O(1) |
O(n) |
O(1) |
O(1) |
O(n) |
O(1) |
O(n) |
|
- |
- |
- |
- |
O(1) |
- |
- |
O(1) |
O(n) |
|
Queue (w/array) |
- |
- |
- |
- |
O(1) |
O(n) |
- |
- |
O(n) |
part02-linear-data-structures.asc (w/list) |
- |
- |
- |
- |
O(1) |
O(1) |
- |
- |
O(n) |