Last Updated on March 14, 2023 by Neeraj

Introduction:

In this article, we will learn about the advantages and disadvantages of linked list over array. 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.

Linked List

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.

Types of Linked List

Let us now look at the various types of linked list.

1. Singly Linked List

A singly linked list is a linear collection of nodes where each node has some data and a pointer to the next node in the list. In singly linked list, we can traverse the list in only one direction. The main advantage of using singly linked list over other types is that it requires less memory.

2. Doubly Linked List

A doubly linked list is similar to a singly linked list except that each node in list contains two pointer: one points to the previous node and the other points to next node. This allows easy traversal in both forward and backward direction. The first node in list is called head node and the last node is called tail node. The previous pointer of head node points to null or nothing, and the tail node points to null or nothing in the next pointer.

3. Circular Linked List

A circular linked list is a type of linked list where the last node points to the first node, creating a circle. This implies that the list can be traversed infinitely in a loop. Circular linked lists can be implemented using either singly linked nodes or doubly linked nodes. In a singly circular linked list, each node contains a single pointer to the next node in the list. In a doubly circular linked list, each node contains two pointers: one pointing to the previous node and one pointing to the next node.

4. Header Linked List

A header linked list is a type of linked list that uses a special header node to represent the beginning of the list. The header node is actually a dummy node with no actual data but rather acts as a reference point to the first node in the list. The advantage of using a header linked list is that it allows for easier insertion and deletion of nodes, as there is no need to handle the special case of inserting or deleting the first node in the list. Additionally, using a header node makes it easier to handle empty lists, as the header node always exists and can be used to represent an empty list.

Advantages of Linked List over Array

Here are some 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.

3) Implementation:

• 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.

Disadvantages of Linked List over Array

Here are some 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.

Conclusion:

So, in the above tutorial, we have discussed the advantages and disadvantages of linked list over array. Also you are suggested to visit our practice coding questions on Linked List, which are curated by our expert mentors at PrepBytes.

FAQs

Here are some frequently asked questions

1. 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.

2. 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.

3. What is a linked list?
   A linked list is a sequence of data structures, which are connected together using a pointer.