Difference between a singly linked list and a doubly linked list

Introduction

Linked list is an important topic to understand while preparing for technical interviews, and it may be used to answer a variety of problems. To solve and answer complex questions, it is necessary to have a profound understanding of the fundamental principles.

This blog will discuss a fundamental but significant topic, i.e., the differences between a singly linked list and a doubly linked list.  

Singly Linked List

A unidirectional linked list containing a set of ‘N’ nodes that can be traversed from the first node to the last node is called a singly linked list. Its node consists of two parts, data and a pointer containing the address of the next node.

For example, 

Doubly Linked List

A linked list containing a set of ‘N’ nodes that can be traversed in both directions, i.e., forward and backward, is termed as a doubly-linked list. Each node of a doubly-linked list consists of three parts, data, and two pointers, one containing the address of the next node and the other having the address of the previous node.

For example, 

Differences

Let us look at a few key differences between a singly linked list and a doubly linked list.

Key

Singly Linked List

Doubly Linked List

Components

Its node consists of two parts, one for storing the data and the other containing the pointer that holds the address of the next node.Its node consists of three parts, one for storing the data and the other two containing pointers that hold the address of the previous and the following nodes.

Traversal

It can be traversed only in one direction, i.e., the forward direction.It can be traversed in both directions, i.e., forward as well as backward.

Memory 

It utilizes less memory as it uses only one pointer to store the address of the next node.It utilizes more memory as it uses two pointers to store the addresses of the next and the previous nodes.

Performance

It lacks in terms of performance but utilizes less memory.It provides better performance but uses more memory which can be considered to be a limitation. 

Complexity

The time complexity to insert or delete an element at a particular position (pointer to that position is given to us) is given by O(N), whereis the total number of nodes in the linked list.The time complexity to insert or delete an element in a doubly-linked list, at a position whose pointer is given, is constant, i.e., O(1).

Applications

A singly linked list is used to implement stacks and queues. Any FIFO structure can be implemented using a singly linked list, and message delivery on a network is also based on this concept. It is used to implement data structures like heaps and binary trees. It is also used to implement backward and forward navigation of visited web pages, and to implement undo and redo in many applications. 

 

Key Takeaways

So, this blog discussed the difference between a singly linked list and a doubly linked list. To learn more topics like Linked ListGraphsTrees, head over right now to CodeStudio and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

Do you know how to implement a Linked List? Let's watch the below video to understand it beforehand.

In case of any comments or suggestions, feel free to post them in the comments section.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think