3, 120 points) The class list shown below lements a list of integers using a dou

Question

3, 120 points) The class list shown below lements a list of integers using a doubly linked list Bll the impl storage mechanism. Note that the keeps track of the number of nodes using the member count. The retrieve front method returns the data at the front of the list and removes that node from the The retrieve back method returns the data at the back of the list and removes that node from the The store method stores an integer in node at middle of the list. That is, if we number the nodes starting with i at a new inserted the at position then the new node is inserted before the node count/2 1. The cases where count o and count m require special treatment The write method prints the list data separated by commas. Write the methods store and retrieve back of class list. File doublelist.cpp This program implements a store and retrieve mechanism asing a doubly linked list of integers sinclude Kiostream> sinclude Kfstrean? using Danespace atd: class node friend class list private int data this is the data in a list elenent node next; pointer to the next node in the list list node "previ Pointer to the previous node in the Public node (int x); data x, pre next NULL class list number of nodes in the list private pointer to front of the list pointer to the of the list int count node. front node. back constructor of an enpty list Public list (void) x at the front of the list int retrieve front (void) i put x at the back of the list of the list int retrieve back (void) Put the niddle void store (int x); store the data at pty (void) const i check for en list to out void write out) const; write data stored A list looks like data data data next next next prev prev front back int main(void) list mylist; mylist store (1); nylist store (2); mylist store (3); mylist store (4) my list write(cout) prints 2, 4, 3, 1 cout mylist retrieve-back endli 2 cout mylist retrieve ront endl; prints 1 f

Explanation / Answer

#include<iostream>
#include<fstream>

using namespace std;

class node {
friend class list;

private:
   int data;
   node *next;
   node *prev;

public :
   node(int x);
};

class list {
private :
   int count;
   node *front;
   node *back;

public :
   list(void);
   int retrieve_front(void);
   int retrieve_back(void);
   void store(int x);
   bool empty(void) const;
   void write(ostream &out) const;

};

node::node(int x) {
   data = x;
   next = NULL;
   prev = NULL;
}

list::list(void) {
   front = NULL;
   back = NULL;
   count = 0;
}

int list::retrieve_back(void) {

   if(front == NULL) {
       return 0;   // returning 0 in error case
   }

   node *nodeToBeRemoved = back;

   int data = nodeToBeRemoved->data;

   if(front == back) {
       front = NULL;
       back = NULL;
   } else {
       back = back->next;
       back->prev = NULL;
   }
   count--;
   delete nodeToBeRemoved;

   return data;
}

int list::retrieve_front(void) {

   if(front == NULL) {
       return 0;
   }

   node *nodeToBeRomoved = front;

   int data = nodeToBeRomoved->data;

   if(front == back) {
       front = NULL;
       back = NULL;
   } else {
       front = front->prev;
       front->next = NULL;
   }
   count--;
   delete nodeToBeRomoved;

   return data;
}

bool list::empty(void) const {

   if(count == 0)
       return 0;
   else
       return 1;
}

void list::store(int x) {

   node *nodeToBeAdded = new node(x);

   if(count == 0) {
       front = nodeToBeAdded;
       back = nodeToBeAdded;
   } else if(count == 1) {
       nodeToBeAdded->next = back;
       back->prev = nodeToBeAdded;
       back = nodeToBeAdded;
   } else {

       int pos = count/2+1;

       node *iter = back;

       while(pos > 1) {
           iter= iter->next;
           pos--;
       }

       nodeToBeAdded->next = iter;
       nodeToBeAdded->prev = iter->prev;

       iter->prev->next = nodeToBeAdded;

       iter->prev = nodeToBeAdded;

   }
   count++;

}

void list::write(ostream &out) const {

   node *iter = back;
   while(iter != NULL) {
       out << iter->data << "," ;
       iter = iter->next;
   }

}

int main(void) {
   list mylist;

   mylist.store(1);
   mylist.store(2);
   mylist.store(3);
   mylist.store(4);

   mylist.write(cout);

   cout<< endl;

   cout<< mylist.retrieve_back() << endl;
   cout<< mylist.retrieve_front() << endl;

   mylist.write(cout);

   return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.