Data structure & Algorithms

Link List

Link list is a linear data structure. Unlike array link list elements or node is not stored in contiguous memory location.

1: What is a Link List?

Link list is linear data structure which node or elements are stored at different memory location. Two nodes of link list is connected with each other by a reference

In above image you can identify two type of variables i.e. first type of variable to store the data & second type of variable to is a pointer to store the next or previous node of link list.There are various type of link list i.e. single link list , doubly link list , circular link list. This section page describes about single link list.


2: How to declare and define a node of Link List

Let us learn this with example : i.e.
a: define a node of link list that can store an integer value


typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL; //head node as a start node of link list
							

3: Insert an element at beginning of Link List

This section provides code to do how to insert an element at beginning of an link list
Problem statement:
- allocate memory for a node of link list.
- Insert newly created node at beginning of link list.
A. Solution Steps:
- Create new node say 'A'
- Fill data in node 'A'
- Assign head node to next element of node 'A'.
- assign node 'A' to head


#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;

void insert_at_beginning_linklist(LinkList *node)
{

    node->next = head;
    head = node;

}

void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert at Beginning";
   cout<<"\n2: Print Link List";
   cout<<"\n3: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            insert_at_beginning_linklist(node);
          }
    }
    else if(index == 2)
    {
        display();
    }
  } while(index != 3);

  return 0;
}
							   



4: Insert an element/node as a last node of link list

This insertion section describes how to insert an element as a last node of link list. This will explain 2 possible solution
Problem statement:
- Insert an element/node as end of link list.
A1. Solution steps: This is by traversing in link list from head node
- Hold head node in a temporary node
- traverse to next node utill next->next node is not null
- Assign the given node to next->next node
B1. Code is below


#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;

void insert_at_last_linklist(LinkList *node)
{
    LinkList *tmp_node = head;
    if(head == NULL)
        head = node;
    else
    {
        while(tmp_node->next != NULL)
        {
            tmp_node = tmp_node->next;
        }
        tmp_node->next = node;
    }
}
void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert at last";
   cout<<"\n2: Print Link List";
   cout<<"\n3: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            insert_at_last_linklist(node);
          }
    }
    else if(index == 2)
    {
        display();
    }
  } while(index != 3);

  return 0;
}

														
							
A2. Solution steps: Tis solution is by creating additional variable tail of link list
- Create pointer variable of type LinkList & name is tail
- Assign new node to tail next node
- Assign tail to tail next node
B2. Code is below

#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;
LinkList *tail = NULL;
void insert_at_last_linklist(LinkList *node)
{

    if(head == NULL)
    {
        head = node;
        tail = head;
    }

    else
    {
        tail->next = node;
        tail = tail->next;
    }
}
void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert at last";
   cout<<"\n2: Print Link List";
   cout<<"\n3: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            insert_at_last_linklist(node);
          }
    }
    else if(index == 2)
    {
        display();
    }
  } while(index != 3);

  return 0;
}
        
                            


5: Insert an element in link list before an existing element

This section explains & provide code to how to insert an element in link list before an existing element in link List.
Problem statement:
- Insert an element at before an given element present in link list.
- if element if not present insert as last element of link list.
A. Solution Steps
- Before searching element hold previous element in pointer variable.
- Move to next node to search
- Do this until found
- If found insert to previous node next
- This step is left for you to understand, you can see the code below to understand also
B. See below the complete Code: Run below code & test on your pc


#include <iostream>
#include <stdlib.h>
#include <malloc.h>

using namespace std;

typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;
LinkList *tail = NULL;
void insert_at_last_linklist(LinkList *node)
{

    if(head == NULL)
    {
        head = node;
        tail = head;
    }
    else
    {
        tail->next = node;
        tail = tail->next;
    }
}
void insert_before_an_element_linklist(LinkList *node, int data_to_find)
{
    //if no data in link list add to head
    if(head == NULL)
        insert_at_last_linklist(node);
    else
    {
        LinkList *prev = head;
        LinkList *tmpNode = head;
        while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        {
            prev = tmpNode;
            tmpNode = tmpNode->next;
        }
        if(tmpNode->data == data_to_find)
        {
            if(tmpNode == head)
            {
                node->next = head;
                head = node;
            }
            else
            {
                prev->next = node;
                node->next = tmpNode;

            }
        }
        else
        {
            insert_at_last_linklist(node);
        }
    }
}
void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert before a number";
   cout<<"\n2: Print Link List";
   cout<<"\n3: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_linklist(node,data_to_find);
          }
    }
    else if(index == 2)
    {
        display();
    }
  } while(index != 3);

  return 0;
}


							


6. Insert an element in link list after an element

