Singly Linked List vs Doubly Linked List
Before looking at the differences between the singly linked list and doubly linked list, we first understand what is singly linked list and doubly linked list separately.
What is a singly linked list?
A [singly linked list] can be simply called a [linked list]. A singly linked list is a list that consists of a collection of nodes, and each node has two parts; one part is the data part, and another part is the address. The singly linked can also be called a chain as each node refers to another node through its address part. We can perform various operations on a singly linked list like insertion, deletion, and traversing.
What is a doubly-linked list?
A doubly linked list is another type of the linked list. It is called a doubly linked list because it contains two addresses while a singly linked list contains a single address. It is a list that has total three parts, one is a data part, and others two are the pointers, i.e., previous and next. The previous pointer holds the address of the previous node, and the next pointer holds the address of the next node. Therefore, we can say that list has two references, i.e., forward and backward reference to traverse in either direction.
We can also perform various operations on a doubly-linked list like insertion, deletion, and traversing.
Differences between the singly-linked list and doubly linked list.
The differences between the singly-linked list and doubly linked list are given below:
The singly-linked is a linear data structure that consists of a collection of nodes in which one node consists of two parts, i.e., one is the data part, and another one is the address part. In contrast, a doubly-linked list is also a linear data structure in which the node consists of three parts, i.e., one is the data part, and the other two are the address parts.
As we know that in a singly linked list, a node contains the address of the next node, so the elements can be traversed in only one direction, i.e., forward direction. In contrast, in a doubly-linked list, the node contains two pointers (previous pointer and next pointer) that hold the address of the next node and the address of the previous node, respectively so elements can be traversed in both directions.
- Memory space
The singly linked list occupies less memory space as it contains a single address. We know that the pointer variable stores the address, and the pointer variable occupies 4 bytes; therefore, the memory space occupied by the pointer variable in the singly linked list is also 4 bytes. The doubly linked list holds two addresses in a node, one is of the next node and the other one is of the previous node; therefore, the space occupied by the two pointer variables is 8 bytes.
- Insertion and Deletion
The insertion and deletion in a singly-linked list are less complex than a doubly linked list. If we insert an element in a singly linked list then we need to update the address of only next node. On the other hand, in the doubly linked list, we need to update the address of both the next and the previous node.
Let’s look at the differences in a tabular form.
|Basis of comparison||Singly linked list||Doubly linked list|
|Definition||A single linked list is a list of nodes in which node has two parts, the first part is the data part, and the next part is the pointer pointing to the next node in the sequence of nodes.||A doubly linked list is also a collection of nodes in which node has three fields, the first field is the pointer containing the address of the previous node, the second is the data field, and the third is the pointer containing the address of the next node.|
|Access||The singly linked list can be traversed only in the forward direction.||The doubly linked list can be accessed in both directions.|
|List pointer||It requires only one list pointer variable, i.e., the head pointer pointing to the first node.||It requires two list pointer variables, head and last . The head pointer points to the first node, and the last pointer points to the last node of the list.|
|Memory space||It utilizes less memory space.||It utilizes more memory space.|
|Efficiency||It is less efficient as compared to a doubly-linked list.||It is more efficient.|
|Implementation||It can be implemented on the stack.||It can be implemented on stack, heap and binary tree.|
|Complexity||In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n) .||In a doubly-linked list, the time complexity for inserting and deleting an element is O(1) .|