Difference between a Singly Linked List and a Doubly Linked List

Introduction

The linked list is one of the most important data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Singly Linked List Introduction

A singly linked list is the kind of linked list, in which a node has two fields:

  • data
  • next

The data field stores the data or the information, and the next field stores the address of the next node.

Doubly Linked List Introduction

A doubly linked list is the kind of linked list, in which a node has three fields:

  • data
  • next
  • previous

The data field stores the data or the information and the next field stores the address of the next node and the previous field stores the address of the previous node.

Difference between Singly linked list and Doubly linked list

Singly Linked List Doubly Linked List
A Singly Linked has nodes with a data field and a next link field. A Doubly Linked List has a previous link field along with a data field and a next link field.
In a Singly Linked List, the traversal can only be done using the link of the next node. In a Doubly Linked List, the traversal can be done using the next node link as well as the previous node link.
A Singly Linked List occupies less memory than the Doubly Linked List, as it has only 2 fields. A Doubly Linked List occupies more memory than the Singly Linked List, as it has 3 fields.
Accessing elements in a Singly Linked List is less efficient when compared to a Doubly Linked List, as only forward traversal is possible. Accessing elements in a Doubly Linked List is more efficient when compared to a Singly Linked List as both forward and backward traversal is possible.
The time complexity of inserting or deleting a node at a given position (if the pointer to that position is given) in a singly linked list is O(n). The time complexity of inserting or deleting a node at a given position (if the pointer to that position is given) in a doubly linked list is O(1).
Singly linked list is preferred when we have memory limitation(we can’t use much memory) and searching is not required. Doubly linked list is preferred when we don’t have memory limitation and searching is required(we need to perform search operation on the linked list).

So, in this article, we have tried to explain the differences between a Singly Linked List and a Doubly Linked List. These basic concepts should be clear if we want to do good in a coding interview. If you want to solve more questions on singly and doubly linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post LinkedList listiterator() method in Java
Next post Find the smallest and largest elements in a singly linked list

Leave a Reply

Your email address will not be published. Required fields are marked *