In this article, we will learn about the advantages and disadvantages of linked list. Every data structure has its own strengths and weaknesses therefore, we need to know the pros and cons of each data structure.
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
A Linked List is a linear data structure. Unlike arrays, the elements are not stored in contiguous locations. The Linked List elements are linked using pointers. Each node consists of 2 parts:
- Data: The Data which is stored at a particular address.
- Reference: Contains the address of the next node of the linked list.
Advantages of a Linked List over Array
1) Dynamic Data Structure:
- Linked List being a dynamic data structure can shrink and grow at the runtime by deallocating or allocating memory, so there is no need for an initial size in linked list.
- Whereas an initial size has to be declared in an array, and the number of elements cannot exceed that size.
2) No Memory Wastage:
- As the size of a linked list can grow or shrink at runtime, so there is no memory wastage. Only the required memory is allocated.
- In arrays, we have to first initialize it with a size which we may or may not fully use; hence wastage of memory may occur.
- Some very helpful data structures like queues and stacks can be easily implemented using a Linked List.
4) Insertion and Deletion Operation:
- In a Linked List, insertion and deletion operations are quite easy, as there is no need to shift every element after insertion or deletion. Only the address present in the pointers needs to be updated.
- While in an array, we have to shift elements. Suppose we have an array that is sorted, and now we need to insert some element in the array in a sorted way. Let arr= [ 1, 3 , 5, 7, ….. ], and we have to insert 2. So, all the elements after 1 have to move by one place towards the right.
Let us also have a look at the disadvantages of Linked Lists.
Disadvantages of a Linked List over Array
1) Memory Usage: The memory required by a linked list is more than the memory required by an array, as there is also a pointer field along with the data field in the linked list. The pointer field too requires memory to store the address of the next node.
2) Random Access: To access node an at index x in a linked list, we have to traverse through all the nodes before it. But in the case of an array, we can directly access an element at index x, using arr[x].
3) Reverse Traversal: In a singly linked list, reverse traversal is not possible, as every node stores only the address of the next node. In case of a doubly-linked list, reverse traversal is possible, but it consumes more memory, as we have to allocate extra memory to store the previous pointer While in arrays, we can do a simple reverse traversal with the help of a for loop.
So, in the above tutorial, we have discussed the advantages and disadvantages of linked list over arrays. Also you are suggested to visit our practice coding questions on Linked List, which are curated by our expert mentors at PrepBytes.
Can we access the random element of the linked list?
In the linked list, we can not access any node directly, if we want to access any node then we have the traverse the linked list.
How is memory not wasted in a linked list?
In the linked list memory is allocated dynamically, so we can remove the memory which is not in use.
What is a linked list?
A linked list is a sequence of data structures, which are connected together using a pointer.