Both Singly linked list and Doubly linked list are the implementation of Linked list in which every element of singly-linked list contains some data and a link to the next element, which allows to keep the structure. On the other hand, every node in a doubly-linked list also contains a link to the previous node.
The following are the important differences between a Singly linked list and Doubly linked list.
| Key | Singly linked list | Doubly linked list |
|---|---|---|
| Complexity | In singly linked list the complexity of insertion and deletion at a known position is O(n) | In case od doubly linked list the complexity of insertion and deletion at a known position is O(1) |
| Internal implementation | In singly linked list implementation is such as where the node contains some data and a pointer to the next node in the list | While doubly linked list has some more complex implementation where the node contains some data and a pointer to the next as well as the previous node in the list |
| Order of elements | Singly linked list allows traversal elements only in one way. | Doubly linked list allows element two way traversal. |
| Usage | Singly linked list are generally used for implementation of stacks | On other hand doubly linked list can be used to implement stacks as well as heaps and binary trees. |
| Index performance | Singly linked list is preferred when we need to save memory and searching is not required as pointer of single index is stored. | If we need better performance while searching and memory is not a limitation in this case doubly linked list is more preferred. |
| Memory consumption | As singly linked list store pointer of only one node so consumes lesser memory. | On other hand Doubly linked list uses more memory per node(two pointers). |