Arrays are one of the most fundamental data structures in programming. They’re simple to use, yet powerful in storing multiple elements efficiently. But have you ever wondered what happens behind the scenes when you use an array? Why do different programming languages have various ways of declaring arrays? What are static and dynamic arrays, and how do they differ? How does an array store data in memory (RAM)? Let’s dive in and explore!
What is an Array?
An array is a container for storing data. Think of it like a series of boxes, each capable of holding one piece of data. When you store data in an array, it’s saved in the computer’s RAM (Random Access Memory), just like any other variable. Throughout this post, when I refer to "memory," I’m specifically talking about RAM.
Arrays store data as bytes. For example, if we add the values 4, 6, 3, 5, and 9 into an array, each of these numbers (depending on the type of data, like integers) might take up a certain number of bytes. In this case, assume each number takes 1 byte (or 8 bits). So, we’re storing five bytes of data in the array, and this is how they’d be arranged in memory:
You access the data in an array by its index. In most programming languages, array indices start at 0, meaning the first element is at position 0. In a fixed-size array, you can easily access, modify, or delete elements at any index.
Memory Allocation in Arrays
When we create a fixed-size array, we inform the system of the amount of memory we need. The system then allocates that memory and returns a reference (or address) to it. This is where we can start performing operations on the array.
Here are a few common operations and their Big O time complexities:
Access O(1)
Modify 0(1)
Remove 0(n): Let’s break down the Remove operation: When you remove an element, say from the middle of an array, the remaining elements must shift to fill the gap. For example, if the array is
[1, 2, 3, 4, 5]and you remove3, it becomes[1, 2, _, 4, 5]. After removing3, the remaining elements are shifted to fill the space:[1, 2, 4, 5, _]. Removing takes constant time, but shifting elements takes O(n) time, where n is the number of elements in the array.Create 0(n)
When you create an array, the process involves allocating space in memory. In a fixed-size array, the memory is reserved ahead of time, making operations constant. However, dynamic arrays are a bit more complex.
Static vs. Dynamic Arrays
There are two main types of arrays:
Static Array: The size is fixed when you create the array.
Dynamic Array: The size can grow as needed. It’s not fixed.
Now that we’ve covered static arrays, let’s move on to dynamic arrays.
Understanding Dynamic Arrays
As mentioned, a dynamic array doesn’t require you to specify a size up front. Languages like Python and JavaScript use dynamic arrays by default. However, no array can be truly unlimited in size. Let’s say a dynamic array starts with a size of 3. When you fill all three positions, the array creates a new, larger array behind the scenes. This new array is typically double the size of the original one. For example, if the original array has a size of 3, the new one will have a size of 6.
Here’s what happens under the hood:
A new array with double the size (6) is created.
The values from the old array are copied into the new array.
The old array is deallocated (freed from memory).
This process of reallocating memory and copying elements takes O(n) time.
Time Complexity of Dynamic Array Operations
Dynamic arrays have similar time complexities to static arrays:
Access: O(1)
Modify: O(1)
Remove: O(n)
Create: O(n)
That’s the essence of arrays! I hope this explanation was short and simple enough. If you have any suggestions or if something isn’t clear, feel free to let me know!
