The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Linked List

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;
}

Back | Next

All problems on Linked List
* Insert, Delete and Search nodes in a single linked list
* Insert, Delete and Search nodes in a double linked list
* Sort a linked list where each node element is either 1 or 0
* Reverse a linked list in an efficient manner
* Merge two sorted linked lists
* Detect a loop in a given linked list