Double Ended List(Using as a Double-linked List) Use a head and tail pointer (an

Question

Double Ended List(Using as a Double-linked List)

Use a head and tail pointer (and size data member) that allows your doublylinked list to support O(1) addition and removal of items from the front and back.

here is the skeleton code delist.h, add appropriate data members to the DElist class definition in delist.h

#ifndef DELIST_H

#define DELIST_H

struct DEItem {

int val;

DEItem* prev;

DEItem* next;

};

class DEList {

public:

/// Constructs an empty Double-Ended List

DEList();

/// Destructor to clean-up memory of current list

~DEList();

/// returns a Boolean 'true' if the list is empty

bool empty();

/// returns number of items in the list

int size();

/// returns front item or -1 if empty list

int front();

/// returns back item or -1 if empty list

int back();

/// Adds a new integer to the front of the list

void push_front(int new_val);

/// Adds a new integer to the back of the list

void push_back(int new_val);

/// Removes the front item of the list (if it exists)

void pop_front();

/// Removes the back item of the list (if it exists)

void pop_back();

private:

// Add your private data here

};

#endif

then write the member functions in a file named "delist.cpp"

here is the skeleton code for delist_test.cpp

#include <iostream>

#include "delist.h"

using namespace std;

int main()

{

DEList list;

list.push_back(1);

cout << "Added 1 to the list and now front is " << list.front() << endl;

list.pop_front();

cout << "Removed item" << endl;

list.push_front(2);

cout << "Added 2 to the list and now back is " << list.back() << endl;

list.pop_back();

cout << "Removed item" << endl;

for(int i=0; i < 5; i++){

list.push_back(10+i);

list.push_front(20+i);

}

cout << "List size after adding 10 elements is " << list.size() << endl;

while(!list.empty()){

cout << "Popping front item = " << list.front() << endl;

list.pop_front();

}

cout << "Trying to pop an item that doesn't exist" << endl;

list.pop_front();

cout << "Renitiatlizing list" << endl;

for(int i=0; i < 5; i++){

list.push_back(10+i);

list.push_front(20+i);

}

while(!list.empty()){

cout << "Popping back item = " << list.back() << endl;

list.pop_back();

}

cout << "Trying to pop an item that doesn't exist" << endl;

list.pop_back();

list.push_back(100);

list.push_front(101);

cout << "Goodbye!" << endl;

return 0;

}

(if use NULL in .cpp, add the line#include in delist.cpp)

Explanation / Answer

#include
usingnamespace std;
struct node
{
    int data;
    node *next;
    node *prev;
};
void addnode();
void delnode();
void display();
void show();
void search();
node *start=NULL, *temp1, *temp2, *temp3;
int main()
{
    char ch;
    do
    {
        char i;
        cout<<"Press 'a' to add node , 'd' to delete"<         cout<<" 's' for search, 'v' for display ,'e' for backward display"<         cin>>i;
       switch (i)
       {
       case'a':
          addnode();
          break;
       case'd':
          delnode();
          break;
       case'v' :
          display();
          break;
       case's':
          search();
          break;
       case'e':
           show();
          break;
       default:
          cout<<"Bad input"<           break;
       }
       cout<<"want to process more y/n"<        cin>>ch;
     }
     while(ch!='n');
       return 0;
}
void addnode()          //adding node
{
    char r;
    temp1=new node;
    cout<<"enter int to store"<     cin>>temp1->data;
    cout<<"press 's' to add in start,'m' for midd , 'e' for end"<     cin>>r;
    switch (r)
    {
    case's':                 //add startif(start==NULL)
        {
            start=temp1;
            temp1->next=NULL;
            temp1->prev=NULL;
        }
        else
        {
            temp2=start;
            temp1->next=temp2;
            temp1->prev=NULL;
            start=temp1;
            temp2->prev=temp1;
        }
        break;
    case'e':               //add endif(start==NULL)
        {
            start=temp1;
            temp1->next=NULL;
            temp1->prev=NULL;
        }
        else
        {
            temp2=start;
            while(temp2->next!=NULL)
                temp2=temp2->next;
            temp2->next=temp1;
            temp1->prev=temp2;
            temp1->next=NULL;
        }
        break;
    case'm':                //add midint num;
        cout<<"enter node after which you want to enter"<         cin>>num;
        temp2=start;
        for(int i=0;i         {
            if(start==NULL)
                cout<<"given node not found"<             else
            {
               temp3=temp2;
               temp2=temp2->next;
             
            }
        }
         temp1->next=temp2;
         temp3->next=temp1;
         temp1->prev=temp3;
         temp2->prev=temp1;
        break;
    }
}
void display()        //displaying
{

    temp3=start;
    if(start==NULL)
        cout<<"no node to display"<     else
    {
      while(temp3->next!=NULL)
      {
          cout<<"Data stored is "<data<<" at "<          temp3=temp3->next;
      }
      cout<<"Data stored is "<data<<" at "<     }
}

void search()            //searching
{
    int p;
    cout<<"enter no to search"<     cin>>p;
    temp1=start;
    while(temp1->next!=NULL)
    {
        if(temp1->data==p)
        {
            cout<data<<" is stored in "<< temp1->next<         }
        temp1=temp1->next;
    }
}
void delnode()           //deleting
{
  
    char d;
    cout<<"press 's' to delete from start,'m' for midd , 'e' for end"<     cin>>d;
    switch (d)
    {
      case's':               //delete startif(start==NULL)
          {
              cout<<"no node to delete"<           }
          else
          {
              temp1=start;
              start=start->next;
              start->prev=NULL;
              delete temp1;
          }
         break;
      case'e':            //delete endif(start==NULL)
          {
              cout<<"no node to delete"<           }
         else
         {
             temp1=start;
             while(temp1->next!=NULL)
             {
                temp2=temp1;
                temp1=temp1->next;
             }
              delete temp1;
             temp2->next=NULL;
         }
        break;
      case'm':               //delete midint num;
          cout<<"enter node you want to delete"<           cin>>num;
        
          temp1=start;
          for(int i=1;i           {
              if(start==NULL)
               cout<<"given node does not exist"<               else
              {
                temp2=temp1;
                temp1=temp1->next;
              }
          }
          temp3=temp1->next;
          temp2->next=temp3;
          temp3->prev=temp2;
          delete temp1;
          break;
    }
}
void show()               //backward display
{
    cout<<"backward display"<     temp3=start;
    if(start==NULL)
        cout<<"no node to display"<     else
    {
       while(temp3->next!=NULL)
       {
           temp3=temp3->next;
       }
       while(temp3->prev!=NULL)
       {
           cout<<"Data stored is "<data<<" at "<            temp3=temp3->prev;
       }
       cout<<"Data stored is "<data<<" at "<     }
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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