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 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 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 this article, we have tried our best to explain the advantages and disadvantages of linked list over arrays. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.