This section is to explain how to insert an element in link list after an existing element of a list.
Problem statement:
- Insert an element after an given element present in link list.
- if element if not present insert as last element of link list.
A. Solution Steps
- Put head node in temporary node
- Move to next node to search
- Do this until found given element or data
- If found insert node to next node
B. See below the complete Code run to see result


#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;
LinkList *tail = NULL;
void insert_at_last_linklist(LinkList *node)
{

    if(head == NULL)
    {
        head = node;
        tail = head;
    }
    else
    {
        tail->next = node;
        tail = tail->next;
    }
}

void insert_after_an_element_linklist(LinkList *node, int data_to_find)
{
    if(head == NULL)
    {
        head = node;
        return;
    }
    LinkList *tmpNode = head;
    while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        tmpNode = tmpNode->next;
    node->next =tmpNode->next;
    tmpNode->next = node;
}
void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert after an element";
   cout<<"\n2: Print Link List";
   cout<<"\n3: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_after_an_element_linklist(node,data_to_find);
          }
    }
    else if(index == 2)
    {
        display();
    }
  } while(index != 3);

  return 0;
}

							



7. Delete an element in link list from beginning

Deletion of an element is another important operation. In this section we will describe how to delete an element or node from beginning in link list
Problem statement:
- Delete an element from beginning in link list.
A. Solution Steps
- Put next node from head to some temporary pointer variable
- delete head node.
- Assign temporary node to head of link list.
B. See below the complete Code


#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;
LinkList *tail = NULL;
void insert_at_last_linklist(LinkList *node)
{

    if(head == NULL)
    {
        head = node;
        tail = head;
    }
    else
    {
        tail->next = node;
        tail = tail->next;
    }
}
void insert_before_an_element_linklist(LinkList *node, int data_to_find)
{
    //if no data in link list add to head
    if(head == NULL)
        insert_at_last_linklist(node);
    else
    {
        LinkList *prev = head;
        LinkList *tmpNode = head;
        while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        {
            prev = tmpNode;
            tmpNode = tmpNode->next;
        }
        if(tmpNode->data == data_to_find)
        {
            if(tmpNode == head)
            {
                node->next = head;
                head = node;
            }
            else
            {
                prev->next = node;
                node->next = tmpNode;

            }
        }
        else
        {
            insert_at_last_linklist(node);
        }
    }
}
void insert_after_an_element_linklist(LinkList *node, int data_to_find)
{
    if(head == NULL)
    {
        head = node;
        return;
    }
    LinkList *tmpNode = head;
    while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        tmpNode = tmpNode->next;
    node->next =tmpNode->next;
    tmpNode->next = node;
}

void delete_from_beginning_linklist()
{
    if(head == NULL)
        return;
    LinkList *tmpNode = head->next;
    head->next = NULL;
    free(head);
    head = tmpNode;
}

void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert after an element";
   cout<<"\n2: Delete from beginning";
   cout<<"\n3: Print Link List";
   cout<<"\n4: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_after_an_element_linklist(node,data_to_find);
          }
    }
    else if(index == 2)
    {
        delete_from_beginning_linklist();
    }
    else if(index == 3)
    {
        display();
    }
  } while(index != 4);

  return 0;
}

							

8. Delete last node of link list

This section describe how to delete last element//node of link list
Problem statement:
- Delete last node of link list.
A. Solution Steps
- Check if head of link list NULL -> do nothing & return
- if head is not NULL but head->next is NULL delete head & return
- if above 2 statement is false then do following
- create 2 pointer variable i.e. prev & tmpNode of link list type & assign the head to both
- traverse in list while tmpNode->next is not null & keep assign prev to tmpNode
- Assign tail to prev & delete the tmpNode


void delete_from_last_linklist()
{
    if(head == NULL)
        return;
    LinkList *prev = head;
    LinkList *tmpNode = head;
    if(head->next == NULL)
    {
        free(head);
        head = NULL;
        tail = NULL;
    }
    while(tmpNode->next != NULL)
    {
        prev = tmpNode;
        tmpNode = tmpNode->next;
    }
    tail = prev;
    tail->next = NULL;
    free(tmpNode);
}
	   
							   
B. See below the complete Code

#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;
LinkList *tail = NULL;

void insert_after_an_element_linklist(LinkList *node, int data_to_find)
{
    if(head == NULL)
    {
        head = node;
        return;
    }
    LinkList *tmpNode = head;
    while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        tmpNode = tmpNode->next;
    node->next =tmpNode->next;
    tmpNode->next = node;
}


void delete_from_last_linklist()
{
    if(head == NULL)
        return;
    if(head->next == NULL)
    {
        free(head);
        head = NULL;
        tail = NULL;
    }
    LinkList *prev = head;
    LinkList *tmpNode = head;
    
	while(tmpNode->next != NULL)
    {
        prev = tmpNode;
        tmpNode = tmpNode->next;
    }
    tail = prev;
    tail->next = NULL;
    free(tmpNode);
}

