Arrays are a Fundament Data Structure
📢 Note: This article is part of a series where I explore algorithms and data structures in depth. Stay tuned for more insights and examples as we dive into the world of Big O and beyond! If you’re interested in learning more about algorithms and data structures, I highly recommend The Last Algorithms Course You’ll Need on Frontend Masters. For the rest of this series see the first post: Working Through an Algorithms Course
Table of contents
Open Table of contents
What are arrays
Arrays are a collection of items that are stored in a contiguous block of memory.
Here’s an example of how you might represent an array of strings:
| Index | Value |
|---|---|
| 0 | “a” |
| 1 | “b” |
| 2 | “c” |
| 3 | “d” |
| 4 | “e” |
This table represents an array of 5 elements, where each row corresponds to an element in the array. The “Index” column represents the index of each element (starting from 0), and the “Value” column represents the value stored at that index. In memory, arrays are stored in a contiguous block, meaning each element is placed right next to the other without any gaps. This contiguous storage allows for efficient access to elements by their index, as the memory address of any element can be calculated if the starting address and the size of each element are known.
đź“ť For the purposes of this course and the examples, the important thing to remember is that arrays are preallocated, static chunks of memory. Elements in the array can be accessed by looking at the starting memory address, multiplying the index (of the element you want) by the size of each element, and adding the result to the starting address.
Big O
Can’t forget about the Big O. The time complexity of accessing an element in an array by its index is O(1), as the memory address of the element can be calculated in constant time. On the other hand, searching for an element by value (in an unsorted array) is O(n), as in the worst case, you may need to look at every element in the array to find the one you’re looking for.
When to use an array
Arrays are a great choice when you need to store a collection of items that you want to access by their index, as the memory address of any element can be calculated because the starting address and the size of each element are known.
When not to use an array
Arrays are not a great choice if you need to insert or remove elements frequently, as this can be inefficient due to the need to shift elements around in memory. Additionally, expanding arrays can be inefficient if the array is full, as this requires allocating a new block of memory and copying all the elements from the old array to the new array.
Technically, there are implementations that solve some of these issues like dynamic arrays, but we aren’t covering those in this post.
Next up
Linear search through an array