Singly Linked List vs Doubly Linked List

Linked List – Linked List consists of nodes attached to each other where every node holds the address of the other node.

We can create two types of linear linked List 

  1. Singly Linked List
  2. Doubly Linked List

What is a Singly Linked List?

A Singly Linked List consists of Nodes attached to each other where each node has two members – ‘data’ and ‘next’ .’data’ is the data of the nodes and ‘next’ stores the address of the next node.

Here is the diagrammatic representation of singly Linked List

Advantages of Singly Linked List

  • Less memory is required for storing the members (2 members – data and next)
  • During execution, we can deallocate or allocate memory very easily.
  • Insertion and Deletion don’t require the shifting of all elements as required in the array.

Disadvantages of Singly Linked List

  • Insertion and Deletion of element require O(N) time.
  • Accessing the previous node is not possible since we do not have prev pointer.

What is a Doubly Linked List?

Doubly Linked List consists of Nodes attached to each other where each node has three members – ‘data’, ‘prev’ and  ‘next’ .’data’ is the data of the nodes,’ prev’ stores the address of the previous node, and ‘next’ stores the address of the next node.

Here is the diagrammatic representation of Doubly Linked List

Advantages of Doubly Linked List

  • Traversal can be done in both directions (either forward or backward since we are now available with two pointers – next and prev)
  • Accessing the previous node easy since we have prev pointer.
  • Insertion and Deletion of element require O(1) time.
  • Insertion and Deletion don’t require the shifting of all elements as required in the array.
  • During execution, we can deallocate or allocate memory very easily.

Disadvantages of Doubly Linked List

  • More memory is required for storing the members (3 members – data , prev and next)
  • Random Access is not available since elements are stored randomly where every node points to other nodes which is present randomly.

Now let us analyze the difference between Singly Linked List and Doubly Linked List.

S.No.ParametersSingly Linked List (SLL)Doubly Linked List (DLL)
1.MembersIt has two members – data and next (‘data’ for holding the data of the current node and ‘next’ for holding the address of the next node)It has three members – data, prev, and next (‘data’ for holding the data of the current node, ‘prev’ for storing the address of the previous node, and ‘next’ for storing the address of the next node)
2.DirectionalIt is unidirectional since traversing can be done using the next pointer only.It is bidirectional since traversing can be done using the next and prev pointer.
3.Insertion and Deletion operationInsertion and deletion can be done in O(n)Insertion and deletion can be done in O(1)
4.MemoryIt requires less memory since we need 2 members.It requires more memory since we need 3 members.

Some Important Questions on LinkedList:

Reverse a LinkedList
Find the middle of LinkedList
Merge two sorted Linked List (use method used in mergeSort)
Remove N-th node from back of LinkedList
Add two numbers as LinkedList
Delete a given Node when a node is given.(0(1) solution)

Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article