Difference between Singly and Doubly Linked List

Introduction

Singly and doubly linked list are used where dynamic memory allocation is necessary.
There are some similarities between them. Singly and doubly linked list are linear data structure. Both Singly and Doubly Linked list uses pointers for its implementation.

With these similarities, there are some key differences between Singly linked list and doubly linked list . 
In this article we are going to understand the difference between them .



Difference between Singly and Doubly Linked List

 
Singly Linked List(SLL) Doubly Linked List(DLL)
As name implies, singly linked list contain the nodes with data part and  a pointer to the next  node. Doubly linked list contain the nodes with data part and two pointers , one pointer to next node and another to point previous node.
In singly linked list traversal is possible in only one direction, only forward direction. In doubly linked list traversal is possible in both forward and backward direction.

Singly linked list require less memory for implementation than doubly linked list.
Doubly linked list require more memory for implementation than SLL.

Time complexity for insertion and deletion of node at known position is O(n)
Time complexity for insertion and deletion of node at known position is O(1)

Searching in singly linked list  is less efficient than doubly linked list .
Searching in doubly linked list  is more efficient than singly linked list .

SLL is used in situation where memory consumption should be be less and searching is less frequent.
DLL is used in situation where memory is not limitation and searching is more frequent .

Singly liked list is generally used to implement stack
Doubly linked list is used to implement heaps , binary tree.



 Just a second !

Hey , Did you find this article useful ? If yes , share with your colleague and give him/her opportunity to learn and grow . Knowledge is free on Internet !