Data Structures - Arrays

Greetings to the Hashnode Community 🙌

So, as review for my own interviews, I've been hard at work at attempting to grasp the inner workings of the relevant data structures expected of a Software Engineer.

Evidently from the title, in this post I'll be piecing down my understanding of how arrays work, more so in the context of statically typed languages, specifically C++.

Firstly, a definition of the array data structure in addition to a "Why arrays?" should suffice before we delve deeper into its implementation.

An Introduction to Arrays

It's important to realize that data structures are primarily meant to be efficient solutions to the retrieval and storage of data. So, how exactly does an array help us, or rather, pose a solution to retrieval and storage?

Suppose you had to calculate the average exam scores of a class of 30 students. Without arrays, this would involve instantiating 30 variables, one for each student, and keeping track of each, which more or less involves watching your code like a hawk. If somehow you were to find a way around this, imagine if I were to scale this to 300 students.

int student1 = 45;
int student2 = 87;
int student3 = 79;
int student4 = 80;
... // 
int student30 = 65;

int avg = (student1 + student2 + student3 + student4+...+student30)/30;

And here lies the problem, namely retrieval or data, and storage of data. It's inefficient and tedious to create n number of variables, and keep track of each when we need them.

Generally when we're writing software in the real world, or any non-trivial program for that matter, chances are you're most definitely going to be dealing with collections of data of the same type. It'd be great if there was some solution to this problem.....

Enter arrays.

Arrays are data structures allowing us to store data of the same type in contiguous blocks of memory. And this contiguousness is what primarily provides us with solutions to the storage and retrieval of data.

int arr[] = {24, 6, 34, 61, 302, 100, 1, 5};

std::cout << arr[3] << std::endl;    // Prints 61
std::cout << arr[5] << std::endl;    // Prints 100

Given the index of an array, we can directly access any element of the array, from the 1st element down to the last, regardless of the size of the array, and "directly" here alludes to a constant time O(1) operation for those of you familiar with the Big O notation.

As to why passing in an unsigned integer value in the [] operator provides us direct access to an element is due to pointer arithmetic. In short, we add the number we pass in through the [] operator to the pointer to the first element of the array.

Now, let's take it up a notch.

Dynamic Arrays 👀

In static arrays, you probably noticed how the size of the array is inherently fixed and non-resizable, as in we need to know beforehand how much data we're dealing with.

Depending on what we're working with, we might need a bit more flexibility as not all domains of software development allow us to know exactly how much data we're working with.

For this purpose, dynamic arrays come to the rescue. Dynamic here refers to the fact that the size of the array can be variable, depending on what we're working with, and this can all happen whilst the program is running, i.e in runtime.

std::vector<int>v1; 
v1.push_back(5); // Inserting 5 
v1.push_back(3); // Inserting 3

For those unfamiliar with C++, vectors are part of the C++ standard library, essentially a wrapper over dynamic arrays, so for the purposes of this article you can pretty much use the terms interchangeably.

Our vector/dynamic array here starts with a memory limit of 0.

When we push the first element, the integer 5 in it, it has to allocate itself 1 block of memory, and assign that place in memory as 5.

Now when we push the second element, the vector/dynamic array will first allocate itself 2 blocks of memory (doubling of allocated memory), copy elements from its previous location and place them in the new position, and then of course place the 3 next to the 5 in this new memory block.

This is what is meant by the dynamic in dynamic arrays. Memory is allocated and deallocated at runtime.

With the exception of dynamically allocating memory, the basic concepts are pretty much the same as arrays when it comes to storage and retrieval with just a few more intricacies that I'll probably tackle in another blog post.

It's important to mention that using either static or dynamic arrays is entirely dependent on the kind of problem you have to solve, one is not simply better than the other, or rather a be-all or end-all solution. Otherwise, you might just be feeding into the Golden Hammer AntiPattern

Thanks for reading this post! Tell me if you liked it, didn't like it, and please feel free to correct me if anything here sounds like waffle ✌