Before discussing algorithms, we need to cover the data structures they commonly rely on. Some algorithms are only efficient because of a specific underlying data structure. This post covers the most fundamental ones.
Array and list
Array
To store multiple data items, we need a data structure that allows reading and writing at any position. The simplest such structure is an array. An array stores data in contiguous memory, so any element can be accessed in constant time via its index. In mathematical notation, it is written as $a[0]$ or $a_0$. The main drawback is the fixed size: you must know the maximum number of elements in advance, or risk accessing unintended memory. An array can be dynamically resized by allocating a new, larger array and copying all elements, though this is costly. The time complexity of array operations is as follows.
| Time complexity | Array |
|---|---|
| Search/Change | $O(1)$ |
| Add (Front) | $O(n)$ |
| Add (Random) | $O(n)$ |
| Add (Back) | $O(n)$ |
| Delete (Front) | $O(n)$ |
| Delete (Random) | $O(n)$ |
| Delete (Back) | $O(n)$ |
| Merge | $O(n)$ |
| Space complexity | $O(n)$ |
Notice that adding and delete will change the size of the array. Merge means that merging two array into a single array. It will be assumed to have the same size of two arrays.
List 1 (Singly-Linked List)
To avoid the fixed-size problem, we use a linked list. A linked list consists of nodes, each holding a data value and a pointer to the next node. This allows dynamic insertion and deletion, but accessing an arbitrary element requires traversing from the head — taking $O(n)$ time.
| Time complexity | List 1 |
|---|---|
| Search/Change | $O(n)$ |
| Add (Front) | $O(1)$ |
| Add (Random) | $O(n)$ |
| Add (Back) | $O(n)$ |
| Delete (Front) | $O(1)$ |
| Delete (Random) | $O(n)$ |
| Delete (Back) | $O(n)$ |
| Merge | $O(n)$ |
| Space complexity | $O(n)$ |
Another limitation is that inserting at the back takes $O(n)$ because we must traverse to the tail.
List 2 (Singly-Linked List with Tail Pointer)
Adding a tail pointer gives $O(1)$ access to the end of the list. This improves back-insertion and deletion, and enables $O(1)$ merging of two lists by connecting the tail of one to the head of the other.
| Time complexity | List 2 |
|---|---|
| Search/Change | $O(n)$ |
| Add (Front) | $O(1)$ |
| Add (Random) | $O(n)$ |
| Add (Back) | $O(1)$ |
| Delete (Front) | $O(1)$ |
| Delete (Random) | $O(n)$ |
| Delete (Back) | $O(1)$ |
| Merge | $O(1)$ |
| Space complexity | $O(n)$ |
However, random access still takes $O(n)$. Linked lists are rarely used directly in implementations for this reason, but the conceptual abstraction is widely used in other data structures.
Other lists
There are another way to implement the list. Followings are the common thing that could be tried.
Double-Sizing Array (Dynamic Array / Vector)
A double-sizing array behaves like a regular array but doubles its capacity when it runs out of space. Back insertions and deletions are amortized $O(1)$ — most are $O(1)$, with occasional $O(n)$ resizes.
| Time complexity | Vector |
|---|---|
| Search/Change | $O(1)$ |
| Add (Front) | $O(n)$ |
| Add (Random) | $O(n)$ |
| Add (Back) | Amortized $O(1)$ |
| Delete (Front) | $O(n)$ |
| Delete (Random) | $O(n)$ |
| Delete (Back) | Amortized $O(1)$ |
| Merge | $O(n)$ |
| Space complexity | $O(n)$ |
Circular Array
A circular array uses a virtual index mapping instead of direct index access. In other words, we access $a[f(i)]$ instead of $a[i]$, where $f$ is a mapping function. Using $f(i) = (i + \mathit{from}) \bmod \mathit{size}$, where $\mathit{from}$ can shift, we achieve $O(1)$ front and back insertions and deletions — similar to List 2, but in a contiguous memory block. In this case, complexity works like below.
| Time complexity | Array |
|---|---|
| Search/Change | $O(1)$ |
| Add (Front) | $O(1)$ |
| Add (Random) | $O(n)$ |
| Add (Back) | $O(1)$ |
| Delete (Front) | $O(1)$ |
| Delete (Random) | $O(n)$ |
| Delete (Back) | $O(1)$ |
| Merge | $O(n)$ |
| Space complexity | $O(n)$ |
Comparison
Complexity
DSA means the Double sizing array and CA means Circular array.
| Time complexity | Array | List 1 | List 2 | DSA | CA |
|---|---|---|---|---|---|
| Search/Change | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ | $O(1)$ |
| Add (Front) | $O(n)$ | $O(1)$ | $O(1)$ | $O(n)$ | $O(1)$ |
| Add (Random) | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Add (Back) | $O(n)$ | $O(n)$ | $O(1)$ | Amortized $O(1)$ | $O(1)$ |
| Delete (Front) | $O(n)$ | $O(1)$ | $O(1)$ | $O(n)$ | $O(1)$ |
| Delete (Random) | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Delete (Back) | $O(n)$ | $O(n)$ | $O(1)$ | Amortized $O(1)$ | $O(1)$ |
| Merge | $O(n)$ | $O(n)$ | $O(1)$ | $O(n)$ | $O(n)$ |
| Space complexity | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
Example code
Here is the simple example of arrays.
1 | |
Performance
Performance depends on the hardware and compiler. Tests were run on a Raspberry Pi; results are shown below.
Without compiler optimization option
| Time consumption | Basic array | Circular array | std::vector | Basic/Circular | std/circular |
|---|---|---|---|---|---|
| Insert first | 5.43E+08 | 730299 | 80218289 | 743.5641 | 109.8431 |
| Erase first | 5.07E+08 | 249735 | 77053027 | 2030.535 | 308.5392 |
| Insert middle | 2.72E+08 | 2.63E+08 | 64868023 | 1.03441 | 0.246638 |
| Erase middle | 3.69E+08 | 93046427 | 60962537 | 3.963127 | 0.655184 |
| Insert random | 2.69E+08 | 1.32E+08 | 67554999 | 2.028211 | 0.510193 |
| Erase random | 2.79E+08 | 1.34E+08 | 61448193 | 2.081033 | 0.457566 |
With compiler optimization option
| Time consumption | Basic array | Circular array | std::vector | Basic/Circular | std/circular |
|---|---|---|---|---|---|
| Insert first | 69745452 | 243124 | 72715663 | 286.8719 | 299.0888 |
| Erase first | 19728613 | 352 | 70335698 | 56047.2 | 199817.3 |
| Insert middle | 28044463 | 33800611 | 58150249 | 0.829703 | 1.72039 |
| Erase middle | 13088558 | 7911878 | 58191397 | 1.654292 | 7.354941 |
| Insert random | 29029662 | 11617777 | 59405666 | 2.498728 | 5.113342 |
| Erase random | 9968517 | 11553333 | 57890608 | 0.862826 | 5.010728 |