Types of Linked List

There are four types of linked lists. They are

• Singly Linked List
• Doubly Linked List
• Circular Linked List
• Doubly Circular Linked List

Singly Linked List

• Each node has a single link to another node is called Singly Linked List.
• Singly Linked List does not store any pointer any reference to the previous node.
• Each node stores the contents of the node and a reference to the next node in the list.
• In a singly linked list, last node has a pointer which indicates that it is the last node. It requires a reference to the first node to store a single linked list.
• It has two successive nodes linked together in linear way and contains address of the next node to be followed.
• It has successor and predecessor. First node does not have predecessor while last node does not have successor. Last node have successor reference as NULL.
• It has only single link for the next node.
• In this type of linked list, only forward sequential movement is possible, no direct access is allowed.

In the above figure, the address of the first node is always store in a reference node known as Head or Front. Reference part of the last node must be null.

 Doubly Linked List

• Doubly linked list is a sequence of elements in which every node has link to its previous node and next node.
• Traversing can be done in both directions and displays the contents in the whole list.

In the above figure, Link1 field stores the address of the previous node and Link2 field stores the address of the next node. The Data Item field stores the actual value of that node. If we insert a data into the linked list, it will be look like as follows:

Important Note:
First node is always pointed by head. In doubly linked list, previous field of the first node is always NULL (it must be NULL) and the next field of the last must be NULL.

In the above figure we see that, doubly linked list contains three fields. In this, link of two nodes allow traversal of the list in either direction. There is no need to traverse the list to find the previous node. We can traverse from head to tail as well as tail to head.

Advantages of Doubly Linked List

• Doubly linked list can be traversed in both forward and backward directions.
• To delete a node in singly linked list, the previous node is required, while in doubly linked list, we can get the previous node using previous pointer.
• It is very convenient than singly linked list. Doubly linked list maintains the links for bidirectional traversing.

Disadvantages of Doubly Linked List

• In doubly linked list, each node requires extra space for previous pointer.
• All operations such as Insert, Delete, Traverse etc. require extra previous pointer to be maintained.

Circular Linked List

• Circular linked list is similar to singly linked list. The only difference is that in circular linked list, the last node points to the first node in the list.
• It is a sequence of elements in which every element has link to its next element in the sequence and has a link to the first element in the sequence.

• In the above figure we see that, each node points to its next node in the sequence but the last node points to the first node in the list. The previous element stores the address of the next element and the last element stores the address of the starting element. It forms a circular chain because the element points to each other in a circular way.
• In circular linked list, the memory can be allocated when it is required because it has a dynamic size.
• Circular linked list is used in personal computers, where multiple applications are running. The operating system provides a fixed time slot for all running applications and the running applications are kept in a circular linked list until all the applications are completed. This is a real life example of circular linked list.
• We can insert elements anywhere in circular linked list, but in the array we cannot insert elements anywhere in the list because it is in the contiguous memory.

Doubly Circular Linked List

• Doubly circular linked list is a linked data structure which consists of a set of sequentially linked records called nodes.
• Doubly circular linked list can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.

• The above diagram represents the basic structure of Doubly Circular Linked List. In doubly circular linked list, the previous link of the first node points to the last node and the next link of the last node points to the first node.
• In doubly circular linked list, each node contains two fields called links used to represent references to the previous and the next node in the sequence of nodes.