In the tutorial we will learn the difference between singly and doubly linked list. Basically a singly linked list has one field of data and one field of the link which points to the next node whereas in doubly linked list each node stores the link to previous pointer as well to the next pointer.
Singly Linked List
A singly linked list is the kind of linked list, in which a node has two fields:
- data
- next
The data field stores the data or the information, and the next field stores the address of the next node.
Doubly Linked List
A doubly linked list is the kind of linked list, in which a node has three fields:
- data
- next
- previous
The data field stores the data or the information and the next field stores the address of the next node and the previous field stores the address of the previous node.
Although for now you might not found any difference between singly and doubly linked list but there are some difference between singly linked list and doubly linked list.
Difference Between Singly linked list and Doubly linked list
In this blog section, we will discuss the difference between singly linked list and doubly linked list.
| Singly Linked List | Doubly Linked List |
|---|---|
| A Singly Linked has nodes with a data field and a next link field. | A Doubly Linked List has a previous link field along with a data field and a next link field. |
| In a Singly Linked List, the traversal can only be done using the link of the next node. | In a Doubly Linked List, the traversal can be done using the next node link as well as the previous node link. |
| A Singly Linked List occupies less memory than the Doubly Linked List, as it has only 2 fields. | A Doubly Linked List occupies more memory than the Singly Linked List, as it has 3 fields. |
| Accessing elements in a Singly Linked List is less efficient when compared to a Doubly Linked List, as only forward traversal is possible. | Accessing elements in a Doubly Linked List is more efficient when compared to a Singly Linked List as both forward and backward traversal is possible. |
| The time complexity of inserting or deleting a node at a given position (if the pointer to that position is given) in a singly linked list is O(n). | The time complexity of inserting or deleting a node at a given position (if the pointer to that position is given) in a doubly linked list is O(1). |
| Singly linked list is preferred when we have memory limitation(we can’t use much memory) and searching is not required. | Doubly linked list is preferred when we don’t have memory limitation and searching is required(we need to perform search operation on the linked list). |
Conclusion:
So in this article we have discussed the difference between singly and doubly linked list and it will also help you to get more understanding of choosing linked lists according to the specific requirements.
FAQs
1. What is a linked list?
The linked list is a set of nodes in which each node has a pointer to the next node and is stored at non-contiguous memory locations.
2. Can a doubly linked list be a circular linked list?
Yes, a doubly linked list can be a circular linked list if the last node of the doubly linked list is connected to the first node of the linked list.
3. What are the different types of linked lists?
Different types of linked lists are:
- Singly-linked list
- Doubly linked list
- Circular linked list
4. Is there any difference between singly linked list and doubly linked list based on memory?
Yes, there is a difference between singly linked list and doubly linked list one the basis of memory as we prefer to use singly linked list in cases of less memory and whereas there is no such memory boundation in doubly linked list.
5. Explain the difference between singly and doubly linked list on the direction of traversal.
The difference between singly and doubly linked list on the basis of traversal is that in singly linked list we can only traverse in forward direction whereas in doubly linked list we can traverse in both forward and backward direction.