void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert after an element";
   cout<<"\n2: Delete from last";
   cout<<"\n3: Print Link List";
   cout<<"\n4: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_after_an_element_linklist(node,data_to_find);
          }
    }
    else if(index == 2)
    {
        delete_from_last_linklist();
    }
    else if(index == 3)
    {
        display();
    }
  } while(index != 4);

  return 0;
}
						
							



9. Delete an element in link list after an element

This section describe how to delete an element after any element
Problem statement:
- Delete an element from array that exist after given number.
- e.g. given an array of 5 element 1 ,2,3,4,5 delete an element after 3 i.e. 4
A. Solution Steps
- If head of link list is NULL return.


if(head == NULL)
        return;
							   
- Traverse in link list until found the data or end of list

LinkList *tmpNode = head;
while(tmpNode != NULL && tmpNode->data != data)
{
	tmpNode = tmpNode->next;
}
							   
- if tmpNode is not NULL put tmpNode->next in tmp
- assign tempNode->next to tmpNode->next->next
- delete tmp node

if(tmpNode != NULL)
{
	LinkList *tmp = tmpNode->next;
	if(tmp)
	{
		tmpNode->next = tmp->next;
		if(tmp == tail)
			tail = tmpNode;
		free(tmp);
	}
}							   
- let us put all together

void delete_element_after_an_element_linklist(int data)
{
    if(head == NULL)
        return;

    LinkList *tmpNode = head;
    while(tmpNode != NULL && tmpNode->data != data)
    {
        tmpNode = tmpNode->next;
    }
    if(tmpNode != NULL)
    {
        LinkList *tmp = tmpNode->next;
        if(tmp)
        {
            tmpNode->next = tmp->next;
            if(tmp == tail)
                tail = tmpNode;
            free(tmp);
        }
    }
}

							
B. See below the complete Code

#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;
LinkList *tail = NULL;
void insert_at_last_linklist(LinkList *node)
{

    if(head == NULL)
    {
        head = node;
        tail = head;
    }
    else
    {
        tail->next = node;
        tail = tail->next;
    }
}
void insert_before_an_element_linklist(LinkList *node, int data_to_find)
{
    //if no data in link list add to head
    if(head == NULL)
        insert_at_last_linklist(node);
    else
    {
        LinkList *prev = head;
        LinkList *tmpNode = head;
        while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        {
            prev = tmpNode;
            tmpNode = tmpNode->next;
        }
        if(tmpNode->data == data_to_find)
        {
            if(tmpNode == head)
            {
                node->next = head;
                head = node;
            }
            else
            {
                prev->next = node;
                node->next = tmpNode;

            }
        }
        else
        {
            insert_at_last_linklist(node);
        }
    }
}
void insert_after_an_element_linklist(LinkList *node, int data_to_find)
{
    if(head == NULL)
    {
        head = node;
        return;
    }
    LinkList *tmpNode = head;
    while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        tmpNode = tmpNode->next;
    node->next =tmpNode->next;
    tmpNode->next = node;
}

void delete_from_beginning_linklist()
{
    if(head == NULL)
        return;
    LinkList *tmpNode = head->next;
    head->next = NULL;
    free(head);
    head = tmpNode;
}

void delete_from_last_linklist()
{
    if(head == NULL)
        return;
    LinkList *prev = head;
    LinkList *tmpNode = head;
    if(head->next == NULL)
    {
        free(head);
        head = NULL;
        tail = NULL;
    }
    while(tmpNode->next != NULL)
    {
        prev = tmpNode;
        tmpNode = tmpNode->next;
    }
    tail = prev;
    tail->next = NULL;
    free(tmpNode);
}
void delete_element_after_an_element_linklist(int data)
{
    if(head == NULL)
        return;

    LinkList *tmpNode = head;
    while(tmpNode != NULL && tmpNode->data != data)
    {
        tmpNode = tmpNode->next;
    }
    if(tmpNode != NULL)
    {
        LinkList *tmp = tmpNode->next;
        if(tmp)
        {
            tmpNode->next = tmp->next;
            if(tmp == tail)
                tail = tmpNode;
            free(tmp);
        }
    }
}

void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert after an element";
   cout<<"\n2: Delete after an element";
   cout<<"\n3: Print Link List";
   cout<<"\n4: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_after_an_element_linklist(node,data_to_find);
          }
    }
    else if(index == 2)
    {
        int data;
        cout<<"Enter data:";
        cin>>data;
        delete_element_after_an_element_linklist(data);
    }
    else if(index == 3)
    {
        display();
    }
  } while(index != 4);

  return 0;
}

							



10. All link list operation as single program

this section provides the single program to do following operation in link list
list of operation & index:



