Problem Set 3: List ADT 

Review the template classs DoublyLinkedList and DoublyLinkedListIterator developed in tutorial 9. In addition, it might be beneficial to review also the lecture material  regarding the construction of an abstract data type and memory management. 

Start with the header files provided on Canvas, as they have been fully tested. 

Using the template classes DoublyLinkedList and DoublyLinkedListIterator,  implement the template class List as specified below: 

#pragma once 

#include "DoublyLinkedList.h" 

#include "DoublyLinkedListIterator.h" 

#include <stdexcept> 

template<typename T>  

class List 

{ 

private: 

 // auxiliary definition to simplify node usage 

 using Node = DoublyLinkedList<T>; 

 Node* fRoot; // the first element in the list 

 size_t fCount; // number of elements in the list 

public: 

 // auxiliary definition to simplify iterator usage 

 using Iterator = DoublyLinkedListIterator<T>;   

 List(); // default constructor  List( const List& aOtherList ); // copy constructor  List& operator=( const List& aOtherList ); // assignment operator  ~List(); // destructor - frees all nodes   

 bool isEmpty() const; // Is list empty?  size_t size() const; // list size 

 void push_front( const T& aElement ); // adds aElement at front  void push_back( const T& aElement ); // adds aElement at back  void remove( const T& aElement ); // remove first match from list 

 const T& operator[]( size_t aIndex ) const; // list indexer 

 Iterator begin() const; // return a forward iterator  Iterator end() const; // return a forward end iterator  Iterator rbegin() const; // return a backwards iterator  Iterator rend() const; // return a backwards end iterator 

 // move features 

 List( List&& aOtherList ); // move constructor  List& operator=( List&& aOtherList ); // move assignment operator  void push_front( T&& aElement ); // adds aElement at front  void push_back( T&& aElement ); // adds aElement at back }; 

The template class List defines an “object adapter” for DoublyLinkedList objects (i.e.,  the list representation). Somebody else has already started with the implementation, but left  the project unfinished. You find a header file for the incomplete List class on Canvas. This  header file contains the specification of the template class List and the implementations for  the destructor ~List() and the remove() method. You need to implement the remaining  member functions.

Problem 1 

Implement the default constructor List(), and the methods push_front(), size(), empty(), as well as all iterator auxiliary methods first. 

To make List work, we have to allocate list node elements on the heap using new. In doing  so, you obtain a pointer to a Node object. The DoublyLinkList member functions,  however, generally only accept references to Node objects. In order to satisfy this  requirement, you need to deference the Node object pointer which gives you the Node object  located in heap memory. This Node object is passed by reference (to a heap memory location)  to the corresponding DoublyLinkList member function (i.e., push_front()). 

You can use #define P1 in Main.cpp to enable the corresponding test driver. 

void testP1() 

{ 

 using StringList = List<string>;   

 string s1( "AAAA" ); 

 string s2( "BBBB" ); 

 string s3( "CCCC" ); 

 string s4( "DDDD" ); 

 cout << "Test of problem 1:" << endl; 

 StringList lList; 

 if ( !lList.empty() ) 

 { 

 cerr << "Error: Newly created list is not empty." << endl; 

 }   

 lList.push_front( s4 ); 

lList.push_front( s3 ); 

 lList.push_front( s2 ); 

 lList.push_front( s1 ); 

 // iterate from the top 

 cout << "Top to bottom " << lList.size() << " elements:" << endl; 

 for ( const string& element : lList ) 

 { 

 cout << element << endl; 

 } 

 // iterate from the end 

 cout << "Bottom to top " << lList.size() << " elements:" << endl; 

 for ( StringList::Iterator iter = lList.rbegin(); iter != iter.rend(); iter-- )  { 

 cout << *iter << endl; 

 } 

 cout << "Completed" << endl; 

} 

The result should look like this. No errors should occur: 

Test of problem 1: 

Top to bottom 4 elements: 

AAAA 

BBBB 

CCCC 

DDDD 

Bottom to top 4 elements: 

DDDD 

CCCC 

BBBB 

AAAA

Completed

problemset-3