Types of Linked List in Data Structure

In this section of the tutorial, we will discuss the different types of Linked List in Data Structure such as, Doubly Linked List, Circular Linked List, and Circular Doubly List and their implementation in programs.

Now let’s move on further to the Complex Linked List Implementation which defines the other types of Linked List and their use in Data Structure.

Complex Linked List Implementation

The implementation we have learnt till now is Singly Linked List as it contains only link to a single successor. But there are also other complex linked list implementation in data structure.

Complex linked list implementation consists of three important implementations, i.e. the circularly linked list, the doubly linked list, and the multilinked list.

We wil discuss each of them now. Let’s learn about the first type, i.e. Circularly Linked List.

Circularly Linked List

In a circularly linked list, the points of the last node is linked to the first node of the list. They are mainly used in such list that allows access to the middle nodes of the list without starting at the beginning.

  • The insertion and deletion operations in a circularly linked list are the same as the deleting and inserting operations of a singly linked list that we have discussed earlier.
  • The only difference is that the last node points to the first node of the list.
  • So it is important to point the link field to the first node of the list when we are doing any inserting and deleting operation.

Doubly Linked List

Doubly Linked List is one of the most powerful implementations in the data structure. It is a linked list structure where every node has a pointer associated with both its successor and predecessor.

  • In the head structure, there are three pieces of metadata in the head, i.e. a count, a position pointer, and a rear pointer.
  • Rear pointers are not necessary to be used in all doubly linked lists, it is only used in some of the list algorithms like an insert and search for making the algorithm more efficient.
  • Each node has two pointers associated with it, i.e. a backward pointer to its predecessor and a forward pointer to its successor.
Insertion

Insert operation performs insertion of a node into a singly linked list, and with also connecting the forward and backward pointers to each other. In a null doubly linked list, the head and rear pointers are null.

  • To insert a node into a null list, the head and rear pointers are set to point to the new node and the forward and backward pointers of the new node is set to null.
  • When inserting between the nodes, the new node must be set to point to both its predecessor and its successor, and they must be set to point to the new node.
  • When inserting at the end, the backward pointer of the new node is set to point to its predecessor. As there is no successor, the forward pointer is set to null.
  • And lastly, the rear pointer in the head must also be set to point to the new rear node.
Deletion

Deletion operation is quite straightforward to carry out in a doubly linked list.

  • If the deleted node’s predecessor is present, it is set to point to the deleted node’s successor.
  • If the deleted node’s successor is present, it is set to point to the deleted tot he deleted node’s predecessor.
  • Once the node is located to be deleted, we simply change the predecessor’s and successor’s pointers of the node and recycle the node.

Multi-Linked Lists

The multilinked list is a list that contains two or more logical key sequences. For example, let’s assume we have a list of 10 presidents of US that is listed chronologically by the date when the president joined.

  • The advantage of using the multilinked list is that the same set of data can be processed into multiple sequences.
  • In a multilinked list, the data are not duplicated anywhere in the list.
  • The data is always one of a kind and exists only once in the list, but multiple paths connect the one set of data.
Insertion

In the diagram above, there can be seen two logical lists. So when adding a node to the list, we must insert it into each of the logical lists there.

  • For different logical lists with different logical keys, we always use separate algorithms for each node insertion and search.
  • The might be situations where we only call insert as long as we read data, otherwise, we don’t call insert in case of any error or we have reached the end of the file.
  • Similarly, we can only call insert as long as the memory allocation in the build node module is active, otherwise, we can’t call insert if it is not active or fails.
Deletion

In the node deleting operation in multilinked list, we must always reconnect the pointer for each logical list.

In the above president list example, if we delete a president’s record, we also need to adjust the spouse’s as well as the president’s successor pointer.

Further, we will perform the insertion and deletion of nodes in a program to understand the implementation more clearly.

Program example to demonstrate the implementation of Complex Linked List Operations

Code:

