Answer to Question #238510 in C for xyz

Question

1. Write a menu-driven program to perform the following operations in a double linked list by using suitable user-defined functions for each case.
a) Traversal of the list.
b) Check if the list is empty.
c) Insert a node at a certain position (at beginning/end/any position).
d) Delete a node at a certain position (at beginning/end/any position).
e) Delete a node for the given key.
f) Count the total number of nodes.
g) Search for an element in the linked list.
Verify & validate each function from main method.

Answer 1

#include<iostream>
using namespace std;


class Node {
  public:
    int key;
  int data;
  Node * next;
  Node * previous;


  Node() {
    key = 0;
    data = 0;
    next = NULL;
    previous = NULL;
  }
  Node(int k, int d) {
    key = k;
    data = d;
  }
};


class DoublyLL {


  public:
    Node * head;


  DoublyLL() {
    head = NULL;
  }
  DoublyLL(Node * n) {
    head = n;
  }




  Node * nodeExists(int k) {
    Node * temp = NULL;
    Node * ptr = head;


    while (ptr != NULL) {
      if (ptr-> key == k) {
        temp = ptr;
      }
      ptr = ptr-> next;
    }


    return temp;
  }


 
  void appendNode(Node * n) {
    if (nodeExists(n-> key) != NULL) {
      cout << "Node Already exists with key value : " << n-> key << ". Append another node with different Key value" << endl;
    } else {
      if (head == NULL) {
        head = n;
        cout << "Node Appended as Head Node" << endl;
      } else {
        Node * ptr = head;
        while (ptr-> next != NULL) {
          ptr = ptr-> next;
        }
        ptr-> next = n;
        n-> previous = ptr;
        cout << "Node Appended" << endl;
      }
    }
  }


 
  void prependNode(Node * n) {
    if (nodeExists(n-> key) != NULL) {
      cout << "Node Already exists with key value : " << n-> key << ". Append another node with different Key value" << endl;
    } else {
      if (head == NULL) {
        head = n;
        cout << "Node Prepended as Head Node" << endl;
      } else {
        head-> previous = n;
        n-> next = head;
        head = n;
        cout << "Node Prepended" << endl;
      }


    }
  }




  void deleteNodeByKey(int k) {
    Node * ptr = nodeExists(k);
    if (ptr == NULL) {
      cout << "Node does not exist with key value: " << k << endl;
    } else {


      if (head-> key == k) {
        head = head-> next;
        cout << "Node UNLINKED with keys value : " << k << endl;
      } else {
        Node * nextNode = ptr-> next;
        Node * prevNode = ptr-> previous;
        // deleting at the end
        if (nextNode == NULL) {


          prevNode-> next = NULL;
          cout << "Node Deleted at the END" << endl;
        }


        else {
          prevNode-> next = nextNode;
          nextNode-> previous = prevNode;
          cout << "Node Deleted in between" << endl;


        }
      }
    }
  }




	
   void search()
   {
   		cout<<"Enter element to search : ";
   		int x;
   		cin>>x;
	   	if(head == NULL)
	   	{
	   		cout<<"Empty List"<<endl;
	   		return;
		}
		else{
			Node* temp = head;
			bool ans = false;
			while(temp!= NULL)
			{
				if(temp->data == x)
				{
					cout<<"Element found"<<endl;
					ans = true;
					break;
				}
			}
			if(ans == false)
			{
				cout<<"Element not found"<<endl;
			}
		}
   }
   
   void count()
		{
			int c = 0;
			if(head == NULL)
			{
				cout<<"Number of nodes = 0"<<endl;
				return;
			}
			else{
				Node* temp = head;
				while(temp!= NULL)
				{
					c++;
					temp = temp->next;
				}
			}
			cout<<"Count of nodes : "<<c<<endl;
		}


  void updateNodeByKey(int k, int d) {


    Node * ptr = nodeExists(k);
    if (ptr != NULL) {
      ptr-> data = d;
      cout << "Node Updated Successfully" << endl;
    } else {
      cout << "Node Doesn't exist with key value : " << k << endl;
    }


  }


  void printList() {
    if (head == NULL) {
      cout << "No Nodes in Doubly Linked List";
    } else {
      cout << endl << "Doubly Linked List Elements : ";
      Node * temp = head;


      while (temp != NULL) {
        cout << "(" << temp-> key << "," << temp-> data << ") <--> ";
        temp = temp-> next;
      }
    }


  }
  
  void insertNodeAfter(int k, Node * n) {
    Node * ptr = nodeExists(k);
    if (ptr == NULL) {
      cout << "Node does not exist with key value: " << k << endl;
    } else {
      if (nodeExists(n-> key) != NULL) {
        cout << "Node Already exists with key value : " << n-> key << ". Append another node with different Key value" << endl;
      } else {
        Node * nextNode = ptr-> next;
        if (nextNode == NULL) {
          ptr-> next = n;
          n-> previous = ptr;
          cout << "Node Inserted at the END" << endl;
        }


        else {
          n-> next = nextNode;
          nextNode-> previous = n;
          n-> previous = ptr;
          ptr-> next = n;


          cout << "Node Inserted in between" << endl;


        }


      }
    }
  }




};


int main() 
{
  DoublyLL obj;
  int option;
  int key1, k1, data1;
  do {
    cout << "\nSelect what you want to perform? Select Option number. Enter 0 to exit." << endl;
    cout << "1. Append Node()" << endl;
    cout << "2. Prepend Node()" << endl;
    cout << "3. Insert Node After()" << endl;
    cout << "4. Delete Node By Key()" << endl;
    cout << "5. Update Node By Key()" << endl;
    cout << "6. Display()" << endl;
    cout << "7. Search()" << endl;
    cout << "8. Count()" << endl;
    cout << "9. Clear Screen" << endl << endl;


    cin >> option;
    Node * n1 = new Node();


    switch (option) {
    case 0:
      break;
    case 1:
      cout << "Append Node Operation \nEnter key & data of the Node to be Appended" << endl;
      cin >> key1;
      cin >> data1;
      n1-> key = key1;
      n1-> data = data1;
      obj.appendNode(n1);
      break;


    case 2:
      cout << "Prepend Node Operation \nEnter key & data of the Node to be Prepended" << endl;
      cin >> key1;
      cin >> data1;
      n1-> key = key1;
      n1-> data = data1;
      obj.prependNode(n1);
      break;


    case 3:
      cout << "Insert Node After Operation \nEnter key of existing Node after which you want to Insert this New node: " << endl;
      cin >> k1;
      cout << "Enter key & data of the New Node first: " << endl;
      cin >> key1;
      cin >> data1;
      n1-> key = key1;
      n1-> data = data1;


      obj.insertNodeAfter(k1, n1);
      break;


    case 4:


      cout << "Delete Node By Key Operation - \nEnter key of the Node to be deleted: " << endl;
      cin >> k1;
      obj.deleteNodeByKey(k1);


      break;
    case 5:
      cout << "Update Node By Key Operation - \nEnter key & NEW data to be updated" << endl;
      cin >> key1;
      cin >> data1;
      obj.updateNodeByKey(key1, data1);


      break;
    case 6:
      obj.printList();


      break;
    case 7:
      obj.search();
      break;
    case 8:
      obj.count();
      break;
    case 9:
      system("cls");
      break;
    default:
      cout << "Enter Proper Option number " << endl;
    }


  } while (option != 0);


  return 0;
}