Difference between a Singly Linked List and a Doubly Linked List

In the tutorial we will learn the difference between singly and doubly linked list.Basically a singly linked list has one field of data and one field of the link which points to the next node whereas in doubly linked list each node stores the link to previous pointer as well to the next pointer.

Singly Linked List

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

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.

linked list

Singly linked list vs 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).

Conclusion:

So in this article we have discussed the difference between singly and doubly linked list and it will also help you to get more understanding of choosing linked lists according to the specific requirements.

Related Articles
Doubly circular linked list in data structure Application of doubly linked list
Applications of linked list Student management system using linked list
Advantages and disadvantages of linked list Doubly linked list all operations in C
Binary search in linked list Bubble sort linked list
Deletion in doubly linked list Delete the middle node of a linked list
Polynomial addition using linked list Find max value and min value in linked list
Insert a node at a specific position in a linked list Swap nodes in linked list
Add two numbers represented by linked lists Find starting point of loop in linked list
Merge sort linked list Delete a node from linked list at a given position
Remove duplicates from unsorted linked list Reverse a linked list in Python

FAQs

  1. What is a linked list?
    The linked list is a set of nodes in which each node has a pointer to the next node and is stored at non-contiguous memory locations.

  2. Can a doubly linked list be a circular linked list?
    Yes, a doubly linked list can be a circular linked list if the last node of the doubly linked list is connected to the first node of the linked list.

  3. What are the different types of linked lists?
    Different types of linked lists are:

    • Singly-linked list
    • Doubly linked list
    • Circular linked list

Leave a Reply

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