Types Of Linked List
Now, let's look at the types of linked list.
1. Singly Linked List
A singly linked list is a Data Structure that consists of a series of nodes, where each node stores a value (or data) and a reference (or pointer) to the immediate next node of the series. The first node of the series is called the head, and the last node of the series points to a null reference.
Here is an example of a singly linked list with four nodes, where each node contains an integer value:
head -> [5] -> [3] -> [7] -> [2] -> null
In this example, the head node contains the value 5, and it points to the next node in the sequence, which contains the value 3. The third node contains the value 7, and it points to the last node in the sequence, which contains the value 2 and points to a null reference.
2. Doubly or Two Way Linked List
A Doubly Linked List, also known as a two-way linked list, is a data structure that is the same as a singly linked list, except that each node in the sequence contains a reference to both the next and the previous nodes in the sequence. This allows for efficient traversal of the list in both directions, from the head to the tail and from the tail to the head.
Here is an example of a doubly linked list with four nodes, where each node contains an integer value:
head <-> [5] <-> [3] <-> [7] <-> [2] <-> null
In this example, the head node contains the value 5 and points to the next node in the sequence, which contains the value 3 and also points back to the previous node. Similarly, the third node contains the value 7 and points to the next node in the sequence, which contains the value 2 and also points back to the previous node.
3. Circular Linked List
A circular linked list is a slight variation of the singly linked list, in which the last node in the sequence points back to the first node, forming a loop or circle. In other words, the next pointer of the last node of the series points to the head of the list.
Here is an example of a circular linked list with four nodes, where each node contains an integer value:
head -> [5] -> [3] -> [7] -> [2] -|
^ |
|---------------------------------|
In this example, the head node contains the value 5, and it points to the next node in the sequence, which contains the value 3. The third node contains the value 7, and it points to the last node in the sequence, which contains the value 2 and points back to the head node.
4. Circular Doubly Linked List
A circular doubly linked list is a data structure that consists of a series of nodes, where each node stores a value, a reference to the immediate next node in the sequence, and a reference to the previous node of the series. The last node of the series points to the first node, creating a circular sequence.
Here is an example of a circular doubly linked list with four nodes, where each node contains an integer value:
head -> [5] <-> [3] <-> [7] <-> [2] <-> head
In this example, the head node contains the value 5, and it points to the next node in the sequence, which contains the value 3 and points back to the head node. The third node contains the value 7, and it points to the next node in the sequence, which contains the value 2 and points back to the head node.
5. Header Linked List
A header-linked list is a variation of a singly linked list with a header node at the beginning of the list. The header node does not store any data and serves as a sentinel or marker for the beginning of the list. The header node always exists, even if the list is empty.
Here is an example of a header-linked list with four nodes:
header -> [5] -> [3] -> [7] -> [2] -> null
In this example, the header node does not contain any data and serves only as a marker for the beginning of the list. The first node in the sequence contains the value 5, and it points to the next node in the sequence, which contains the value 3. The third node contains the value 7, points to the last node in the sequence, which contains the value 2 and points to a null reference.
Must Read Algorithm Types
Advantages Of Linked List
Dynamic Data Structure
In LinkedList, memory is dynamically allocated to the LinkedList. One can easily add or remove an element to the LinkedList at the runtime. Hence, there is no need for initial size.
Implementation
LinkedList is a very useful Data Structure that helps implement other Data Structures like Stacks and Queues.
No Memory Wastage
As discussed in the first point, memory is dynamically allocated to the LinkedList. That is why we can remove the memory which is not in use, and no memory is wasted.
Insertion and Deletion
In LinkedList, insertion and deletion operations are efficient compared to other Data Structures such as Arrays as no shifting of elements is required in the LinkedList. Only the pointers need to be updated.
Versatility
Linked lists can be used to implement a wide range of data structures, including stacks, queues, associative arrays, and graphs, as well as linked data structures such as trees and hash tables.
Persistence
Linked lists can be used to implement persistent data structures, which are data structures that can be modified and accessed across multiple program executions. This is because linked lists can be easily serialized and stored in non-volatile memory.
Disadvantages Of Linked List
Memory Usage
The memory used by LinkedList is more because we also need to store the address of the next data.
Accessing an element
We can not access any element of the LinkedList directly. We don’t have direct access to every element of LinkedList. If we want to access the ith element of the LinkedList, then we need to traverse the LinkedList till the ith index.
Reverse Traversal
The reverse traversal is not possible in the Singly LinkedList because we don’t have the memory address of the previous pointers. It is possible in the Doubly LinkedList, but again it consumes more memory as we need to store the memory address of the previous pointers.
More complex implementation
Linked lists can be more complex to implement than other data structures, such as arrays or stacks. They require knowledge of dynamic memory allocation and pointer manipulation, which can be difficult for novice programmers.
Lack of cache locality
Linked lists may not take advantage of the caching mechanisms in modern processors, since accessing elements in a linked list requires jumping to different locations in memory. This can result in slower performance compared to other data structures that have better cache locality, such as arrays.
Common Use Cases for Linked Lists
The common use cases of linked lists are as follows
Stacks and Queues Implementation
Stacks and queues are two essential data structures that are utilized in a wide range of applications. Due to their ease of adding and removing components from the list's beginning or end, linked lists are a logical choice for building stacks and queues.
Dynamic Memory Allocation
The technique of allocating and freeing memory while a program executes is known as dynamic memory allocation. Using each node in the linked list to represent a vacant block of memory, linked lists can be utilized to accomplish dynamic memory allocation.
Graph Implementation
A graph is a type of data structure used to show the connections between objects. In a graph, every node denotes an object, and every edge denotes a connection between two objects. By using each node in the linked list to represent a vertex in the graph, linked lists can be utilized to implement graphs.
Representing Sparse Matrices
Sparse matrices are those with a high proportion of zeros. By using each node in the linked list to represent a non-zero element in the sparse matrix, linked lists can be utilized to represent sparse matrices. As a result, sparse matrices can be stored and handled effectively.
Also read - Merge sort in linked list
Frequently Asked Questions
What are the applications of linked lists?
Linked lists have various applications, such as implementing dynamic data structures like stacks, queues, and hash tables. They are also used in memory allocation, graph traversal algorithms, and file systems. Linked lists are particularly useful when memory is limited or when inserting or deleting elements frequently.
Can we access the random element of the LinkedList?
We can not access any element of the LinkedList directly. We don’t have direct access to every element of LinkedList. If we want to access the ith element of the LinkedList, then we need to traverse the LinkedList till the ith index.
How is memory not wasted in LinkedList?
Since the memory is dynamically allocated to the LinkedList, we can remove the memory that is not in use, and no memory is wasted.
Which linked list is better and why?
A single linked list is an excellent option if you require a linked list that is effective for insertion and deletion at the start or end of the list. A doubly linked list is a suitable option if you require a linked list that is effective for searching and traversing the list in reverse order.
Conclusion
In this blog, we have covered the following things:
- We first discussed what LinkedList is.
- Then we discussed the advantages and disadvantages of LinkedList.
If you want to learn more about Linked List and want to practice some questions which require you to take your basic knowledge on Linked List a notch higher, then you can visit our Guided Path for Linked List
Until then, All the best for your future endeavors, and Keep Coding.