Summary

Implement a template for a doubly linked list called DList along with iterators to access the list. In your implementation, you can choose to use sentinel nodes or not use sentinel nodes. That is entirely up to you.

Nodes in this list will have a pointer not only to the next node but also a pointer to the previous node.

The DList class has the following member functions. Each function must meet the big-O runtime specified. Unless otherwise stated n refers to number of nodes within the linked list.:

DList(); 

constructor, creates empty DList

O(1)

iterator begin(); 

returns iterator to Node containing the first piece of data in the linked list

O(1)

iterator end(); 

returns iterator to the Node after the node containing the last piece of data of the linked list

O(1)

const_iterator begin() const; 

returns const_iterator to to Node containing the first piece of data in the linked list

O(1)

const_iterator end() const; 

returns const_iterator to the Node after the node containing the last piece of data of the linked list

O(1)

void push_front(const T& data); 

adds a node containing data to the front of the linked list

O(1)

void push_back(const T& data); 

adds a node containing data to the back of the linked list

O(1)

void pop_front(); 

removes the first node from the linked list

O(1)

void pop_back(); 

removes the last node from the linked list

O(1)

iterator insert(const T& data,iterator it); 

adds a node containing data to the linked list such that the new node goes before the node referred to by it

Note that it is allowed to be equivalent to end().

returns iterator to newly added node

O(1)

iterator erase(iterator it); 

removes the node referred to by it

returns iterator to node after the node removed

O(1)

iterator erase(iterator first, iterator last); 

removes the nodes between the nodes referred to by iterator first to last. This includes the node referred to by first but NOT the node referred to by last.

returns iterator to last

O(n) where n is the number of nodes between first and last

iterator search(const T& data); const_iterator search(const T& data) const; 

returns iterator to the node containing data. If data is not found, returns end()

O(n)

bool empty() const; 

function returns true if the list is empty, false otherwise

O(1)

int size() const; 

function returns number of pieces of data stored in the list

O(1)

~DList(); DList(const DList&); DList& operator=(const DList&); DList(DList&&); DList& operator=(DList&&); 

Your linked list must also implement destructor, copy constructor, assignment operator, move constructor, move operator.

runtime for destructor, copy constructor and assignment operator must not exceed O(n)

runtime for move constructor/operator must not exceed O(1)

Iterator

The idea of an iterator is to provide a means to traverse your class. In the STL, different classes like vectors or list all have iterators that help you iterate through your list. For the linked list, you will also write an iterator class.

You will need two iterators. a const_iterator and an iterator which is derived from const_iterator. For both operators, the following public members/operators are needed. You are welcome to add any other private or protected members as you see fit:

iterator(); const_iterator(); 

constructors, returns iterators to nullptrs O(1)

iterator operator++(); const_iterator operator++() const; iterator operator++(int); const_iterator operator++(int); 

prefix and postfix ++ operator

makes iterator point to the next node in the list.

return as appropriate for each operator

O(1)

iterator operator--(); const_iterator operator--() const; iterator operator--(int); const_iterator operator--(int); 

prefix and postfix operator --

increments iterator so that it points to previous node in list

return as appropriate for each operator

O(1)

operator== 

returns true if two iterators point at the same node, false otherwise

operator != 

returns true if two iterators point at different nodes, false otherwise

O(1)

const T& operator*()const; (in both iterator and const_iterator) T& operator*(); (only in iterator) 

dereferencing operator, returns the data in the node pointed to by iterator

O(1)

-------------------------------------------------------------------------------------------------------

MY CODE:

template

