Instructions :
- You have to design a doubly linked list container.
- The necessary classes and their declarations are given below
- The main() function for testing the your design is also given below. The outputs form each of the output statements are provided in the text box for your comparison.
- So complete the program by supplying your implementations of the member functions. Some are already implemented, use as it is.
// List . h
template
class List;
template
std::ostream& operator<< (std::ostream& os, const List& l);
template
class Link;
template
class ListIterator;
template
class List{
friend std::ostream& operator<< (std::ostream& os, const List& l);
public:
typedef ListIterator Iterator;
List() : first_(0), last_(0) {};
List(const List & other); // copy constructor
~List(); // destructor
List & operator = (const List & rhs); // assignment operator
T& front() const; // returns the front element
void push_front(const T& e); // adds from front
void pop_front(); // deletes from front
T& back() const; // returns the last element
void push_back(const T& e); // adds from back
void pop_back(); // deletes the last element
void clear(); // emptied by deleting all elements in it
bool empty() const; // return true if list id empty
int size() const; // returns the no. of elements
Iterator begin();
Iterator end();
Iterator insert(Iterator& itr, const T& val);
void insert(Iterator& itr, int n, const T& val);
void erase(Iterator& itr);
void erase(Iterator& start, Iterator& stop);
private:
void copy(const List & other); // private utility only, users use =
Node* first; // points to first node
Node* last; // points to last node
};
template
std::ostream& operator<< (std::ostream& os, const List& lst){
os<<"f[ ";
Link *pp = lst.first_; //cursor to lst
while(pp != 0){
if(pp != lst.first_)os<<", ";
os<< pp->elem_;
pp = pp->next_;
}
os<<" ]b"<
return os;
}
template // implements the node of a doubly linked list
class Node{
friend class List;
friend class ListIterator;
friend std::ostream& operator<< (std::ostream& os, const List& l);
private:
Node(const T& e) : elem_(e), next_(0), prev_(0){} // constrructor
T elem_; // element value
Node* next; // pointer to next element in the list
Node* prev; // pointer to the previous element in the list
};
template // implements a iterator for the list class
class ListIterator{
friend class List;
typedef ListIterator Iterator;
public:
ListIterator(List* list = 0, Link* ccNode = 0) : list_(list), cNode(ccNode) {}
T& operator *(){
// returns the element value of the node pointed by the iterator
}
bool operator == (Iterator rhs){
// returns true if this integrator and itertrator rhs are pointing to same node }
bool operator != (Iterator rhs){
// returns false if this integrator and itertrator rhs are pointing to same node
}
Iterator& operator ++ (int){
// advance the iterator to the right
}
Iterator operator ++ (){
// postfix version
}
Iterator& operator -- (int){
// backward the iterator by one position to the left
}
Iterator operator -- (){
// postfix version
};
private:
List* list; // pointer to current doubly linked list object
Node* cNode; // pointer to the node in the doubly linked list
};
// Main driver program
#include "List.h"
#include
#include
using namespace std;
typedef List ListD;
typedef List ListI;
typedef List ListS;
int main(){
ListD x;
x.push_front(4.4); x.push_front(3.3); x.push_front(2.2); x.push_front(1.1);
ListD y(x);
ListD z = x;
// output is shown in the text box 1
cout<< "x.front = "<< x.front()<< endl;
cout<< "List x ="<
cout<< "x.size() ="<< x.size()<< endl;
while(!x.empty()){
cout<< x.front()<< endl;
x.pop_front();
}
cout<< "x.size() now = "<< x.size()<< endl;
cout<< "List y ="<
cout<< y<< endl;
cout<< "List z ="<
cout<< z<< endl;
ListD v;
v = y;
v.pop_front();
// output is show in the text box 2
cout<< "List v (v = y; v.pop_front();) ="<
cout<< v<< endl;
ListI li;
li.push_front(3); li.push_front(2); li.push_front(1);
// output is show in the text box 3
cout<< "List li via operator <<"<
cout<< li<< endl;
li.push_back(22);
li.push_back(33);
// output is show in the text box 4
cout<< "li.push_back(22), li.push_back(33)"<< endl;
cout<< li<< endl;
cout<< "back(), pop.back()"<< endl;
while(!li.empty()){
cout<< li.back()<< endl;
li.pop_back();
}
ListS ls;
ls.push_front("abcd");
ls.push_front("cdefgh");
ls.push_back("back");
cout<< ls<< endl; // output is show in the text box 5
ListI c5;
for(uint i = 0; i< 5; ++i){
c5.push_back(i);
cout<< "c5.push_back(i = "<< i<< "): "<< c5; // output is show in the text box6
}
cout<< "using Iterator"<< endl; // output is show in the text box 7
ListI::Iterator itr = c5.begin();
ListI::Iterator itrb = c5.begin();
ListI::Iterator itre = c5.end();
if(itr == itrb) cout<< "itr == itrb"<< endl;
else cout<< "itr != itrb"<< endl;
if(itr != itrb) cout<< "itr != itrb"<< endl;
else cout<< "itr == itrb"<< endl;
ListI::Iterator it;
for(it = c5.begin(); it != c5.end(); ++it){
cout<< *it<< ' '; // output is show in the text box 7
}
// output is show in the text box 8
cout<< "ListI::Iterator itr2 = c5.begin(), ++, ++ "<< endl;
cout<< "c5.insert(itr2, 5, 33) "<< endl;
ListI::Iterator itr2 = c5.begin();
itr2++; itr2++;
c5.insert(itr2, 5, 33);
cout<< c5;
return 0;
}