Data structure & Algorithms

Doubly Link List

Doubly Link list same as single link list i.e. is a linear data structure.

1: What is a Doubly Link List?

Doubly Link list is linear data structure which node or elements are stored at different memory location. The Difference between Single Link List and Doubly Link List is that in single link list is contains address of next node in link list while in doubly link list it contains 2 address i.e. similar to single link list i.e. address of next node along with other address to store the address of previous node. This property makes all operation simple and easy.

In above image you can identify three 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. This section page describes about doubly 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 _doublyLinkList
{
  int data;
  struct _doublyLinkList *next;// pointer variable to store address of next element of linklist
  struct _doublyLinkList *previous;// pointer variable to store address of previous 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 or data at beginning of a doubly link list
Problem statement:
- allocate memory for a node of link list.
- Insert newly created node at beginning of doubly link list.
A. Solution Steps:
- Define the doubly link list structure like below


typedef struct _doublyLinkList
{
  int data;
  struct _doublyLinkList *next;// pointer variable to store address of next element of linklist
  struct _doublyLinkList *previous;// pointer variable to store address of previous element of linklist
} LinkList;
 
							   
- Define a head node for doubly link list

LinkList *head = NULL; //head node as a start node of link list
							   
- Allocate a memory in a node and put the data inside node.

LinkList *node = (LinkList *)malloc(sizeof(LinkList));
if(node != NULL)
{
	cout<<"\nEnter name : ";
	cin>>node->data;
}
							   
- Now our next task to write a function that can assign current head node to next pointer variable given node and assign head node previous pointer with given node.


void insert_at_beginning_doubly_link_list(LinkList *node)
{
    /*create temporary node & hold head */
    LinkList *tmpNode = head; 
   //this will be new head node so it's previous node is NULL.
    node->previous = NULL;
   //Assing the next link List node
    node->next = tmpNode;
   //make new head node
    head = node;
}
							   
- complete code to insert at beginning in doubly link list is below

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

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

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

void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}

void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}

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_doubly_link_list(node);
          }
    }
    else if(index == 2)
    {
        dispaly_linkList();
    }
  } while(index != 3);

  return 0;
}
						   



4: Insert an element/node as a last node of double 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 doubly link list.
Solution steps: Till now we have seen how to add at beginning. This section describes how to add a last.
- if head node of link list is NULL assign the node to head


if(head == NULL)
{
   head = node;
   head->next = NULL;
   head->previous = NULL;
   return;
}
							   
- Now if head node is not NULL traverse to link list until node->next variable is not null

LinkList *tmp = head;
while(tmp->next != NULL)
	tmp = tmp->next;

							   
- Assign the given node to tmp->next as a next node, & initialize the previous & next pointer variable with respective value.

tmp->next = node;
node->previous = tmp;
node->next = NULL;
								
Now let put this code in a function


void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}
								
- The complete code using add at last is below

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

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

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


void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}


void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}
void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}
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: 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;
            insert_at_beginning_doubly_link_list(node);
          }
    }
	else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            insert_at_last_doublyLinkList(node);
          }
    }
    else if(index == 3)
    {
        dispaly_linkList();
    }
  } while(index != 4);

  return 0;
}

							


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

This section explains how to insert an element in doubly link list before an existing element in link List.
Problem statement:
- Insert an element at before an given element present in doubly link list.
- if element if not present insert as last element of doubly link list.
A. Solution Steps
- if head element is null assign to head node.


if(head == NULL)
{
   head = node;
   head->next = head->previous = NULL;
}
							   
- if head is not null i.e. link list has some data, search the given data or element

LinkList *tmp = head;
while(tmp->next != NULL && tmp->data != existing_data)
    tmp = tmp->next;

							   
- if data found add the element before identified node

if(tmp->data == existing_data)
{
  LinkList *prev = tmp->previous;
  tmp->previous = node;
  node->next = tmp;
  node->previous = prev;
  if(prev != NULL)
	prev->next = node;
}
							   
- Check if identified node is head node so update the head

if(tmp->data == existing_data)
{
  LinkList *prev = tmp->previous;
  tmp->previous = node;
  node->next = tmp;
  node->previous = prev;
  if(prev != NULL)
	prev->next = node;
  if(tmp == head)
  {
	  head = node;
	  node->previous = NULL;
  }
}
							   
