Variants of Linked List

Types of Linked List:-

Singly Linked List
Doubly Linked List
Circular Linked List
Circularly Doubly Linked List


Singly Linked List:-

It is a one-way linked list.
Singly Linked List (or simply, 'Linked List') has,
One data part and One pointer, the last node points to NULL.

The structure of node of SLL is already shown in previous chapter.

Uses:-

The list is not required to be contiguously present in the memory.
The node can reside any where in the memory and linked together to make a list.
This achieves optimized utilization of space.
list size is limited to the memory size and doesn't need to be declared in advance.
Empty node can not be present in the linked list.
We can store values of primitive types or objects in the singly linked list.


Doubly Linked List:-

Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence.

Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer).

The node structure in C:-
struct node { struct node *prev; int data; struct node *next; }

In a singly linked list, we could traverse only in one direction, because each node contains address of the next node and it doesn't have any record of its previous nodes. However, doubly linked list overcome this limitation of singly linked list.


Circular Linked List:-

In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list.

We traverse a circular singly linked list until we reach the same node where we started.
The circular singly liked list has no beginning and no ending.
There is no null value present in the next part of any of the nodes.

Node Structure is same as that of single linked list.
Only difference is that, the last node does not point to NULL but to the first node address.

Circular linked list are mostly used in task maintenance in operating systems.
There are many examples where circular linked list are being used in computer science including browser surfing where a record of pages visited in the past by the user, is maintained in the form of circular linked lists and can be accessed again on clicking the previous button.


Circular Doubly Linked List:-

Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node.

Circular doubly linked list doesn't contain NULL in any of the node.
The last node of the list contains the address of the first node of the list.
The first node of the list also contain address of the last node in its previous pointer.

Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more space per node and more expensive basic operations.
However, a circular doubly linked list provides easy manipulation of the pointers and the searching becomes twice as efficient.