Arrays, behind the scenes
What is an array? How is an array stored in memory? Review Push and Pop operations.
What is an array? Basically an array is a collection of items [1,2,3,4,5]. Usually, developers do some standard manipulation with an array, like pop and push items, but what happens when we call one of those operations? To understand this we first need to know how an array is stored in memory.
Array in memory
int array[4] = {1,2,3,4};With this line of code, we created a static array that contains the four integers, but what exactly happened? The compiler will see that we need to create an array of integers and for this it needs to ask for memory, but how much? If we check integer size sizeof(array[0]); we will get 4 bytes, so to store our array we need 16 bytes 4 * 4 = 16 . Computer memory is organized into memory cells, each storing 8 bits and has an index number. One byte equals 8 bits, so each item will use 4 memory cells or 32 bits. We can see the full picture on the image.
We see on the image some computer memory with a 25 memory cells. Now we can see that our array took 16 memory cells or 128 bits.
Push element to the array
A push operation means to add a new element to the end of an array. The question is, is it possible to add an element to the array at all? And the answer, No. What if I want to add another integer 5? Of course, you might think “what’s the problem?, I can just add another integer and it will take cells 26–29”. But the answer will still be No you can’t. To understand why not, we need to go back to our array and memory cells.
The problem with adding additional values to an array is that our array was allocated 128 bits or 16 memory cells and because we can’t manage where the memory object will be saved, we can’t be sure that cells 26–29 are free. Maybe earlier, another array was stored starting from cell 26, or a 1 byte char was stored in that cell. The solution for this problem, is to take the length of the current array (in our case 4) and increase it by 1. An array of length 5 requires 20 bytes. We must ask for 20 bytes for a new array, copy the values from the old array and insert our new value 5 into the last cell. Now our array occupies 20 memory cells or 160 bits, and now the memory may look like this
In the programming world, this kind of array is called a dynamic array, and it involves a concept known as Growth Factor
For example, let’s use a growth factor of 1.5. If we have an array of 4 items (128 bits) and we push a new element to the end, the new array would be 5 items long (192 bits). 4 * 1.5 = 6 6 * 4 * 8 = 192 24 memory cells or 192 bits.
Pop last element from the array
A pop operation removes the last element from an array. Lat’s back to our array int array[4] = {1,2,3,4}; , now we want to pop the last item, in this case 4. For popping elements, you can find many solutions. For example, you can allocate memory for a new array (1 shorter than the original) and copy all elements except the last. But let’s imagine popping from an array with 1000 elements. We would need to allocate memory for a new array and copy 999 elements, a costly task. To simplify this task we can create a buffer zone.
Buffer
A buffer holds two variables: “_length” and “_maxLength”. When you will want to remove an element from the array, you need only reduce _length by 1 _length -= 1. Don’t worry about the remaining memory cells, they will not interfere. This way, when you push a new element into an array, you can do this without wasting resources, because we don’t have to create a new array. The array will be delivered with the buffer, so every time an element is read, make sure the requested index is not bigger than _length. Also do not forget to increase _length by 1 _length += 1 when adding a new element. Only when _length becomes bigger than _maxLength you will run growth logic.
Conclusion
I hope I managed to convey what an array is in the computer memory and how complicated it can be to work with them. You must know that each programming language has its own solution for working with arrays which is not limited to the Push and Pop operations. Good luck!