- if given element not exist add at last

if(tmp->data == existing_data)
{
  ....
}
else
{
  tmp->next = node;
  node->previous = tmp;
  node->next = NULL;
}
                               
- Let us put all this code in a function

void insert_before_an_element_doublyLinkList(LinkList *node, int existing_data)
{
   if(head == NULL)
   {
       head = node;
       head->next = head->previous = NULL;
   }
   else
   {
      LinkList *tmp = head;
      while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
      if(tmp->data == existing_data)
      {
          LinkList *prev = tmp->previous;
          tmp->previous = node;
          node->next = tmp;
          node->previous = prev;
          if(prev != NULL)
            prev->next = node;
          if(tmp == head)
          {
              head = node;
              node->previous = NULL;
          }
      }
      else
      {
          tmp->next = node;
          node->previous = tmp;
          node->next = NULL;
      }
   }
}
                               
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 _doublyLinkList
{
  int data;
  struct _doublyLinkList *next;// pointer variable to store address of next element of linklist
  struct _doublyLinkList *previous;// pointer variable to store address of previous element of linklist
} LinkList;

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

void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}

void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}

void insert_before_an_element_doublyLinkList(LinkList *node, int existing_data)
{
   if(head == NULL)
   {
       head = node;
       head->next = head->previous = NULL;
   }
   else
   {
      LinkList *tmp = head;
      while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
      if(tmp->data == existing_data)
      {
          LinkList *prev = tmp->previous;
          tmp->previous = node;
          node->next = tmp;
          node->previous = prev;
          if(prev != NULL)
            prev->next = node;
          if(tmp == head)
          {
              head = node;
              node->previous = NULL;
          }
      }
      else
      {
          tmp->next = node;
          node->previous = tmp;
          node->next = NULL;
      }
   }
}
void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}
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: Print Link List";
   cout<<"\n5: 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_doubly_link_list(node);
          }
    }
    else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            insert_at_last_doublyLinkList(node);
          }
    }
    else if(index == 3)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_doublyLinkList(node,data_to_find);
          }
    }
    else if(index == 4)
    {
        dispaly_linkList();
    }
  } while(index != 5);

  return 0;
}
							


6. Insert an element in link list after an element

This section is to explain how to insert an element in doubly link list after an existing element of a list.
Problem statement:
- Insert an element after an given element present in doubly link list.
- if element if not present insert as last element of doubly link list.
A. Solution Steps
- If head node is null add the node


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

							   
- if head is not null search the element until element is found or next node is null

LinkList *tmp = head;
while(tmp->next != NULL && tmp->data != existing_data)
	tmp = tmp->next;

							   
- Now add the new node a next element

LinkList *nextList = tmp->next;
tmp->next = node;
node->previous = tmp;
node->next = nextList;
							   
- Let us put this code in single function

void insert_element_after_an_element_doublyLinkList(LinkList *node, int existing_data)
{
    if(head == NULL)
    {
       head = node;
       head->next = head->previous = NULL;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        LinkList *nextList = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = nextList;

    }
}
							   
B. See below the complete Code & let us test it

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

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

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

void insert_element_after_an_element_doublyLinkList(LinkList *node, int existing_data)
{
    if(head == NULL)
    {
       head = node;
       head->next = head->previous = NULL;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        LinkList *nextList = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = nextList;

    }
}


void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}

void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}

void insert_before_an_element_doublyLinkList(LinkList *node, int existing_data)
{
   if(head == NULL)
   {
       head = node;
       head->next = head->previous = NULL;
   }
   else
   {
      LinkList *tmp = head;
      while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
      if(tmp->data == existing_data)
      {
          LinkList *prev = tmp->previous;
          tmp->previous = node;
          node->next = tmp;
          node->previous = prev;
          if(prev != NULL)
            prev->next = node;
          if(tmp == head)
          {
              head = node;
              node->previous = NULL;
          }
      }
      else
      {
          tmp->next = node;
          node->previous = tmp;
          node->next = NULL;
      }
   }
}
void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}
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: Print Link List";
   cout<<"\n6: 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_doubly_link_list(node);
          }
    }
    else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            insert_at_last_doublyLinkList(node);
          }
    }
    else if(index == 3)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_doublyLinkList(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_element_after_an_element_doublyLinkList(node,data_to_find);
          }
    }
    
    else if(index == 5)
    {
        dispaly_linkList();
    }
  } while(index != 6);

  return 0;
}

							



