- Explain how programming languages implement arrays
- Identify the runtime complexity of common array methods in Big O notation
While you may be familiar with arrays, chances are you have not considered what happens when our computer either manipulates an array by adding or removing elements, or retrieves information from an array. In this lesson, we'll discuss what happens when we retrieve or manipulate data in an array.
Understanding how familiar data structures work under the hood will give you a better sense of what's happening at a low level, as well as some clues as to how to determine the Big O of algorithms that use these data structures.
When we initialize an array in a programming language, the language allocates
space in memory for your array, and then points that starting variable to that
address in memory. Then the program assigns a fixed amount of memory for each
element.
Let's say my array say starts at memory address 100. Assume that the programming language allocates eight bits of memory for each element in the array, and that it allocates enough space for ten elements evenly spaced in memory.
Now, let's try to think through how a computer program retrieves an element at a specific index.
let myAarr = ["a"];
myAarr[0] = "a";
When we initialize the array and assign the letter "a"
as the first element,
the programming language assigns the letter "a"
to a specific space in memory.
In our example, address 100. So then, when we call myArr[0]
all the program
has to do is go to address 100, and retrieve the element.
So now, what do you think happens if we call myArr[3]
, to return what is in
that slot. If the myArr
begins at address 100, and we allocate eight bits of
space for each, what address does the program go to to retrieve the element at
index 3?
Is there a formula that we can come up with for retrieval? Yep!
100 + 3 * 8 = 124
Our programming language knows that if eight bits are allocated to each element, and then to retrieve an element at a specific index, the program simply visits an address by using the following formula:
memoryLocationOfElement = arrayStartAddress + indexNumber * bitAllocation
Now that we talked about retrieving elements from an array, let's talk about removing elements from an array.
let arr = [1, 24, 48, 9];
arr.pop;
// 9
arr;
// [1, 24, 48]
Performing an operation like pop
is fairly simple. Let's assume that our array
begins at memory address 100:
memory address | 100 | 108 | 116 | 124 |
---|---|---|---|---|
arr |
1 | 24 | 48 | 9 |
arr.pop |
1 | 24 | 48 | X |
Removing from the end of the array is not so bad. But removing an element from the beginning involves a lot more:
memory address | 100 | 108 | 116 | 124 |
---|---|---|---|---|
arr |
1 | 24 | 48 | 9 |
arr.shift |
24 | 48 | 9 | X |
Looking at the chart above, shifting involves moving every remaining element to a new space in memory. The cost is equal to the number of elements in the array. So the time complexity of shifting is Big O(n). Adding elements to the beginning of the array also will cost Big O(n), as every subsequent element would have to move to different spot in memory:
memory address | 100 | 108 | 116 | 124 | 132 |
---|---|---|---|---|---|
arr |
1 | 24 | 48 | 9 | X |
arr.unshift(5) |
5 | 1 | 24 | 48 | 9 |
So unshift
is Big O(n) and shift
is Big O(n). However, pop
and accessing
elements using their index positions take the same amount of time regardless the
size of the array. That is, the time complexity is Big O(1), meaning that the
cost of the operation does not depend on the number of elements in the array.
Remember that to retrieve information from an array, we simply need to apply the
formula startingAddress + index * bitAllocation
and go to the corresponding
address. One problem that occurs with having all of these contiguous elements
is that we must allocate a specific amount of space โ say enough space for six
elements. What happens when we want to add an seventh element?
memory address | 100 | 108 | 116 | 124 | 132 | 140 |
---|---|---|---|---|---|---|
arr |
1 | 24 | 48 | 9 | 32 | song.mp3 |
arr.push(5) |
1 | 24 | 48 | 9 | 32 | song.mp3 |
Do you see our problem? We want to push another element, but something else is on those eight bits. If we move our new element to a different location, our formula for retrieving elements no longer works. Instead, we copy our array into a new location in memory where there is enough space. However, notice that the cost of doing this is Big O(n), as we must incur a cost for each element we copy over.
new memory address | 300 | 308 | 316 | 324 | 332 | 340 |
---|---|---|---|---|---|---|
arr |
1 | 24 | 48 | 9 | 32 | X |
arr.push(5) |
1 | 24 | 48 | 9 | 32 | 5 |
We saw in this section that some of the strengths and weaknesses of using an array. Retrieving elements by index and adding elements to the end of the array has a time complexity of Big O(1), while adding or removing elements at the beginning of an array is Big O(n). We also saw that because operations in our array rely on using neighboring locations in memory, we can run out of space.
Here's a summary of the Big O of common array methods:
Method | Big O |
---|---|
Access | O(1) |
Search | O(n) |
Insertion (end) | O(1) |
Insertion (beginning) | O(n) |
Deletion (end) | O(1) |
Deletion (beginning) | O(n) |
For problems that rely on adding or removing elements from the beginning, you're better off using a linked list, as we saw in a previous lesson. Arrays are quick for accessing elements when you know their index position, and for adding and removing items from the end.