int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert at beginning";
   cout<<"\n2: Insert at last";
   cout<<"\n3: Insert before an element";
   cout<<"\n4: Insert after an element";
   cout<<"\n5: Delete from beginning";
   cout<<"\n6: Delete from last";
   cout<<"\n7: Delete after an element";
   cout<<"\n8: Print Link List";
   cout<<"\n9: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}

							
A. Code linklist.cpp

#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;


typedef struct _SingleLinkList
{
  int data;
  struct _SingleLinkList *next;// pointer variable to store address next element of linklist
} LinkList;

LinkList *head = NULL;
LinkList *tail = NULL;

void insert_at_beginning_linklist(LinkList *node)
{

    node->next = head;
    head = node;

}


void insert_at_last_linklist(LinkList *node)
{
    LinkList *tmp_node = head;
    if(head == NULL)
        head = node;
    else
    {
        while(tmp_node->next != NULL)
        {
            tmp_node = tmp_node->next;
        }
        tmp_node->next = node;
    }
}
void insert_before_an_element_linklist(LinkList *node, int data_to_find)
{
    //if no data in link list add to head
    if(head == NULL)
        insert_at_last_linklist(node);
    else
    {
        LinkList *prev = head;
        LinkList *tmpNode = head;
        while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        {
            prev = tmpNode;
            tmpNode = tmpNode->next;
        }
        if(tmpNode->data == data_to_find)
        {
            if(tmpNode == head)
            {
                node->next = head;
                head = node;
            }
            else
            {
                prev->next = node;
                node->next = tmpNode;

            }
        }
        else
        {
            insert_at_last_linklist(node);
        }
    }
}
void insert_after_an_element_linklist(LinkList *node, int data_to_find)
{
    if(head == NULL)
    {
        head = node;
        return;
    }
    LinkList *tmpNode = head;
    while(tmpNode->next != NULL && tmpNode->data != data_to_find)
        tmpNode = tmpNode->next;
    node->next =tmpNode->next;
    tmpNode->next = node;
}

void delete_from_beginning_linklist()
{
    if(head == NULL)
        return;
    LinkList *tmpNode = head->next;
    head->next = NULL;
    free(head);
    head = tmpNode;
}

void delete_from_last_linklist()
{
    if(head == NULL)
        return;
    LinkList *prev = head;
    LinkList *tmpNode = head;
    if(head->next == NULL)
    {
        free(head);
        head = NULL;
        tail = NULL;
    }
    while(tmpNode->next != NULL)
    {
        prev = tmpNode;
        tmpNode = tmpNode->next;
    }
    tail = prev;
    tail->next = NULL;
    free(tmpNode);
}
void delete_element_after_an_element_linklist(int data)
{
    if(head == NULL)
        return;

    LinkList *tmpNode = head;
    while(tmpNode != NULL && tmpNode->data != data)
    {
        tmpNode = tmpNode->next;
    }
    if(tmpNode != NULL)
    {
        LinkList *tmp = tmpNode->next;
        if(tmp)
        {
            tmpNode->next = tmp->next;
            if(tmp == tail)
                tail = tmpNode;
            free(tmp);
        }
    }
}

void display()
{
    LinkList *node = head;
    int index =1;
    cout<<"\ndata in link list present is : \n";
    while(node != NULL)
    {
        cout<data<<" " ;
        node = node->next;
        index++;
    }
}

int main_menu()
{
   int index = 0;
   cout<<"\n Main Menu\n";
   cout<<"\n==============================\n";
   cout<<"\n1: Insert at beginning";
   cout<<"\n2: Insert at last";
   cout<<"\n3: Insert before an element";
   cout<<"\n4: Insert after an element";
   cout<<"\n5: Delete from beginning";
   cout<<"\n6: Delete from last";
   cout<<"\n7: Delete after an element";
   cout<<"\n8: Print Link List";
   cout<<"\n9: Exit";
   cout<<"\n==============================\n";
   cout<<"\nEnter Your Input: ";
   cin>>index;
   return index;
}


int main()
{
  int index = 0;
  do{
    index = main_menu();

    if(index == 1)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            insert_at_beginning_linklist(node);
          }
    }
    else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            insert_at_last_linklist(node);
          }
    }
    else if(index == 3)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_linklist(node,data_to_find);
          }
    }
    else if(index == 4)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_after_an_element_linklist(node,data_to_find);
          }
    }
    else if(index == 5)
    {
        delete_from_beginning_linklist();
    }
    else if(index == 6)
    {
        delete_from_last_linklist();
    }
    else if(index == 7)
    {
        int data;
        cout<<"Enter data:";
        cin>>data;
        delete_element_after_an_element_linklist(data);
    }
    else if(index == 8)
    {
        display();
    }
  } while(index != 9);

  return 0;
}