Data Structures Part 3: Arrays
Hello there! More than likely you’ve heard about arrays at some point in time during your coding journey. We’ve talked about them in past articles, and touched on some of their methods; so I suppose it is time to be formally introduced. Arrays are one of the most fundamental data structures in computer science which makes them all that more important to know. They are the building blocks to create more complex data structures like queues and stacks and they give us a great foundation in learning how to manipulate data. So let’s get to it shall we?
What is an Array?
You can think of an array like a list. A list contains several items at once, whether it’s groceries, a wish list, or things to accomplish on an agenda. Arrays do the same; you can store strings, numbers, booleans, even other data structures within an array in a linear order. JavaScript comes with the array data structure pre-built, along with many methods that we will cover soon.
In JavaScript, the easiest way to create an array is to define a variable and set it equal to a pair of square brackets as displayed below:
From here, you can manipulate the array by adding, removing, reversing, splicing, etc. using simple array methods!
Types of Arrays
There are two main types of arrays that we are going to cover. Dynamic and Static arrays.
- ) Static Arrays
Our first type of array is the Static array. They are fixed in size upon initialization, meaning you as the programmer determine how much memory this array will need. The downside of static arrays is that there is no guarantee that any data that goes beyond the threshold will be stored, since the memory was “pre-allocated”. Not only this, but the data may not be stored in the desired order either. You could see how this could become a problem if we don’t know how much memory we’ll need in the future if our data were to grow.
2. ) Dynamic Arrays
One way to solve this problem of memory space and growing data sets, is to create our second type of array: the Dynamic Array. A Dynamic array allows us to copy the original array and rebuild it in another location that contains more memory. For JavaScript users, this process is done automatically and the array resizes on its own…(you may not have even noticed you’ve been using dynamic arrays this whole time).
Widely-Used Array Manipulations and Big O Notation
While there are several array methods that can be used to manipulate an array (link here to explore), we are only going to cover some of the most popular ones as well as their Big O notation.
In order to find one value within an array, we can simply “look it up” by using the index. Remember, when using arrays, our counting begins at zero that is index[0] is the first element in the array. Below, if we want to look up the 3rd element in the array, it will be at index[2] as seen below. This operation has a Big O notation of O(1), since we are performing one operation without any iterations.
Now we would like to add to the end of our array. We will use the method .push(). We first define the array that we want to manipulate and then push the value into the array. This method is also an O(1) operation because we are just adding to the end of the array without looping.
We can also remove the last item of the array by using the method .pop(). If you guessed that this operation is O(1) as well, you were correct, for these last few operations we have only targeted a specific value without having to loop through the entire array.
Instead of adding to the end of the array, now let’s add a name to the beginning, using the method .unshift(). In order to add an element to the beginning of an array, it is necessary to loop through every other item to update the indexes. In our example, ‘Kayla’ will now have the position index[0], which means all of the other indexes are shifted over. This operation is O(n) because we are now having to iterate through the entire array.
We can also insert a value at any index we would like using the .splice() method. The first argument describes what index we would like to insert, the second argument is how many elements we would like to delete, and the third argument is the element we would like to add. Below, we are adding the name ‘Dante’ at index[2], and we are not going to delete any names in the meantime. In order to insert in the middle of the array, this requires us to iterate through only half the array to reassign the indexes to the right of our insert. This is an O(n/2) notation, however; however; it is widely accepted that we remove constants from the Big O notation, therefore this operation would also be considered O(n).
Now that we have covered some of the basic array methods, I hope that this brings some clarification on when you would want to use an array for storing data and when you would not based on time/space complexity. Being aware of the operations going on behind the scenes is a powerful tool, and allows us to think deeply and intentionally about the code we write. Now that we have a good foundation, let’s solve some problems using our knowledge of arrays!
Examples:
A popular interview question is to create a function that reverses a string. There are several ways to solve this challenge, and we will solve it together using two different strategies. Let’s go!
In this first diagram, we are defining a function called “reverse1” and it is taking in a parameter that is a string. We then are initializing an empty array that we will be using in our for-loop. We are setting our starting point of the for loop to the end of our string and the stop point as greater than or equal to 0. Then we will be decrementing with each iteration of the loop to move backwards. For every iteration, we are pushing a letter into the “backwards” array, starting with the exclamation point. Lastly, we are going to return the backwards array and use .join(‘ ‘) to concatenate each letter back into its original string form. And there you have it, we have a backwards string that reads “!reenigne erawtfos a ma I !olleH”.
For this second implementation, we are still passing a string as a parameter, and we are going to pass “myStr” into our function call below our function definition. In function “reverseMe”, we are going to first split the string using the .split(‘ ’) method. This is going to separate each letter into its own index of an array. Then we will use the .reverse() method, which ultimately simulates the looping behavior we used in our first implementation. Lastly, we use .join(‘ ‘) to revert the array back into a string, getting rid of all the indexes and spaces between each letter!
We have officially checked the box on another data structure! Arrays are a simple but very necessary data structure that we use quite often in software development. As we continue on, you will see arrays and several of its methods pop up again and again (yes, the pun was intended). Until next time…
Thanks for reading and see you again soon!
💕👩🏾💻Happy Coding!👩🏾💻💕
REFERENCES:
