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

you have to study basicccccccccs c

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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