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:
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:
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.
Singly linked list vs 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).|
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.
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.
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.
What are the different types of linked lists?
Different types of linked lists are:
- Singly-linked list
- Doubly linked list
- Circular linked list