#include<stdio.h>  
#include<stdlib.h>  
struct node  
{  
    struct node *prev;  
    struct node *next;  
    int data;  
};  
struct node *head;  
void insert_begin();  
void insert_end();  
void delete_begin();  
void delete_end();  
void display();  
void find();  
void main()  
{  
int n =0;  
    while(n!=9)  
    {    
        printf("\nChoose 1 to insert node in beginning\nChoose 2 to insert node at last\nChoose 3 to delete node from beginning\nChoose 4 to delete node from last\nChoose 5 to search node\nChoose 6 to show node\nChoose 7 to exit\n");  
        printf("\nPress number for your choice.\n");  
        scanf("\n%d",&n);  
        switch(n)  
        {  
            case 1:  
            insert_begin();  
            break;  
            case 2:  
            insert_end();  
            break;  
            case 3:  
            delete_begin();  
            break;  
            case 4:  
            delete_end();  
            break;  
            case 5:  
            find();  
            break;  
            case 6:  
            display();  
            break;  
            case 7:  
            exit(0);  
            break;  
            default:  
            printf("Enter a valid number.");  
        }  
    }  
}  
void insert_begin()  
{  
   struct node *ptr,*temp;   
   int element;  
   ptr = (struct node *)malloc(sizeof(struct node));  
   if(ptr == NULL)  
   {  
       printf("\nOverflow");  
   }  
   else  
   {  
    printf("\nEnter the value of item: ");  
    scanf("%d",&element);  
    ptr->data=element;  
   if(head==NULL)  
   {  
      head = ptr;  
      ptr -> next = head;   
      ptr -> prev = head;   
   }  
   else   
   {  
       temp = head;   
    while(temp -> next != head)  
    {  
        temp = temp -> next;   
    }  
    temp -> next = ptr;  
    ptr -> prev = temp;  
    head -> prev = ptr;  
    ptr -> next = head;  
    head = ptr;  
   }  
   printf("\nNode inserted successfully.\n");  
}  
     
}  
void insert_end()  
{  
   struct node *ptr,*temp;  
   int element;  
   ptr = (struct node *) malloc(sizeof(struct node));  
   if(ptr == NULL)  
   {  
       printf("\nOverflow");  
   }  
   else  
   {  
       printf("\nEnter a value:");  
       scanf("%d",&element);  
        ptr->data=element;  
       if(head == NULL)  
       {  
           head = ptr;  
           ptr -> next = head;   
           ptr -> prev = head;   
       }  
       else  
       {  
          temp = head;  
          while(temp->next !=head)  
          {  
              temp = temp->next;  
          }  
          temp->next = ptr;  
          ptr ->prev=temp;  
          head -> prev = ptr;  
      ptr -> next = head;  
        }  
   }  
     printf("\nNode inserted successfully.\n");  
}  
  
void delete_begin()  
{  
    struct node *temp;  
    if(head == NULL)  
    {  
        printf("\nUnderflow");  
    }  
    else if(head->next == head)  
    {  
        head = NULL;   
        free(head);  
        printf("\nNode deleted successfully.\n");  
    }  
    else  
    {  
        temp = head;   
        while(temp -> next != head)  
        {  
            temp = temp -> next;  
        }  
        temp -> next = head -> next;  
        head -> next -> prev = temp;  
        free(head);  
        head = temp -> next;  
    }  
  
}  
void delete_end()  
{  
    struct node *ptr;  
    if(head == NULL)  
    {  
        printf("\nUnderflow");  
    }  
    else if(head->next == head)  
    {  
        head = NULL;   
        free(head);   
        printf("\nNode deleted successfully.\n");  
    }  
    else   
    {  
        ptr = head;   
        if(ptr->next != head)  
        {  
            ptr = ptr -> next;   
        }  
        ptr -> prev -> next = head;  
        head -> prev = ptr -> prev;    
        free(ptr);  
        printf("\nNode deleted successfully.\n");  
    }  
}  
  
void display()  
{  
    struct node *ptr;  
    ptr=head;  
    if(head == NULL)  
    {  
        printf("\nNo data to print.");  
    }     
    else  
    {   
        while(ptr -> next != head)  
        {  
          
            printf("%d\n", ptr -> data);  
            ptr = ptr -> next;  
        }  
        printf("%d\n", ptr -> data);  
    }  
              
}  
  
void find()  
{  
    struct node *ptr;  
    int element,i=0,flag=1;  
    ptr = head;   
    if(ptr == NULL)  
    {  
        printf("\nEmpty list found\n");  
    }  
    else  
    {   
        printf("\nEnter data to be searched?\n");   
        scanf("%d",&element);  
        if(head ->data == element)  
        {  
        printf("Data found at location [%d]",i+1);  
        flag=0;  
        }  
        else   
        {  
        while (ptr->next != head)  
        {  
            if(ptr->data == element)  
            {  
                printf("Data found at location [%d] ",i+1);  
                flag=0;  
                break;  
            }   
            else  
            {  
                flag=1;  
            }  
            i++;  
            ptr = ptr -> next;  
        }  
        }  
        if(flag != 0)  
        {  
            printf("Data not found.\n");  
        }  
    }     
          
}

In the next section of the tutorial, we will discuss the use of Stack in Data Structure and its implementation in programs that will be used thoroughly in this Data Structure tutorial.