7. Delete an element in doubly 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 doubly link list
Problem statement:
- Delete an element from beginning in doubly link list.
A. Solution Steps
- Check if head is null then return


if(head == NULL)
	return;

							   
- if head is not null store next list of head in some variable and delete head

LinkList *nextList = head->next;
delete(head);
							   
- now assign next list to head & make previous is null.

head = nextList;
if(head != NULL)
	head->previous = NULL;
							   
- let us put above code in single function delete from beginning is ready.

void delete_from_beginning_doublylinklist()
{
    if(head == NULL)
        return;
    LinkList *nextList = head->next;
    delete(head);
    head = nextList;
    if(head != NULL)
        head->previous = NULL;
}
							   
B. Let us put all code together

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


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

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

void delete_from_beginning_doublylinklist()
{
    if(head == NULL)
        return;
    LinkList *nextList = head->next;
    delete(head);
    head = nextList;
    if(head != NULL)
        head->previous = NULL;
}
void insert_element_after_an_element_doublyLinkList(LinkList *node, int existing_data)
{
    if(head == NULL)
    {
       head = node;
       head->next = head->previous = NULL;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        LinkList *nextList = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = nextList;

    }
}


void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}

void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}

void insert_before_an_element_doublyLinkList(LinkList *node, int existing_data)
{
   if(head == NULL)
   {
       head = node;
       head->next = head->previous = NULL;
   }
   else
   {
      LinkList *tmp = head;
      while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
      if(tmp->data == existing_data)
      {
          LinkList *prev = tmp->previous;
          tmp->previous = node;
          node->next = tmp;
          node->previous = prev;
          if(prev != NULL)
            prev->next = node;
          if(tmp == head)
          {
              head = node;
              node->previous = NULL;
          }
      }
      else
      {
          tmp->next = node;
          node->previous = tmp;
          node->next = NULL;
      }
   }
}
void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}
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: Print Link List";
   cout<<"\n7: 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_doubly_link_list(node);
          }
    }
    else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            insert_at_last_doublyLinkList(node);
          }
    }
    else if(index == 3)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_doublyLinkList(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_element_after_an_element_doublyLinkList(node,data_to_find);
          }
    }
    else if(index == 5)
    {
        delete_from_beginning_doublylinklist();
    }
    
    else if(index == 6)
    {
        dispaly_linkList();
    }
  } while(index != 7);

  return 0;
}

							

8. Delete last node of doubly link list

This section describe how to delete last element//node of doubly link list
Problem statement:
- Delete last node of doubly link list.
A. Solution Steps
- Check if head of link list NULL -> do nothing & return


if(head == NULL)
    return ;
							   
- if head is not NULL take head in temporary node & traverse in link list until it's next element is null

while(tmp->next != NULL)
	tmp = tmp->next;
   
							   
- if current node is head delete head & assign null

  if(tmp == head)
    {
       delete(head);
       head = NULL;
    }
  
							   
- If current node is not null then hold previous node make previous next node null & delete current node

  if(tmp == head)
    {
     ....
    }
    else
    {
        LinkList *prev = tmp->previous;
        delete(tmp);
        prev->next = NULL;
    }
  
							   
- put all above code in a function and this ready to use


void delete_from_last_doubly_link_list()
{
    if(head == NULL)
        return ;
    LinkList *tmp = head;
    while(tmp->next != NULL)
        tmp = tmp->next;
    if(tmp == head)
    {
       delete(head);
       head = NULL;
    }
    else
    {
        LinkList *prev = tmp->previous;
        delete(tmp);
        prev->next = NULL;
    }
}
							   
B. See below the complete Code - to use delete_from_last_doubly_link_list()

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


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

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

void delete_from_last_doubly_link_list()
{
    if(head == NULL)
        return ;
    LinkList *tmp = head;
    while(tmp->next != NULL)
        tmp = tmp->next;
    if(tmp == head)
    {
       delete(head);
       head = NULL;
    }
    else
    {
        LinkList *prev = tmp->previous;
        delete(tmp);
        prev->next = NULL;
    }
}

