Data Structures Demystified: Arrays
The aim of this story is to personalize the different data structures, written in a fashion that is friendly and interesting to the general audience, but also technical enough as a refresher for people in the field of software engineering. It’s meant to be a quick read for technical interviews.
How does an Array look like? Simple yet deceiving
Every story has a beginning
Legend has it that this data structure is one of the most commonly tested in technical interviews. It allows us to store a collection of data that are similar in nature. It could even be used in a linear fashion, and strings (basically words) are a really good example of such an implementation using arrays, where a series of characters (letters or punctuation) is stored linearly, enabling us to give it meaning. Some might even wonder, how can a computer store characters when it only understands binary numbers? The answer is pretty simple, we can define a mapping between numbers to characters. Some of you might have encountered something called “ASCII”, and this is a common character encoding where we can express characters as 8-bit integers, and that’s how we can also store strings as arrays of 8-bit characters.
Arrays typically come in two forms, a static array is one where you have to indicate how many elements you’re gonna have in your array ahead of time, so it requires planning before using it. On the other hand, the dynamic array is something much fancier that is made as an improvement to the static array, where it automatically resizes as you add more elements on the go.
Technicalities of an Array
By understanding the technicalities of data structures. It allows you to utilize them to solve algorithmic questions with clarity.
Every position in the array is given an index, which is simply a number to represent where you are. Using the index to retrieve an element, allows you to obtain it in constant speed, commonly written as O(1). However, finding an element without knowing its position, requires you to search through the entire array, which takes linear time — O(N). One simple analogy is that if you know the room number where your friends are located at, it is extremely easy to find them, you can go directly to them. But you will have to go through each and every room to find your friends when you have no clue where they are. Knowing the efficiency is crucial in studying data structures because it enables us to determine if an array is the right data structure to be used to solve a particular problem or is there a better way?
It is also costly to insert/delete elements from the array because you have to shift all the other elements to fill in the missing gap. If you have N elements in the array, you would roughly take O(N) time to shift the other elements to rectify the ordered property of this data structure. Some might ask why is the shift necessary whenever we insert or delete an element in the array? The reason is simple, if we do not correct the order of the elements in the array, we violate the principles of this data structure. It is these characteristics of an array that makes it different and unique from other data structures.
Appending elements by default goes to the end of the array, you can achieve this in constant time. However, appending at a specified location is expensive, because you will have to rectify the order of the elements once again.
Arrays are the most common and overlooked data structure, it forms the basis for many other data structures which is why it is important that we first start here and journey off to the other data structures.
Thanks for spending time to read it, I hope you have enjoyed it as much as I have written it. This is the first part of a series that I will write about. Hopefully, you have learned something from this, especially those that are interested in programming but have yet started. If you would like to practice algorithmic questions for technical interviews, LeetCode is a great platform where you can do it for free. With consistent practice, I’m sure you will get through it. The key is to never give up when you encounter a tough question, and learn from it. Good luck!
Read the next story in the series here.