This is using C++ implementation of the Linked List Complete the implementation

Question

This is using C++

implementation of the Linked List

Complete the implementation of the my_list template class as defined in “my_list.h” so that it runs correctly with the test code test_list.cpp (provided at the end of this page, and in the repository as well). Initially, you can just write stubs for the list methods that correspond to the iterator structure, and stubs for the iterator functions.

Implementation of the iterator

Implement the iterator class for the linked list structure to provide an iterator with the capability to move forward and backward through the list. You will also need to implement the test for (in-)equality, assignment and de-reference operators. The driver program for this is “test_list_iterators.cpp”

Using the code given in my repository, implement the list and iterator class in a separate file called “my_list.cpp”. Provided are two test files, test_list.cpp and test_list_iterators.cpp, both of which validate the functionality of your list, both with and without iterators.

You will know you are done when test_list_iterators.cpp compiles and runs with no errors or failed assertions.

Skeleton Code

Listing 1: List Header File

Listing: my_list.h

#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>;
};


#include "my_list.cpp"

#endif

Listing 2: Test Driver (no iterators)

Listing: test_list.cpp

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

using namespace std;

int main(int argc, char* argv[])
{
#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


l.pop_back(); //list = 22, 33
assert(l.back() == 33);
l.pop_front(); //list = 33
assert(l.front() == 33);
assert(l.front() == l.back());

cout << "All non-iterator tests passed. ";
cin.get();
}
Listing 3: Test Drive (with iterators)

Listing: test_list_iterators.cpp

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

using namespace std;

int main(int argc, char* argv[])
{
#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. ";
cin.get();
}

Explanation / Answer

Try this way 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 using namespace std; // forward declaration of classes defined in this header template class my_list; template class my_link; template class my_list_iterator; template class my_list { public: typedef T value_type; typedef my_list_iterator 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 * first_link; my_link * last_link; unsigned int my_size; }; template class my_link { private: my_link(const T & x); T x; my_link * next_link; my_link * prev_link; friend class my_list; friend class my_list_iterator; }; template class my_list_iterator { public: typedef my_list_iterator iterator; // constructor my_list_iterator(my_link * 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 * current_link; friend class my_list; }; #endif // test_my_list.cpp #include #include #include #include #include "my_list.h" using namespace std; int main(char* args[]) { #define LIST my_list //#define LIST list LIST 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::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::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 copy = l; //copy = 22, 33, 38 assert(copy.size() == 3); LIST::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

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.