void delete_from_beginning_doublylinklist()
{
    if(head == NULL)
        return;
    LinkList *nextList = head->next;
    delete(head);
    head = nextList;
    if(head != NULL)
        head->previous = NULL;
}
void insert_element_after_an_element_doublyLinkList(LinkList *node, int existing_data)
{
    if(head == NULL)
    {
       head = node;
       head->next = head->previous = NULL;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        LinkList *nextList = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = nextList;

    }
}


void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}

void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}

void insert_before_an_element_doublyLinkList(LinkList *node, int existing_data)
{
   if(head == NULL)
   {
       head = node;
       head->next = head->previous = NULL;
   }
   else
   {
      LinkList *tmp = head;
      while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
      if(tmp->data == existing_data)
      {
          LinkList *prev = tmp->previous;
          tmp->previous = node;
          node->next = tmp;
          node->previous = prev;
          if(prev != NULL)
            prev->next = node;
          if(tmp == head)
          {
              head = node;
              node->previous = NULL;
          }
      }
      else
      {
          tmp->next = node;
          node->previous = tmp;
          node->next = NULL;
      }
   }
}
void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}
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<<"\n8: Delete before an element"*/
   cout<<"\n7: Print Link List";
   cout<<"\n8: 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_doubly_link_list(node);
          }
    }
    else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            insert_at_last_doublyLinkList(node);
          }
    }
    else if(index == 3)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_doublyLinkList(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_element_after_an_element_doublyLinkList(node,data_to_find);
          }
    }
    else if(index == 5)
    {
        delete_from_beginning_doublylinklist();
    }
    else if(index == 6)
    {
        delete_from_last_doubly_link_list();
    }
    else if(index == 7)
    {
        dispaly_linkList();
    }
  } while(index != 8);

  return 0;
}

						
							



9. Delete an element in doubly link list after an element

This section describe how to delete an element after any element
Problem statement:
- Delete an element from doubly link list that exist after given number.
- e.g. given an doubly link list 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 *tmp = head;
while(tmp->next != NULL && tmp->data != existing_data)
	tmp = tmp->next;

							   
- do following steps now
- if at current node having given data
- check if next node of current node is not null - delete next node but before deleting next node update previous & next

 if(tmp->data == existing_data)
	{
	   LinkList *next = tmp->next;
	   if(next != NULL)
	   {
		  tmp->next = next->next;
		  if(next->next != NULL)
		  {
			  next->next->previous = tmp;
			  next->next = NULL;
			  next->previous = NULL;
		  }
		  else
		  {
			  tmp->next = NULL;
		  }
		  delete(next);
	   }
	}
							   
- let us put all code together in a function

void delete_element_after_an_element_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        if(tmp->data == existing_data)
        {
           LinkList *next = tmp->next;
           if(next != NULL)
           {
              tmp->next = next->next;
              if(next->next != NULL)
              {
                  next->next->previous = tmp;
                  next->next = NULL;
                  next->previous = NULL;
              }
              else
              {
                  tmp->next = NULL;
              }
              delete(next);
           }
        }
    }
}

							
B. Code to use this operation

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


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

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

void delete_element_after_an_element_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        if(tmp->data == existing_data)
        {
           LinkList *next = tmp->next;
           if(next != NULL)
           {
              tmp->next = next->next;
              if(next->next != NULL)
              {
                  next->next->previous = tmp;
                  next->next = NULL;
                  next->previous = NULL;
              }
              else
              {
                  tmp->next = NULL;
              }
              delete(next);
           }
        }
    }
}

void delete_from_last_doubly_link_list()
{
    if(head == NULL)
        return ;
    LinkList *tmp = head;
    while(tmp->next != NULL)
        tmp = tmp->next;
    if(tmp == head)
    {
       delete(head);
       head = NULL;
    }
    else
    {
        LinkList *prev = tmp->previous;
        delete(tmp);
        prev->next = NULL;
    }
}

void delete_from_beginning_doublylinklist()
{
    if(head == NULL)
        return;
    LinkList *nextList = head->next;
    delete(head);
    head = nextList;
    if(head != NULL)
        head->previous = NULL;
}
void insert_element_after_an_element_doublyLinkList(LinkList *node, int existing_data)
{
    if(head == NULL)
    {
       head = node;
       head->next = head->previous = NULL;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        LinkList *nextList = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = nextList;

    }
}


void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}

void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}