class DList{ struct Node{

T data_; Node* next_; Node* prev_;

Node(const T& data=T{},Node* nx=nullptr,Node* pr=nullptr){

data_ = data; next_ = nx; prev_ = pr; } };

Node* front_; Node* back_;

public: class const_iterator{ friend class DList;

protected:

Node* curr_; const_iterator(Node* n){ curr_=n; }

public: const_iterator(){ curr_= nullptr; }

const_iterator operator++(){ if(curr_){ curr_=curr_->next_; } return *this; }

const_iterator operator++(int){ const_iterator old=*this; if(curr_){ curr_=curr_->next_; } return old; }

const_iterator operator--(){ if(curr_){ curr_=curr_->prev_; } return *this; }

const_iterator operator--(int){ const_iterator old=*this; if(curr_){ curr_=curr_->prev_; } return old; }

bool operator==(const_iterator rhs){ return curr_==rhs.curr_; } bool operator!=(const_iterator rhs){ return curr_!=rhs.curr_; } const T& operator*()const{ return curr_->data_; } }; class iterator:public const_iterator{ friend class DList; iterator(Node* n):const_iterator(n){} public: iterator(){} iterator operator++(){ if(this->curr_){ this->curr_=this->curr_->next_; } return *this; } iterator operator++(int){ iterator old=*this; if(this->curr_){ this->curr_=this->curr_->next_; } return old; } iterator operator--(){ if(this->curr_){ this->curr_=this->curr_->prev_; } return *this; } iterator operator--(int){ iterator old=*this; if(this->curr_){ this->curr_=this->curr_->prev_; } return old; } T& operator*(){ return this->curr_->data_; } const T& operator*()const{ return this->curr_->data_; } }; DList(); ~DList(); DList(const DList& rhs); DList& operator=(const DList& rhs); DList(DList&& rhs); DList& operator=(DList&& rhs); iterator begin(){ return iterator(front_);} iterator end(){ return iterator(nullptr);} const_iterator begin() const{ return iterator(front_);} const_iterator end() const{ return iterator(nullptr);} void push_front(const T& data); void push_back(const T& data); void pop_front(); void pop_back(); iterator insert(const T& data, iterator it); iterator search(const T& data); const_iterator search(const T& data) const; iterator erase(iterator it); iterator erase(iterator first, iterator last); bool empty() const; int size() const;

private: Node* back_; Node* front_; friend class DList;

};

template DList::DList(){

front_= nullptr; back_ = nullptr; } template DList::~DList(){

Node* curr=front_; while(curr != back_){ front_ = front_->next_; delete curr; curr = front_; }

} template DList::DList(const DList& rhs){

const Node* curr = rhs.front_; Node* temp = nullptr;

if (curr != back_) { front_ = new Node(curr->data_); temp = front_; curr = curr->next_; } while(curr != back_) { Node* nn = new Node(curr->data_); temp->next_ = nn; temp = temp->next_; curr = curr->next_; }

} template DList& DList::operator=(const DList& rhs){

} template DList::DList(DList&& rhs){

}

template DList& DList::operator=(DList&& rhs){

}

