Show transcribed image text

Expert Answer

• 
  Sanat Taori answered this

  Was this answer helpful?

  641 answers

  1. Lets implement list ADT with all operations specified in question below is solution with detailed explaination using c++ comments.

  // header for input output
  #include <iostream>
  using namespace std;
  
  
  class ListADT
  {
  // since node should not be modified outside
  private:
          struct node
          {
                  // two feilds, current key and next node pointer
                  int key;
                  node *next;
          };
          // head of list
          node *head;
  
  
  
  public:
          // constructor, initially set head to null.
          ListADT()
          {
                  head = NULL;
          }
  
          // insert taking key as parameter
          void insertElement(int key)
          {
                  // create new node
                  node *n = new node;
                  // add new node to current key parameter
                  n->key = key;
                  // append to front, with next null
                  n-> next = head;
                  head = n;
          }
  
          // delete element from list
          int deleteElement()
          {
                  // temp node
                  node *temp;
                  // no elements
                  if (head == NULL) {
                          cout << "empty list" << endl;
                          return 0;
                  }
                  else
                          // remove first element
                          temp = head;
                  // and set next element to head
                  head = head->next;
                  delete(temp);
                  return (1);
          }
  
          // search for key in node
          int searchItem(int key)
          {
                  node *temp;
                  int pos = 0;
                  temp = head;
                  // iterate through list
                  while (temp != NULL) {
                          pos++;
                          // return key index if key found on node
                          if (temp->key == key)
                                  return (pos);
                          temp = temp->next;
                  }
                  // no key found
                  return (-1);
  
          }
  
          int countItems()
          {
                  // init count
                  int Count = 0;
                  if (head == NULL)
                          return 0;
                  node *temp;
                  temp = head;
                  // iterate through list
                  while (temp != NULL)
                  {
                          // increment count
                          Count++;
                          temp = temp->next;
                  }
                  return (Count);
          }
  
          // destructor, after instance ends delete all nodes list
          ~ListADT()
          {
                  while (head != NULL)
                          deleteElement();
          }
  };
  
  
  // driver code to test implemented listADT
  int main()
  {
          ListADT l1;
  
          // insert key
          l1.insertElement(10);
          l1.insertElement(20);
          l1.insertElement(30);
          cout << "count number of nodes before delete: " << l1.countItems() << endl;
  
          // delete element
          l1.deleteElement();
  
          // count elements
          cout << "count number of nodes after delete: " << l1.countItems() << endl;
  
          // search for 20, this will be first node
          cout << "search for key element (20) :" << l1.searchItem(20) << endl;
  
          return 0;
  }

  Output:

  As per chegg guidelines for multiple questions, I am allowed to solve only first question, unless specified in note.