Difference between singly linked list doubly linked list and circular linked list

Difference between Singly linked list and Doubly linked list

Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piece of information and ‘link’ field is used to point to next node. Basically the ‘link’ field stores the address of the next node.

Table of Contents Show

Difference between Singly linked list and Doubly linked list
Singly Linked List vs Doubly Linked List
Difference between Singly linked list and Doubly linked list in Java
What is Single Linked List
What is Double Linked List
Types of Linked List - Singly linked, doubly linked and circular

Introduction to Doubly linked list : A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.

Singly linked list vs Doubly linked list

Singly linked list (SLL)	Doubly linked list (DLL)
SLL nodes contains 2 field -data field and next link field.	DLL nodes contains 3 fields -data field, a previous link field and a next link field.

In SLL, the traversal can be done using the next node link only. Thus traversal is possible in one direction only.	In DLL, the traversal can be done using the previous node link or the next node link. Thus traversal is possible in both directions (forward and backward).
The SLL occupies less memory than DLL as it has only 2 fields.	The DLL occupies more memory than SLL as it has 3 fields.
Complexity of insertion and deletion at a given position is O(n).	Complexity of insertion and deletion at a given position is O(1).

Article Tags :

Data Structures

Difference Between

Linked List

doubly linked list

Practice Tags :

Data Structures

Linked List

Read Full Article

Singly Linked List vs Doubly Linked List

Before looking at the differences between the singly linked list and doubly linked list, we first understand what is singly linked list and doubly linked list separately.

Difference between Singly linked list and Doubly linked list in Java

Java 8Object Oriented ProgrammingProgramming

Both Singly linked list and Doubly linked list are the implementation of Linked list in which every element of singly-linked list contains some data and a link to the next element, which allows to keep the structure. On the other hand, every node in a doubly-linked list also contains a link to the previous node.

The following are the important differences between a Singly linked list and Doubly linked list.

Sr. No.	Key	Singly linked list	Doubly linked list
1	Complexity	In singly linked list the complexity of insertion and deletion at a known position is O(n)	In case od doubly linked list the complexity of insertion and deletion at a known position is O(1)
2	Internal implementation	In singly linked list implementation is such as where the node contains some data and a pointer to the next node in the list	While doubly linked list has some more complex implementation where the node contains some data and a pointer to the next as well as the previous node in the list
3	Order of elements	Singly linked list allows traversal elements only in one way.	Doubly linked list allows element two way traversal.
4	Usage	Singly linked list are generally used for implementation of stacks	On other hand doubly linked list can be used to implement stacks as well as heaps and binary trees.
5	Index performance	Singly linked list is preferred when we need to save memory and searching is not required as pointer of single index is stored.	If we need better performance while searching and memory is not a limitation in this case doubly linked list is more preferred.
6	Memory consumption	As singly linked list store pointer of only one node so consumes lesser memory.	On other hand Doubly linked list uses more memory per node(two pointers).

What is Single Linked List

A linked list is a linear data structure that consists of a group of nodes in a sequence. A node or an element consists of data and the address of another node. A single linked list is a type of linked list.

A single linked list stores the data and the address of the next node in the sequence. As the nodes stores the address of the next node, the nodes are referring to each other. Therefore, it forms a structure similar to a chain. It is possible to perform operations such as inserting, deleting and traversing through the elements in a single linked list.

What is Double Linked List

Similar to a single linked list, a double linked list is also a type of linked list. It is also called a doubly linked list. It stores data and two addresses. These addresses are the address of the next node and the address of the previous node. As there are two references, it is possible to go forward and backward through elements in the double linked list. Furthermore, the programmer can perform operations such as inserting elements and deleting elements in a double linked list.

In addition to these two types, there is another linked list as a circular linked list. In this kind of list, the last node stores the address of the first node. Therefore, it forms a structure similar to a circular chain.