template void DList::push_front(const T& data){

Node* nn=new Node(data,front_,nullptr); if(front_!=nullptr){ //make front's prev point to new node front_->prev_ = nn; } else{

back_=nn; } //make front point to new node front_=nn; } template void DList::push_back(const T& data){

Node* newN = new Node(data, nullptr, back_); if( back_ != nullptr){ back_->next_ = newN; } else{ front_ = newN; } back_ = newN; } } template void DList::pop_front(){

if(front_ != nullptr){ Node* rm = front_; if(front_!=back_){ //make sure we have more than one node front_=front_->next_; //front_=rm->next_; front_->prev_=nullptr; } else{ front_=back_=nullptr; } delete rm; } } template void DList::pop_back(){

if(back_ != nullptr){ Node* temp = back_; if(front_!=back_){ back_->prev_->next_ = nullptr; back_ = back_->prev_; //std::cout << "new back data: " << back_->data_; } else{ front_ = back_ = nullptr; } delete temp; }

}

template typename DList::iterator DList::insert(const T& data, iterator it){

}

template typename DList::iterator DList::search(const T& data){

}

template typename DList::const_iterator DList::search(const T& data) const{

}

template typename DList::iterator DList::erase(iterator it){

}

template typename DList::iterator DList::erase(iterator first, iterator last){

} template bool DList::empty() const{

return front_->next_ == nullptr; } template int DList::size() const{

}

-------------------------------------------------------------

MAIN TESTER

#include "a1q1start.h" #include #include #include using namespace std; //change the #define VERBOSE to 1 for a bit more error information #define VERBOSE 0

struct Record{ char word_[30]; int count_; }; ostream& operator<<(ostream& os, const Record rec){ os << rec.word_; return os; } bool operator==(const Record& a,const Record& b){ bool rc=false; if(strcmp(a.word_,b.word_)==0 && a.count_==b.count_){ rc=true; } return rc; } bool operator!=(const Record& a,const Record& b){ return !(a==b); } bool operator <(const Record& a, const Record& b){ bool rc=false; if(strcmp(a.word_,b.word_) < 0){ rc=true; } return rc; }

template void removeItem(T arr[],int idx,int sz); template bool checkList(const DList& list,const T arr2[],int sz); template void duplicateArray(T dest[], const T src[],int sz); template void printLists(const DList& list,const T array[],int sz); template typename DList::iterator setIterator(DList& list, int idx); template void addFront(const T& data,T arr[],int sz); template void addBack(const T& data,T arr[],int sz); template void add(const T& data,int idx, T arr[],int sz);

int main(void){ const int cap=10000; const int numSearches=200; Record data[20]={ {"the",1}, {"quick",2}, {"brown ",3}, {"fox",4}, {"jumped",5}, {"over",6}, {"lazy",7}, {"dog",8}, {"Calvin",9}, {"and",10}, {"Hobbes",11}, {"night",12}, {"watch",13}, {"captain",14}, {"carrot",15}, {"lilac",16}, {"lavender",17}, {"lily",18}, {"coffee",19}, {"tea",20} }; int intData[cap];

//these array will mirror what happens to LL Record mirror[20]; int intMirror[cap]; for(int i=0;i

DList recList; DList intList;

bool passtest=true; int numPassed=0;

/* Test constructors, begin and end functions*/ cout << "test 1: create list empty list, check begin() and end()" << endl; if((recList.begin() != recList.end()) || (intList.begin() != intList.end())){ cout << "error 1: check your constructor, begin() and end() functions" << endl; passtest=false; } else{ numPassed++; }

if(passtest){ for(int i=0;i<5;i++){ addFront(data[i],mirror,i); recList.push_front(data[i]); } for(int i=5;i<10;i++){ addBack(data[i],mirror,i); recList.push_back(data[i]); } DList::iterator it=recList.begin(); for(int i=0;i<5;i++){ it++; } for(int i=10;i<20;i++){ it=recList.insert(data[i],it); add(data[i],5,mirror,i); } DList::iterator it2=intList.begin(); for(int i=0;i0 && passtest;i--){ if(mirror[i] != *(it--)){ passtest=false; cout << "Error 3b: postfix -- operator is not returning iterator to correct node" << endl; } } for(int i=0;i<19 && passtest;i++){ if(*(++it) != mirror[i+1]){ passtest=false; cout << "Error 3c: prefix ++ operator is not returning iterator to correct node" << endl; } } for(int i=19;i>0 && passtest;i--){ if(*(--it) != mirror[i-1]){ passtest=false; cout << "Error 3d: prefix -- operator is not returning iterator to correct node" << endl; } } }

DList recCopy=recList; DList intCopy=intList; DList recCopy2=recCopy; DList intCopy2=intCopy; duplicateArray(data,mirror,20); duplicateArray(intData,intMirror,cap);

if(passtest){ numPassed++; cout << "test 4: create a duplicate of the lists with copy constructor, ensure they match" << endl; if(!checkList(recList,mirror,20)){ passtest=false; cout << "Error 4a: Bug in copy constructor" << endl; } if(!checkList(intList,intMirror,cap)){ passtest=false; cout << "Error 4b: Bug in copy constructor" << endl; } } if(passtest){ numPassed++; cout << "test 5: test search() function" << endl; for(int i=0;i<20;i++){ DList::iterator it = recList.search(mirror[i]); if(it == recList.end() || *it != mirror[i]){ passtest=false; cout << "Error 5a: Bug in search, iterator returned does not point at correct node" << endl; } } for(int i=0;i::const_iterator it = intList.search(intMirror[pick]); if(it == intList.end() || *it != intMirror[pick]){ passtest=false; cout << "Error 5b: Bug in search, iterator returned does not point at correct node" << endl; } } }

if(passtest){ numPassed++; cout << "test 6: test erase function" << endl; DList::iterator it; it=setIterator(recList,19); recList.erase(it); removeItem(mirror,19,20); if(!checkList(recList,mirror,19)){ passtest=false; cout << "Error 6a: Bug in erase. erased last item" << endl; #if VERBOSE >= 1 printLists(recList,mirror,19); #endif } recList.erase(recList.begin()); removeItem(mirror,0,19); if(!checkList(recList,mirror,18)){ passtest=false; cout << "Error 6b: Bug in remove. erased first item" << endl; #if VERBOSE >= 1 printLists(recList,mirror,18); #endif } for(int i=0;i<3 && passtest;i++){ int pick=rand()%(18-i); it=setIterator(recList,pick); recList.erase(it); removeItem(mirror,pick,18-i); if(!checkList(recList,mirror,18-i-1)){ passtest=false; cout << "Error 6c: Bug in erase." << endl; } } intList.erase(intList.begin()); removeItem(intMirror,0,cap); if(!checkList(intList,intMirror,cap-1)){ passtest=false; cout << "Error 6d: Bug in erase, removed first" << endl; } intList.erase(intList.begin()); removeItem(intMirror,0,cap-1); if(!checkList(intList,intMirror,cap-2)){ passtest=false; cout << "Error 6e: Bug in erase. removed first again" << endl; } DList::iterator it2; it2=setIterator(intList,cap-3); intList.erase(it2); removeItem(intMirror,cap-3,cap-2); if(!checkList(intList,intMirror,cap-3)){ passtest=false; cout << "Error 6f: Bug in erase.removed last" << endl; } it2=setIterator(intList,cap-4); intList.erase(it2); removeItem(intMirror,cap-4,cap-3); if(!checkList(intList,intMirror,cap-4)){ passtest=false; cout << "Error 6g: Bug in erase. removed last again" << endl; } for(int i=0;i<100 && passtest;i++){ int pick=rand()%(cap-4-i); it2=setIterator(intList,pick); intList.erase(it2); removeItem(intMirror,pick,cap-4-i); if(!checkList(intList,intMirror,cap-i-5)){ passtest=false; cout << "Error 6h: Bug in erase." << endl; } } } if(passtest){ numPassed++; cout << "test 7: ensure that copied list were not altered (proper deep copy was made) " << endl; if(!checkList(recCopy,data,20)){ passtest=false; cout << "Error 7a: Bug in copy constructor, deep copy not made?" << endl; #if VERBOSE >= 1 printLists(recCopy,data,20); #endif } if(!checkList(intCopy,intData,cap)){ passtest=false; cout << "Error 7b: Bug in copy constructor, deep copy not made?" << endl; #if VERBOSE >= 2 printLists(intCopy,intData,cap); #endif } } if(passtest){ numPassed++; cout << "test 8: test assignment operator" << endl; recCopy2 = recList; intCopy2 = intList; if(!checkList(recCopy2,mirror,15)){ passtest=false; cout << "Error 8a: Bug in assignment operator" << endl; #if VERBOSE >= 1 printLists(recCopy2,mirror,15); #endif } if(!checkList(intCopy2, intMirror,cap-104)){ passtest=false; cout << "Error 8b: Bug in assignment operator" << endl; #if VERBOSE >= 2 printLists(intCopy2,intMirror,cap-104); #endif } }

if(passtest){

numPassed++;

cout << "test 9: test assignment operator (deep copy)" << endl; recCopy2.erase(recCopy2.begin()); intCopy2.erase(intCopy2.begin()); if(!checkList(recList,mirror,15)|| recList.empty() || recList.size()!=15){ passtest=false; cout << "Error 9a: Bug in = operator, no deepcopy?" << endl; } if(!checkList(intList,intMirror,cap-104)|| intList.empty() || intList.size()!=cap-104){ passtest=false; cout << "Error 9b: Bug in = operator,no deep copy?" << endl; } }

if(passtest){ numPassed++; cout << "test 10: search for removed items" << endl; int pick[2]={0,19}; for(int i=0;i<2;i++){ auto it =recList.search(data[pick[i]]); if(it!=recList.end()){ cout << "Error 10a: Bug in search, returned iterator is not correct" << endl; passtest=false; } }

} if(passtest){ int pick[4]={0,1,cap-1,cap-2}; for(int i=0;i<4;i++){ auto it = intList.search(intData[pick[i]]); if(it != intList.end()){

passtest=false; cout << "Error 10b: Bug in search."<< endl; } } } if(passtest){ numPassed++; cout << "test 11: test erase(front,back) function" << endl; DList::iterator it; DList::iterator it2; Record tmp[20]; duplicateArray(tmp,mirror,15); removeItem(tmp,0,15); it=setIterator(recCopy2,2); it2=setIterator(recCopy2,5);

recCopy2.erase(it,it2); removeItem(tmp,4,14); removeItem(tmp,3,13); removeItem(tmp,2,12); if(!checkList(recCopy2,tmp,11)){ passtest=false; cout << "Error 11a: Bug erase(it) function" << endl; #if VERBOSE >= 1 printLists(recCopy2,tmp,11); #endif } if(!checkList(recList,mirror,15)){ passtest=false; cout << "Error 11b: assignment operator, (deep copy not made?)" << endl; #if VERBOSE >= 1 printLists(recList,mirror,15); #endif

} } if(passtest){ numPassed++; cout << "test 12: test erase(it,end()) function" << endl; DList::iterator it; DList::iterator it2; Record tmp[20]; recCopy2=recList; intCopy2=intList; duplicateArray(tmp,mirror,15); it=setIterator(recCopy2,11);

recCopy2.erase(it,recCopy2.end()); removeItem(tmp,14,15); removeItem(tmp,13,14); removeItem(tmp,12,13); removeItem(tmp,11,12); if(!checkList(recCopy2,tmp,11)){ passtest=false; cout << "Error 12a: Bug erase(first,last) function" << endl; #if VERBOSE >= 1 printLists(recCopy2,tmp,11); #endif } if(!checkList(recList,mirror,15)){ passtest=false; cout << "Error 12b: assignment operator, (deep copy not made?)" << endl; #if VERBOSE >= 1 printLists(recList,mirror,15); #endif

} } DList recCopy3=std::move(recList); if(passtest){ numPassed++; cout << "test 13: test move constructor" << endl;

if(!checkList(recCopy3,mirror,15)){ passtest=false; cout << "Error 13a: Bug in move constructor" << endl; #if VERBOSE >= 1 printLists(recCopy3,mirror,15); #endif } if(recList.begin() == recCopy3.begin()){ passtest=false; cout << "Error 13b: Bug in move constructor" << endl; cout << "original and copy both refer to same list" << endl; } }

if(passtest){ numPassed++; recList=recCopy3; cout << "test 14: test move assignment operator" << endl; recCopy3=std::move(recList); if(!checkList(recCopy3,mirror,15)){ passtest=false; cout << "Error 14a: Bug in move assignment operator" << endl; #if VERBOSE >= 1 printLists(recCopy3,mirror,15); #endif } if(recList.begin() == recCopy3.begin()){ passtest=false; cout << "Error 14b: Bug in move assignment operator" << endl; cout << "original and copy both refer to same list" << endl; } }

if(passtest){ numPassed++; } if(numPassed == 14){ cout << "Testing for Assignment 1, part 1 completed successfully" << endl; cout << "14/14 tests passed" << endl; } else{ cout << numPassed << " / 14 tests passed. Looks like you still" << endl; cout << "have some work to do" << endl; } return 0; } template void addFront(const T& data,T arr[],int sz){ add(data,0,arr,sz); } template void addBack(const T& data,T arr[],int sz){ arr[sz]=data; } template void add(const T& data,int idx, T arr[],int sz){ for(int i=sz-1;i>=idx;i--){ arr[i+1]=arr[i]; } arr[idx]=data; } template void removeItem(T arr[],int idx,int sz){ for(int i=idx;i bool checkList(const DList& list,const T array[],int sz){ bool rc=true; auto it=list.begin(); int i; for(i=0;i

template void duplicateArray(T dest[], const T src[],int sz){ for(int i=0;i

template void printLists(const DList& list,const T array[],int sz){ auto it=list.begin(); for(int i=0;i typename DList::iterator setIterator(DList& list, int idx){ typename DList::iterator it=list.begin(); for(int i=0;i

Any help would be useful as this is also a study guide for an upcoming test,

Thank you greatly.