Please answer in C++ only. 21.8 Lab: Doubly-linked list Doubly-linked list Lab S
ID: 3744506 • Letter: P
Question
Please answer in C++ only.
21.8 Lab: Doubly-linked list
Doubly-linked list Lab Specification
Implement a doubly-linked list with dummy head and tail nodes to store integer values. Unlike singly-linked list which only allows forward navigation, a doubly-linked list allows you to navigate the list in both forward and backward directions. A node in a doubly-linked list stores two pointers, prev and next. prev points to the previous node in the list and next points to the next node in the list. The header file (IntList.h) should declare and implement the IntNode struct (just copy it exactly as it is below) as well as the IntList Class interface only. You are also required to come up with a separate implementation file (IntList.cpp) that implements the member functions of the IntList class.
IntNode struct
The IntNode struct you are required to use is provided. This struct definition is in the IntList.h file exactly as is. Make sure it is above the definition of your IntList class. Notice that you will not code an implementation file for the IntNode struct. The IntNode constructor has been defined inline (within the class declaration). Do not write any other functions for the IntNode struct. Use as is.
IntList class
To avoid dealing with special cases, it is usually more convenient to add two dummy nodes at both end of a doubly-linked list. Dummy node does not contain any data. A dummy head node precedes the first node in the list and dummy tail follows the last node in the list.
Encapsulated (Private) Data Fields
dummyHead: IntNode *
dummyTail: IntNode *
Public Interface (Public Member Functions)
IntList(): Initializes an empty list with dummy head and dummy tail.
~IntList(): Deallocates all remaining dynamically allocated memory (all remaining IntNodes).
void push_front(int value): Inserts a data value (within a new node) at the front end of the list. This must be an O(1) operation.
void pop_front(): Removes the node at the front end of the list (the node after the dummy head). Does nothing if the list is already empty. This must be an O(1) operation.
void push_back(int value): Inserts a data value (within a new node) at the back end of the list. This must be an O(1) operation.
void pop_back(): Removes the node at the back end of the list (the node before the dummy tail). Does nothing if the list is already empty. This must be an O(1) operation.
bool empty() const: Returns true if the list does not store any data values (it only has dummy head and dummy tail), otherwise returns false.
friend ostream & operator<<(ostream &out, const IntList &rhs): A global friend function that outputs to the stream all of the integer values within the list on a single line, each separated by a space. This function does NOT send to the stream a newline or space at the end.
void printReverse() const: prints to a single line all of the int values stored in the list in REVERSE order, each separated by a space. This function does NOT output a newline or space at the end.
Explanation / Answer
#include <iostream>
using namespace std;
struct IntNode {
int data;
IntNode *prev;
IntNode *next;
IntNode(int data) : data(data), prev(0), next(0) {}
IntNode()
{
data=0;
prev=NULL;
next=NULL;
}
};
class IntList
{
public:
IntList ()
{
head=new IntNode();
tail=new IntNode();
head->next=tail;
tail->prev=head;
size=2;
}
~IntList ()
{
while(head!=NULL)
{ IntNode *temp;
temp=head->next;
delete head;
head=temp;
temp=temp->prev;
}
}
void push_front(int value);
void pop_front();
void push_back(int value);
void pop_back();
bool empty() const;
friend ostream & operator<<(ostream &out, const IntList &rhs);
void printReverse() const;
void print()const;
IntNode *head;
IntNode *tail;
int size;
};
void IntList::printReverse()const
{
IntNode * temp=tail->prev;
cout<<"reverse of linkedlist element:"<<endl;
while(temp!=head)
{
cout<<temp->data<<" ";
temp=temp->prev;
}
}
void IntList::print()const
{
IntNode * temp=head->next;
while(temp!=tail)
{
cout<<temp->data<<" ";
temp=temp->next;
}
}
void IntList::push_front(int value)
{
struct IntNode *s, *temp;
temp = new IntNode(value);
s=head->next;
head->next=temp;
temp->prev=head;
temp->next=s;
s->prev=temp;
size++;
}
void IntList::push_back(int value)
{
struct IntNode *s, *temp;
temp = new IntNode(value);
s=tail->prev;
tail->prev=temp;
temp->next=tail;
temp->prev=s;
s->next=temp;
size++;
}
void IntList::pop_front()
{
struct IntNode *s, *temp;
if(size>2)
{
s=head->next->next;
s->prev=head;
temp=head->next;
head->next=s;
delete temp;
size--;
}
else
{
cout<<"list doesnot have element"<<endl;
}
}
bool IntList::empty()const
{
if(size<=2)
{
return true;
}
return false;
}
ostream & operator<<(ostream &out, const IntList &rhs) {
if (rhs.head == NULL) {
return out;
}
IntNode *st=rhs.head->next;
while(st!=rhs.tail)
{
out<<st->data<<" ";
st=st->next;
}
return out;
}
void IntList:: pop_back()
{
struct IntNode *s, *temp;
if(size>2)
{
s=tail->prev->prev;
s->next=tail;
temp=tail->prev;
tail->prev=s;
delete temp;
size--;
}
else
{
cout<<"list doesnot have element"<<endl;
}
}
int main()
{
//created class object linked list
IntList *c1=new IntList();
//list check
if(c1->empty())
cout<<"list is empty"<<endl<<endl;
else
cout<<"list not is empty"<<endl;
//push data into linked list
c1->push_back(1);
c1->push_back(2);
c1->push_back(3);
c1->push_back(4);
c1->push_back(5);
c1->push_back(6);
c1->push_back(7);
//show linked list value
cout<<"linked list after push back value:";
c1->print();
cout<<endl;
//push data front into linked list
c1->push_front(15);
c1->push_front(14);
c1->push_front(13);
c1->push_front(12);
c1->push_front(10);
//show linked list value after push front
cout<<endl;
cout<<"linked list after push front value:";
c1->print();
cout<<endl;
//pop first front from linked list
c1->pop_front();
cout<<endl;
//show linked list value after pop front value
cout<<"linked list after pop front value:";
c1->print();
//pop first back from linked list
cout<<endl;
c1->pop_back();
cout<<endl;
//show linked list value after pop back value
cout<<"linked list after pop back value:";
c1->print();
cout<<endl;
cout<<"linked list print using << operator overloading:";
cout<<endl;
cout << *c1 ;
return 0;
}