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.

Space Jump Back to the Top