Single Linked List vs Doubly Linked List
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.
|Singly linked list
|Doubly linked list
|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)
|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.
|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.
|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.
|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).