TYPES OF LINKED LIST

Types of linked list

1.  Singly linked list

2.  Doubly linked list

3.  Circular linked list

   1. Singly linked list

•   A singly linked list is a linked list in which each node contains only  one linked field pointing to the next node in the list.
•   Singly linked list does not store any pointer any reference to the next node in the list.
•    It has successor and predecessor. First node does not have predecessor while last node does not have successor. Last nodes have successor reference as null.
•   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.

Advantages:

• Insertion and deletion can be done easily.
• Its size is not fixed.
• It can be extended or reduce according to requirement.

Disadvantages:

• Different amount of time is required to access each element.
• We cannot traverse it from last, only from the beginning.            

 2.  Doubly linked list:

•    A Doubly linked list is a linked list in which each node has three fields namely data field, forward link(FLINK), backward link(BLINK).
•     FLINK points to the successor node in the list.
•   BLINK points to the predecessor node in the list. 

In the above figure, FLINK field stores the address of the previous node and BLINK field stores the address of the next node .The data element field stores the actual value of the node. If we insert  a data  into the linked list, it will be look like as follows,

In the above figure we see that, doubly linked list and we can traverse from head to tail as well as tail to head.  

Advantages:

• Deleting operation is easier.
• Finding the predecessor & successor of the node is easier.

Disadvantages: 

• More memory space is required since it has two pointers.

3.Circular  linked list:

         In circular linked list the pointer of the last node points to the first node.circular linked list can be implemented as singly linked list and doubly linked list with or without headers.

         (a).Singly linked circular list:  

                    In which last node of the list points to the  first node.

                        

               (b).Doubly linked circular list:

                      In which the forward link of the last node points to the first node and backward link of the first node points to  the last node of the list.

                         

Advantages:                                                                                       

• It allows to traverse the list starting at any point.
• It allows quick access to the first and last record.
• Circularly doubly linked list allows to traverse the list in either directions.   

Disadvantages:    

• It is not easy to reverse the linked list.
• If the proper care is not taken, then the problem of infinite loop can occur.

                                                                     *********