void insert_before_an_element_doublyLinkList(LinkList *node, int existing_data)
{
   if(head == NULL)
   {
       head = node;
       head->next = head->previous = NULL;
   }
   else
   {
      LinkList *tmp = head;
      while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
      if(tmp->data == existing_data)
      {
          LinkList *prev = tmp->previous;
          tmp->previous = node;
          node->next = tmp;
          node->previous = prev;
          if(prev != NULL)
            prev->next = node;
          if(tmp == head)
          {
              head = node;
              node->previous = NULL;
          }
      }
      else
      {
          tmp->next = node;
          node->previous = tmp;
          node->next = NULL;
      }
   }
}
void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}
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_doubly_link_list(node);
          }
    }
    else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            insert_at_last_doublyLinkList(node);
          }
    }
    else if(index == 3)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_doublyLinkList(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_element_after_an_element_doublyLinkList(node,data_to_find);
          }
    }
    else if(index == 5)
    {
        delete_from_beginning_doublylinklist();
    }
    else if(index == 6)
    {
        delete_from_last_doubly_link_list();
    }
    else if(index == 7)
    {
        int data;
        cout<<"Enter data:";
        cin>>data;
        delete_element_after_an_element_doubly_link_list(data);
    }
    else if(index == 8)
    {
        dispaly_linkList();
    }
  } while(index != 9);

  return 0;
}

							



10. Delete before an element

Problem statement: - Delete an element from doubly link list that exist before given number.
- e.g. given an doubly link list of 5 element 1 ,2,3,4,5 delete an element after 3 i.e. 2
Solution:
- if head is null return


if(head == NULL)
	return;
							
- Traverse the in link list until found the data or next element is null

LinkList *tmp = head;
while(tmp->next != NULL && tmp->data != existing_data)
	tmp = tmp->next;
							
- if current node is head node, then return

if(tmp->data == existing_data)
{
	if(tmp == head)
	   return;
}
							
- if current node previous is head node, then delete head

if(tmp->data == existing_data)
{
	if(tmp == head)
	   return;
	else
	{
		LinkList *prev = tmp->previous;
		if(prev == head)
		{
			delete(head);
			head = tmp;
			head->previous = NULL;
		}
	}
}
							
- if current node previous is not head node, then delete previous node

if(tmp->data == existing_data)
{
	if(tmp == head)
	   return;
	else
	{
		LinkList *prev = tmp->previous;
		if(prev == head)
		{
			delete(head);
			head = tmp;
			head->previous = NULL;
		}
		else
		{
			LinkList *prev_prev = prev->previous;
			prev_prev->next = tmp;
			tmp->previous = prev_prev;
			delete(prev);
		}
	}
}							
- Now let us put these code in function


void delete_element_before_an_element_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    LinkList *tmp = head;
    while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
    if(tmp->data == existing_data)
    {
        if(tmp == head)
           return;
        else
        {
            LinkList *prev = tmp->previous;
            if(prev == head)
            {
                delete(head);
                head = tmp;
                head->previous = NULL;
            }
            else
            {
                LinkList *prev_prev = prev->previous;
                prev_prev->next = tmp;
                tmp->previous = prev_prev;
                delete(prev);
            }
        }
    }

}

							
Code to use this function

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


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

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


void delete_element_before_an_element_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    LinkList *tmp = head;
    while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
    if(tmp->data == existing_data)
    {
        if(tmp == head)
           return;
        else
        {
            LinkList *prev = tmp->previous;
            if(prev == head)
            {
                delete(head);
                head = tmp;
                head->previous = NULL;
            }
            else
            {
                LinkList *prev_prev = prev->previous;
                prev_prev->next = tmp;
                tmp->previous = prev_prev;
                delete(prev);
            }
        }
    }

}

void delete_element_after_an_element_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        if(tmp->data == existing_data)
        {
           LinkList *next = tmp->next;
           if(next != NULL)
           {
              tmp->next = next->next;
              if(next->next != NULL)
              {
                  next->next->previous = tmp;
                  next->next = NULL;
                  next->previous = NULL;
              }
              else
              {
                  tmp->next = NULL;
              }
              delete(next);
           }
        }
    }
}

void delete_from_last_doubly_link_list()
{
    if(head == NULL)
        return ;
    LinkList *tmp = head;
    while(tmp->next != NULL)
        tmp = tmp->next;
    if(tmp == head)
    {
       delete(head);
       head = NULL;
    }
    else
    {
        LinkList *prev = tmp->previous;
        delete(tmp);
        prev->next = NULL;
    }
}

