If you are familiar with programming languages like Ruby or JavaScript, then you probably have experience working with Arrays. Arrays are very versatile data structures. In Ruby, there are a variety of built in methods that can be performed on an array. For example, push, pop, shift and unshift are all methods that involve adding or removing from an array. Even though arrays seem like the best option for storing a collection of similar data types, there are still some drawbacks that could be solved by using a data structure called a Linked List.
When preparing for technical interviews as a developer, it is important to be familiar with different data structures like arrays and linked lists and the pros and cons of working with each. Something to take into consideration is the memory allocated for each and also the time complexity of each. One way of looking at speed is through the Big O Notation.
Big O Notation
What is the Big O Notation? Big O is the way we describe the performance efficiency or complexity of algorithms.
The graph above represents the Big O complexity chart. In order to understand the differences and similarities between Arrays and Linked List, we must first understand Big O and some of the different time complexity possibilities. Below are three different possibilities for the speed of an algorithm.
- O(1): Executes in the same time regardless of the size of the input
- O(n): Executes linearly and proportionally to the size of the input
- O(n²): Performance is directly proportional to the square of the size of the input (ex: nested iterations, loops)
Now that we are familiar with the Big O, we can now dive into the similarities of Linked Lists in terms of time complexity and memory allocation.
Arrays
What is an Array? An array is a collection of elements that are ideally of the same data type. When an array is created, the size of the array is specified at the time of declaration meaning it is a fixed size. Arrays are also stored as one large contiguous block of memory starting at an index of zero. This means that the elements get stored in consecutive slots of memory. For example, when accessing an array at an index of 2, we are retrieving the third element.
Since the size of an array is specified at the time of declaration, part of the array contains the data, and the other portion of the array is empty so that it can store new elements if we wanted to add to it. If an array becomes too large, a new array must be created that copies over the original data and then doubles in size to create more empty space for future data to be stored. With an array, there is often memory allocated to the actual data stored and memory allocated to empty slots that may be filled in the future.
The image above represents an array. When using an array it common to access an element at a certain point, remove an elements or add an element. However, these different actions have costs in terms of time. For an array, accessing elements at a specified index has a constant time of Big O(1).
Inserting or removing from an array can come in three different forms: inserting/removing from the being, inserting/removing from the end, or inserting/removing from the middle. In order to add an element to the beginning of an array, we must shift every other element after it to a higher index. For example, If we wanted to add 2 to the beginning of the above so that it would now be at the zeroth index, 10 would now be at the first, 9 would be at the second and so on. Time taken will be proportional to the size of the list or Big O(n), n being the size of the list.
Adding to the end of the array is a lot simpler in terms of speed. It involves adding the element to the next highest index of the array. This means that it is constant time and Big O(1) if the array is not already full. However, if the array is full it would involve having to create a new array and then copy the contents of the original into the new array which would be O(n). The third case of insertion would be adding to a position between the beginning and end of the array which would be Big O(n). The same time complexity is also true for removing from an array.
Linked Lists
What is a linked list? A linked list consists of nodes where each node contains data and and a reference to the next node in the list. Unlike an array, data is not stored in one contiguous block of memory and does not have a fixed size. Instead, it consists of multiple blocks of memory at different addresses. This means that the size is variable because elements are allocated memory at runtime. We can create and free nodes when we want or need without having to worry about memory. In order to access any node or element of the list, we need the address of the head node and need to then traverse the entire list in order to get to the desired element. Unlike an array, there is no reserved or unused memory. However, extra memory is used to store addresses for the next node. The last node’s address pointer will be undefined or 0 since it is the last node of the chain and will not have anything that comes after it.
When accessing elements of a linked list, speed is proportional to size of the list with Big O(n). Since we must traverse the entire list in order to get to the desired element, it is more costly compared to accessing elements of an array.
When inserting a node into the beginning of the list, it only involves creating a new node with an address that points to the old head. The time it takes to perform this is not dependent on the size of the list. This means that it will be constant time or a Big O(1). Inserting an element to the end of the list involves traversing the whole list and then creating a new node and adjusting the previous node’s address for the next node. Time taken will be proportional to the size of the list and Big O(n). When we are inserting node into a position between the beginning and end of the linked list, we will have to traverse the list up until the specific point and then adjust the pointers with Big O(n). The same time complexity is also true for removing nodes from a linked list.
Comparing Arrays and Linked Lists
The graph shown above represents the different time complexities of performing different actions on arrays and linked lists. It is not necessarily better to use one data structure over the other. However, you must take into consideration what actions you will be performing on them.
