CSCI 330 Lab: Linked List

Complete the implementation of the mylist, mylink and mylist_iterator template classes as defined below, so that they run correctly with the test code test_mylist.cpp.

Note: page 207 of the textbook shows inline implementations of the pre-increment and pre-decrement operations. However, it mistakenly shows these within the bodies of the post-increment and post-decrement operators.

#ifndef MY_LIST_H
#define MY_LIST_H

// my_list.h  - a doubly-linked list

#include <algorithm>
using namespace std;

// forward declaration of classes defined in this header
template <class T> class my_list;
template <class T> class my_link;
template <class T> class my_list_iterator;

template <class T> 
class my_list
{
public:
   typedef T value_type;
   typedef my_list_iterator<T> iterator;

   // constructors
   my_list();  // no-arg constructor 
   my_list(const my_list & l); // copy constructor

   ~my_list(); // destructor

   // operations
   bool empty() const;
   int size() const;
   T & back() const;
   T & front() const;
   void push_front(const T & x);
   void push_back(const T & x);
   void pop_front();
   void pop_back();
   iterator begin() const;
   iterator end() const;
   void insert(iterator pos, const T & x); // insert x before pos
   void erase(iterator pos);

protected:
   my_link<T> * first_link;
   my_link<T> * last_link;
   unsigned int my_size;
};

template <class T> 
class my_link 
{
private:
   my_link(const T & x);

   T x;
   my_link<T> * next_link;
   my_link<T> * prev_link;

   friend class my_list<T>;
   friend class my_list_iterator<T>;
};

template <class T> class my_list_iterator 
{
public:
   typedef my_list_iterator<T> iterator;

   // constructor
   my_list_iterator(my_link<T> * current_link); 

   // operators
   T & operator*();  // dereferencing operator
   void operator=(const iterator & rhs); 
   bool operator==(const iterator & rhs) const;
   bool operator!=(const iterator & rhs) const;
   iterator & operator++();  // pre-increment, ex. ++it
   iterator operator++(int); // post-increment, ex. it++
   iterator & operator--();  // pre-decrement
   iterator operator--(int); // post-decrement

protected:
   my_link<T> * current_link;
   friend class my_list<T>;
};

#endif

// test_my_list.cpp

#include <iostream>
#include <list>
#include <string>
#include <cassert>
#include "my_list.h"

using namespace std;

int main(char* args[])
{
   #define LIST my_list
   //#define LIST list

   LIST<int> l;

   assert(l.size() == 0);
   assert(l.empty());

   l.push_front(44);  // list = 44
   assert(!l.empty());
   assert(l.front() == 44);
   assert(l.back() == 44);

   l.push_front(33);  // list = 33, 44
   assert(l.size() == 2);
   assert(l.front() == 33);
   assert(l.back() == 44);

   l.push_front(22);  // list = 22, 33, 44
   LIST<int>::iterator it = l.begin();
   l.insert(it, 11);  // list = 11, 22, 33, 44
   it = l.begin();
   assert(l.front() == 11);
   assert(*it == 11);
   assert(*++it == 22);
   assert(*++it == 33);
   assert(*++it == 44);

   it = l.begin();
   ++it;
   ++it;
   ++it;
   l.insert(it, 38);  // list = 11, 22, 33, 38, 44
   LIST<int>::iterator it2 = l.begin();
   assert(*it2 == 11);
   assert(*++it2 == 22);
   assert(*++it2 == 33);
   assert(*++it2 == 38);
   assert(*++it2 == 44);

   l.pop_front();  // list = 22, 33, 38, 44
   it2 = l.begin();
   assert(*it2 == 22);
   assert(*++it2 == 33);
   assert(*++it2 == 38);
   assert(*++it2 == 44);

   l.pop_back(); //list = 22, 33, 38
   LIST<int> copy = l; //copy = 22, 33, 38
   assert(copy.size() == 3);
   LIST<int>::iterator it3 = copy.begin();
   assert(*it3 == 22);
   assert(*++it3 == 33);
	
   copy.erase(it3); //copy = 22, 38
   assert(copy.size() == 2);
   it3 = copy.begin();
   assert(*it3 == 22);
   assert(*++it3 == 38);

   cout << "All tests passed.\n";
   cin.get();
}