void delete_from_beginning_doublylinklist()
{
    if(head == NULL)
        return;
    LinkList *nextList = head->next;
    delete(head);
    head = nextList;
    if(head != NULL)
        head->previous = NULL;
}
void insert_element_after_an_element_doublyLinkList(LinkList *node, int existing_data)
{
    if(head == NULL)
    {
       head = node;
       head->next = head->previous = NULL;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        LinkList *nextList = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = nextList;

    }
}


void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}

void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}

void insert_before_an_element_doublyLinkList(LinkList *node, int existing_data)
{
   if(head == NULL)
   {
       head = node;
       head->next = head->previous = NULL;
   }
   else
   {
      LinkList *tmp = head;
      while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
      if(tmp->data == existing_data)
      {
          LinkList *prev = tmp->previous;
          tmp->previous = node;
          node->next = tmp;
          node->previous = prev;
          if(prev != NULL)
            prev->next = node;
          if(tmp == head)
          {
              head = node;
              node->previous = NULL;
          }
      }
      else
      {
          tmp->next = node;
          node->previous = tmp;
          node->next = NULL;
      }
   }
}
void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}
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: Delete before an element";
   cout<<"\n9: Print Link List";
   cout<<"\n10: 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_doubly_link_list(node);
          }
    }
    else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            insert_at_last_doublyLinkList(node);
          }
    }
    else if(index == 3)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_doublyLinkList(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_element_after_an_element_doublyLinkList(node,data_to_find);
          }
    }
    else if(index == 5)
    {
        delete_from_beginning_doublylinklist();
    }
    else if(index == 6)
    {
        delete_from_last_doubly_link_list();
    }
    else if(index == 7)
    {
        int data;
        cout<<"Enter data:";
        cin>>data;
        delete_element_after_an_element_doubly_link_list(data);
    }
    else if(index == 8)
    {
        int data;
        cout<<"Enter data:";
        cin>>data;
        delete_element_before_an_element_doubly_link_list(data);
    }

    else if(index == 9)
    {
        dispaly_linkList();
    }
  } while(index != 10);

  return 0;
}
							



11. Delete an element in doubly link list

Problem statement: - Delete an element from doubly link list .
- e.g. given an doubly link list of 5 element 1 ,2,3,4,5 delete an element 3
Solution:
Please see below code


void delete_an_element_from_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    LinkList *tmp = head;
    while(tmp != NULL && tmp->data != existing_data)
        tmp = tmp->next;
    if(tmp != NULL)
    {
        if(tmp == head)
        {
            tmp = tmp->next;
            delete(head);
            head = tmp->next;
        }
        else
        {
            LinkList *next = tmp->next;
            LinkList *prev = tmp->previous;
            prev->next = next;
            if(next)
                next->previous = prev;
            delete(tmp);
        }
    }
}
							
- complete code of doubly link list with all it's operation is below

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


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

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

void delete_an_element_from_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    LinkList *tmp = head;
    while(tmp != NULL && tmp->data != existing_data)
        tmp = tmp->next;
    if(tmp != NULL)
    {
        if(tmp == head)
        {
            tmp = tmp->next;
            delete(head);
            head = tmp->next;
        }
        else
        {
            LinkList *next = tmp->next;
            LinkList *prev = tmp->previous;
            prev->next = next;
            if(next)
                next->previous = prev;
            delete(tmp);
        }
    }
}

void delete_element_before_an_element_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    LinkList *tmp = head;
    while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
    if(tmp->data == existing_data)
    {
        if(tmp == head)
           return;
        else
        {
            LinkList *prev = tmp->previous;
            if(prev == head)
            {
                delete(head);
                head = tmp;
                head->previous = NULL;
            }
            else
            {
                LinkList *prev_prev = prev->previous;
                prev_prev->next = tmp;
                tmp->previous = prev_prev;
                delete(prev);
            }
        }
    }

}

