**Problem :- **

Implement algorithms for inserting, deleting and searching nodes in a double linked list.

**Solution :- **

**Insert : ** To insert a new node in the beginning of the list, make the **next** pointer of the new node point to the **head** of the list, make the **prev** pointer of the **head node** point to the new node and make the new node as **head** . For inserting at the end, just traverse through the entire list and move to the last node,
then make the **next** pointer of the last node point to the new node and **prev** pointer of the new node point to the last node.

Suppose, you want to insert a new node **p** between two nodes **x** and **y** . Then, make **next** of **p** point to **y** ,
**prev** of **y** point to **p** ,
**next** of **x** point to **p** and **prev** of **p** point to **x** .

**Delete : ** Suppose the current list is **x <-> y <-> z**. To delete **x** , just make the **head**
point to **y** and delete **x** . To delete **z** , just make the **next** of **y** point to **NULL** and delete **z**.
To delete **y** , make the **next** of **x** point to **z** , **prev** of **z** point to **x** and delete **y** ( resulting list is **x <-> z** ).

**Search : ** To search a node, the list has to be traversed starting from the **head** of the list.

**#include<iostream>**
**using namespace** std;
*/* defines the structure of a double linked list node*/*
**typedef struct** list_node {
**int** data;
**struct** list_node *next; *// pointer to next node*
**struct** list_node *prev; *// pointer to previous node*
}node;
*/* create new node */*
node *getNewNode(**int** data) {
node *new_node = **new** node;
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
**return** new_node;
}
*/* displays the list elements */*
**void** displayList(node *head) {
cout << "Displaying List : ";
node *temp = NULL; *// used to display list in reverse direction*
**while** (head != NULL) {
cout << head->data << " -> ";
temp = head;
head = head->next;
}
cout << "NULL " << endl;
cout << "Displaying List in reverse direction : ";
**while** (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->prev;
}
cout << "NULL " << endl;
}
*/* Search the node with element as data
Return the pointer to the node if found else return NULL */*
node *searchNode(node *head, **int** data) {
node *ptr = NULL;
**while** (head) {
**if** (head->data == data) {
ptr = head;
**break**;
}
head = head->next;
}
**return** ptr;
}
*/* insert a node at the beginning of the list */*
node *insertNodeBeg(node *head, **int** data) {
node *ptr = getNewNode(data);
**if** (head == NULL) { *// if list is empty*
head = ptr;
}
**else** {
ptr->next = head;
head->prev = ptr;
head = ptr;
}
**return** head;
}
*/* insert a node at the end of the list */*
node *insertNodeEnd(node *head, **int** data) {
node *ptr = getNewNode(data);
**if** (head == NULL) { *//if list is empty*
head = ptr;
}
**else** {
node *temp = head;
**while** (temp->next != NULL) { *// move to the last node*
temp = temp->next;
}
temp->next = ptr; *// insert node at the end*
ptr->prev = temp;
}
**return** head;
}
*/* insert a node at the after a particular node in the list */*
node *insertNodeAfter(node *head, **int** element, **int** data) {
*// search the element after which node is to be inserted*
node *temp = searchNode(head, element);
**if** (temp == NULL) { *// element not found*
cout << "Element not found ... " << endl;
}
**else** {
node *ptr = getNewNode(data);
**if** (temp->next == NULL) { *// node has to inserted after the last node*
temp->next = ptr;
ptr->prev = temp;
}
**else** { *// insert the node after the first or an intermediate node*
ptr->next = temp->next;
temp->next->prev = ptr;
ptr->prev = temp;
temp->next = ptr;
}
}
**return** head;
}
*/* delete a particular node from the list */*
node *deleteNode(node *head, **int** element) {
node *temp = searchNode(head, element); *// search the node to be deleted*
**if** (temp == NULL) { *// element not found*
cout << "Node to be deleted not found ... " << endl;
}
**else** {
**if** (temp == head) { *// first node is to be deleted*
head = head->next;
head->prev = NULL;
**delete** temp;
}
**else if** (temp->next == NULL) { *// node to be deleted is the last node*
temp->prev->next = NULL;
**delete** temp;
}
**else** { *// node to deleted is an intermediate node*
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
**delete** temp;
}
}
**return** head;
}
**int** main() {
node *head = NULL;
head = insertNodeBeg(head, 7); *// 7*
head = insertNodeBeg(head, 9); *// 9 -> 7*
head = insertNodeEnd(head, 11); *// 9 -> 7 -> 11*
head = insertNodeAfter(head, 9, 4); *// 9 -> 4 -> 7 -> 11*
head = insertNodeAfter(head, 7, 3); *// 9 -> 4 -> 7 -> 3 -> 11*
head = insertNodeAfter(head, 11, 6); *// 9 -> 4 -> 7 -> 3 -> 11 -> 6*
displayList(head);
head = deleteNode(head, 7); *// 9 -> 4 -> 3 -> 11 -> 6*
head = deleteNode(head, 6); *// 9 -> 4 -> 3 -> 11*
head = deleteNode(head, 9); *// 4 -> 3 -> 11*
displayList(head);
**return** 0;
}