Table of Contents
Introduction
In software engineering, the ways that we choose to organize our data is half the battle. When it comes to managing the data, many tools could do the job for us. ”Understanding of WHEN TO USE? WHY USE IT? WHERE TO USE? is the key!”
Regardless of the language, we code in, one of the first things that we encounter are data structures, which are the different ways we can organize our data; arrays, stacks, linked lists, variables, etc., are all different types of data structures. These are just the tip of the iceberg for data structures. In this blog, we will draw the comparison between Linked List vs Arrays.
Linked List
A Linked List is a linear data structure where the elements are stored at non-contiguous memory locations. In simple terms, it can be defined as a collection of objects randomly stored in the memory. These objects are called nodes.
A node contains two fields: a data field and a reference link. The data field contains the data stored at that particular address. And the reference link contains the pointer, which contains the address of the next node in the memory. The last node of the linked list contains a pointer to null.
Attempt some questions related to Linked List on our CodeStudio platform.
Advantages of a Linked List :
- It does not have any fixed size and can change its size at runtime by allocating and deallocating memory.
- Insertion and deletion operations are easier in a linked list.
- No memory wastage as the size of the linked list can increase or decrease in size at run time.
Disadvantages of a Linked List :
- Extra memory space is required to store the pointers along with the data.
- Random access is not possible as it is not index-based.
- In the linked list, reverse traversing is difficult. In the case of a doubly-linked list, it’s easier, but extra memory is required for the back pointer, decreasing memory efficiency.
Arrays
Array stores elements of the same type in contiguous memory locations, making it easier to calculate addresses for the elements stored and allows faster access to an element at a specific index. If we try to create an array with different types of elements, a compile-time error will occur.
Arrays can be used to store collections of primitive data types such as int, double, char, etc., as well as non-primitive data types such as an array of objects.
Are arrays required?
One can always declare any number of variables to store data. But this approach is not suitable when the data required is significantly large. So in such situations, arrays are used, which makes our job faster and efficient.
The array has a fixed length, and only a fixed set of elements can be stored in it.
They are index-based, i.e., the first element of the array is held at the 0th index, the second element of the array is held at the 1st index, etc.
Attempt some questions related to Arrays on our CodeStudio platform.
Advantages of an Array :
- It is easier to access elements by their index.
- Arrays have better cache locality that can make a pretty big difference in performance.
- Extra memory for pointers is not required in the case of arrays.
Disadvantages of an Array :
- The size of arrays is fixed.
- Insertion and deletion operations are difficult in an array as the elements are stored in contiguous memory locations, and the shifting operation is costly.
- Allocating more memory than required leads to wastage of memory space, and less memory allocation also leads to memory shortage.
Linked List vs Arrays
Is an array better than a linked list / Is a linked list better than an array?
The question is which one wins the gold.
Well, It is not possible to decide which one of them is better. The data structure has to be selected depending on the various requirements. There are multiple factors taken into consideration: the type of operations performed on the data structure, the size, etc. Let’s see some differences between the linked list and the array based on some parameters.
- Cost of accessing an element
An array takes a constant time for accessing an element (irrespective of the array size). Using the base address of the element, the address of any element can be found out. To find out the address of the element, some basic calculation is performed, and hence, it takes a time complexity of O(1) to access an element.
In the above example, an element takes up 4 byte space and the address of the element is calculated as follows:
arr[0] = 100 + (0*4) = 100
arr[1] = 100 + (1*4) = 104
arr[2] = 100 + (2*4) = 108
arr[3] = 100 + (3*4) = 112
arr[4] = 100 + (4*4) = 116
arr[5] = 100 + (5*4) = 120
In a linked list, to find any node, we first need to determine the head node (first node) and traverse from the head node to the required node. In the worst-case scenario, we might end up traversing all the nodes. Hence, the average case for accessing the element in a linked list is O(n).
Thus, it is better to use an array if the requirement for accessing the elements.
2. Cost of inserting an element
Inserting the element at the beginning
To insert a new element at the beginning of an array, the elements must shift towards the right to create a space in the first position. So, in this case, the time complexity will be proportional to the size of the array. So the time complexity is O(n) for an array of size n.
In a linked list, to insert an element at the beginning, a new node is created, and the address of the first node is added to the new node. This makes the new node the head node. In this case, the time complexity is O(1).
Inserting the element at the ith position
To insert a new element at the ith position of an array, the elements from the ith index should shift towards the right. So, in this case, the time complexity will be proportional to the size of the array. So the time complexity is O(n) for the average case.
In a linked list, we have to traverse to that position where the new element has to be inserted. This traversal makes the time complexity proportional to the number of elements in the linked list. Hence, the time complexity for the average case is O(n).
Inserting the element at the end
If an array is not full, the new element can be added directly through the index. In this case, the time complexity is O(1).
To insert an element at the end of the linked list, a complete traversal has to be done, and the element is added at the end of the linked list. Due to this traversal, the time complexity is O(n). But this can be reduced to O(1) if we also keep a tail pointer along with a head pointer.
3. Memory Efficiency
For “n” elements, a linked list will use more memory than an array. This is because the linked list uses extra memory to store the reference to the next node. For example, to store five integers, the size requirements are as follows:
- Size required for an array = 5 * 4 bytes = 20 bytes
- In the case of a linked list, each node requires 8 bytes ( 4 bytes to store the integer and 4 bytes to store the reference)
Size required for a linked list = 5 * 8 bytes = 40 bytes
In an array, allocating more memory than required leads to wastage of memory space, and less memory allocation also leads to memory shortage. So, a linked list is a better choice when there is an uncertainty of size as it increases its size when new elements are added.
4. Memory allocation
In arrays, if the size is known at compile-time, memory is allocated at compile time; else, allocation happens at runtime. But once the size is fixed, it cannot be changed. In the case of the linked list, the memory allocation occurs at runtime.
5. Size
The size of an array cannot be altered at runtime. This is because elements in an array are stored in contiguous addresses, and if the size is changed, there is a risk of overwriting other data.
However, in a linked list, as each node points to the next one, data can be stored at non-contiguous addresses; this allows the linked list to change its size at runtime.
6. Ease of use
An array implementation is easier when compared to the linked list. While using a linked list, errors like a segmentation fault, memory leak, etc., can occur.
Frequently Asked Questions
Arrays have better performance and are memory-efficient when the size is known.
The array has a fixed size, and elements can be accessed using the index ([ ]).
No, a linked list allows sequential access and is slower while arrays allow direct and sequential access both.
Insertion and deletion are faster in a linked list because less memory needs to be manipulated.
In a linked list, memory allocation happens at runtime, and in arrays, the memory allocation can happen both at compile-time and runtime.
Key Takeaways
With this discussion, this blog attempted to compare the data structures Linked List vs Arrays, along with the advantages and disadvantages.
Now that you know the data structures well go ahead and attempt some questions based on them on our CodeStudio Platform!
We hope you found this blog useful in understanding Linked List vs Arrays. Feel free to let us know your thoughts in the comments below.