void delete_element_after_an_element_doubly_link_list(int existing_data)
{
    if(head == NULL)
        return;
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        if(tmp->data == existing_data)
        {
           LinkList *next = tmp->next;
           if(next != NULL)
           {
              tmp->next = next->next;
              if(next->next != NULL)
              {
                  next->next->previous = tmp;
                  next->next = NULL;
                  next->previous = NULL;
              }
              else
              {
                  tmp->next = NULL;
              }
              delete(next);
           }
        }
    }
}

void delete_from_last_doubly_link_list()
{
    if(head == NULL)
        return ;
    LinkList *tmp = head;
    while(tmp->next != NULL)
        tmp = tmp->next;
    if(tmp == head)
    {
       delete(head);
       head = NULL;
    }
    else
    {
        LinkList *prev = tmp->previous;
        delete(tmp);
        prev->next = NULL;
    }
}

void delete_from_beginning_doublylinklist()
{
    if(head == NULL)
        return;
    LinkList *nextList = head->next;
    delete(head);
    head = nextList;
    if(head != NULL)
        head->previous = NULL;
}
void insert_element_after_an_element_doublyLinkList(LinkList *node, int existing_data)
{
    if(head == NULL)
    {
       head = node;
       head->next = head->previous = NULL;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL && tmp->data != existing_data)
            tmp = tmp->next;
        LinkList *nextList = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = nextList;

    }
}


void insert_at_beginning_doubly_link_list(LinkList *node)
{
    LinkList *tmpNode = head;
    node->previous = NULL;
    node->next = tmpNode;
    head = node;
}

void insert_at_last_doublyLinkList(LinkList *node)
{
    if(head == NULL)
    {
       head = node;
       head->next = NULL;
       head->previous = NULL;
       return;
    }
    else
    {
        LinkList *tmp = head;
        while(tmp->next != NULL)
            tmp = tmp->next;
        tmp->next = node;
        node->previous = tmp;
        node->next = NULL;
    }
}

void insert_before_an_element_doublyLinkList(LinkList *node, int existing_data)
{
   if(head == NULL)
   {
       head = node;
       head->next = head->previous = NULL;
   }
   else
   {
      LinkList *tmp = head;
      while(tmp->next != NULL && tmp->data != existing_data)
        tmp = tmp->next;
      if(tmp->data == existing_data)
      {
          LinkList *prev = tmp->previous;
          tmp->previous = node;
          node->next = tmp;
          node->previous = prev;
          if(prev != NULL)
            prev->next = node;
          if(tmp == head)
          {
              head = node;
              node->previous = NULL;
          }
      }
      else
      {
          tmp->next = node;
          node->previous = tmp;
          node->next = NULL;
      }
   }
}
void dispaly_linkList()
{
    cout<<"\n===========================\n";
    cout<<"\nData present in link list is : \n";
    LinkList *tmpNode = head;
    while(tmpNode != NULL)
    {
        cout<<" "<data;
        tmpNode = tmpNode->next;
    }
    cout<<"\n===========================\n";
}
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: Delete before an element";
   cout<<"\n9: Delete an element";
   cout<<"\n10: Print Link List";
   cout<<"\n11: 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_doubly_link_list(node);
          }
    }
    else if(index == 2)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            insert_at_last_doublyLinkList(node);
          }
    }
    else if(index == 3)
    {
          LinkList *node = (LinkList *)malloc(sizeof(LinkList));
          if(node != NULL)
          {
            cout<<"\nEnter name : ";
            cin>>node->data;
            node->next = NULL;
            node->previous = NULL;
            int data_to_find;
            cout<<"\nEnter Data to Find: ";
            cin>>data_to_find;
            insert_before_an_element_doublyLinkList(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_element_after_an_element_doublyLinkList(node,data_to_find);
          }
    }
    else if(index == 5)
    {
        delete_from_beginning_doublylinklist();
    }
    else if(index == 6)
    {
        delete_from_last_doubly_link_list();
    }
    else if(index == 7)
    {
        int data;
        cout<<"Enter data:";
        cin>>data;
        delete_element_after_an_element_doubly_link_list(data);
    }
    else if(index == 8)
    {
        int data;
        cout<<"Enter data:";
        cin>>data;
        delete_element_before_an_element_doubly_link_list(data);
    }
    else if(index == 9)
    {
        int data;
        cout<<"Enter data:";
        cin>>data;
        delete_an_element_from_doubly_link_list(data);
    }

    else if(index == 10)
    {
        dispaly_linkList();
    }
  } while(index != 11);

  return 0;
}