Write a deep copy constructor for the linked list below. Use the following test

Question

Write a deep copy constructor for the linked list below. Use the following test program to test the deep copy constructor. ( I apologize in advace for making it so long. I am unable to upload the files.)

/* The test file, header file and class declarations are three seperate files, but they will be added together here*/

//Header File:

#ifndef LIST_H
#define LIST_H

#include <string>

using namespace std;

class List;
class Iterator;

class Node
{
public:
/**
Constructs a node with a given data value.
@param element the data to store in this node
*/
Node(string element);
private:
string data;
Node* previous;
Node* next;
friend class List;
friend class Iterator;
};

class List
{
public:
/**
Constructs an empty list.
*/
List();
/**
Appends an element to the list.
@param element the value to append
*/
List(const List& l);

void push_back(string element);
/**
Inserts an element into the list.
@param iter the position before which to insert
@param element the value to insert
*/
void insert(Iterator iter, string element);
/**
Removes an element from the list.
@param iter the position to remove
@return an iterator pointing to the element after the
erased element
*/
Iterator erase(Iterator iter);
/**
Gets the beginning position of the list.
@return an iterator pointing to the beginning of the list
*/
Iterator begin();
/**
Gets the past-the-end position of the list.
@return an iterator pointing past the end of the list
*/
Iterator end();
private:
Node* first;
Node* last;
friend class Iterator;
};

class Iterator
{
public:
/**
Constructs an iterator that does not point into any list.
*/
Iterator();
/**
Looks up the value at a position.
@return the value of the node to which the iterator points
*/
string get() const;
/**
Advances the iterator to the next node.
*/
void next();
/**
Moves the iterator to the previous node.
*/
void previous();
/**
Compares two iterators.
@param other the iterator to compare with this iterator
@return true if this iterator and other are equal
*/
bool equals(Iterator other) const;
private:
Node* position;
List* container;
friend class List;
};

#endif

/***************************************************************End of Header *******************************************************/

//Classes:

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

using namespace std;

Node::Node(string element)
{
data = element;
previous = nullptr;
next = nullptr;
}

List::List()
{
first = nullptr;
last = nullptr;
}

void List::push_back(string element)
{
Node* new_node = new Node(element);
if (last == nullptr) // List is empty
{
first = new_node;
last = new_node;
}
else
{
new_node->previous = last;
last->next = new_node;
last = new_node;
}
}

void List::insert(Iterator iter, string element)
{
if (iter.position == nullptr)
{
push_back(element);
return;
}

Node* after = iter.position;
Node* before = after->previous;
Node* new_node = new Node(element);
new_node->previous = before;
new_node->next = after;
after->previous = new_node;
if (before == nullptr) // Insert at beginning
{
first = new_node;
}
else
{
before->next = new_node;
}
}

Iterator List::erase(Iterator iter)
{
Node* remove = iter.position;
Node* before = remove->previous;
Node* after = remove->next;
if (remove == first)
{
first = after;
}
else
{
before->next = after;
}
if (remove == last)
{
last = before;
}
else
{
after->previous = before;
}
delete remove;
Iterator r;
r.position = after;
r.container = this;
return r;
}

Iterator List::begin()
{
Iterator iter;
iter.position = first;
iter.container = this;
return iter;
}

Iterator List::end()
{
Iterator iter;
iter.position = nullptr;
iter.container = this;
return iter;
}

Iterator::Iterator()
{
position = nullptr;
container = nullptr;
}

string Iterator::get() const
{
return position->data;
}

void Iterator::next()
{
position = position->next;
}

void Iterator::previous()
{
if (position == nullptr)
{
position = container->last;
}
else
{
position = position->previous;
}
}

bool Iterator::equals(Iterator other) const
{
return position == other.position;
}

/* ******************************************************* End of Classes*********************************************************************************************************** */

//Test File:

#include <string>
#include <iostream>
#include "list.h"
using namespace std;

int main()
{
List names;

names.push_back("Tom");
names.push_back("Diana");
names.push_back("Harry");
names.push_back("Juliet");

// Add a value in fourth place

Iterator pos = names.begin();
pos.next();
pos.next();
pos.next();

names.insert(pos, "Romeo");

// Remove the value in second place

pos = names.begin();
pos.next();

names.erase(pos);

// Print all values

for (pos = names.begin(); !pos.equals(names.end()); pos.next())
{
cout << pos.get() << endl;
}
cout << endl;
List names_copy(names); //Copy constructor
names_copy.push_back("Shakespeare");
// Verify that Shakespeare was inserted.
cout << "Printing new list" << endl;
for (pos = names_copy.begin(); !pos.equals(names.end()); pos.next())
{
cout << pos.get() << endl; //
}
cout << "Printing original list " << endl;
for (pos = names.begin(); !pos.equals(names.end()); pos.next())
{
cout << pos.get() << endl;
}

return 0;
}

Explanation / Answer

//main.cpp
#include <string>
#include <iostream>
#include "list.h"

using namespace std;

int main()
{
   List names;

   names.push_back("Tom");
   names.push_back("Diana");
   names.push_back("Harry");
   names.push_back("Juliet");

   // Add a value in fourth place

   Iterator pos = names.begin();
   pos.next();
   pos.next();
   pos.next();

   names.insert(pos, "Romeo");

   // Remove the value in second place

   pos = names.begin();
   pos.next();

   names.erase(pos);

   // Print all values

   for (pos = names.begin(); !pos.equals(names.end()); pos.next())
   {
      cout << pos.get() << endl;
   }

   return 0;
}

--------------------------------------------------------------------------------------------------
//List.cpp
#include <string>
#include "list.h"

using namespace std;

Node::Node(string element)
{
   data = element;
   previous = nullptr;
   next = nullptr;
}

List::List()
{
   first = nullptr;
   last = nullptr;
}

List::List(List& other) { // cant name const parameter cause its not a const function
   // https://github.com/aryan-gupta/DataStructures/blob/develop/DList.h
  
   // @todo check if other is not empty
  
   Iterator pos = other.begin(), end = other.end();
  
   last = first = new Node(pos.get()); // restrictions
   pos.next();
  
   for (; !pos.equals(end); pos.next()) {
       last->next = new Node(pos.get()); // forward link
       last->next->previous = last; // back link
       last = last->next; // move last forward for next iteration
   }
}

void List::push_back(string element)
{
   Node* new_node = new Node(element);
   if (last == nullptr) // List is empty
   {
      first = new_node;
      last = new_node;
   }
   else
   {
      new_node->previous = last;
      last->next = new_node;
      last = new_node;
   }
}

void List::insert(Iterator iter, string element)
{
   if (iter.position == nullptr)
   {
      push_back(element);
      return;
   }

   Node* after = iter.position;
   Node* before = after->previous;
   Node* new_node = new Node(element);
   new_node->previous = before;
   new_node->next = after;
   after->previous = new_node;
   if (before == nullptr) // Insert at beginning
   {
      first = new_node;
   }
   else
   {
      before->next = new_node;
   }
}

Iterator List::erase(Iterator iter)
{
   Node* remove = iter.position;
   Node* before = remove->previous;
   Node* after = remove->next;
   if (remove == first)
   {
      first = after;
   }
   else
   {
      before->next = after;
   }
   if (remove == last)
   {
      last = before;
   }
   else
   {
      after->previous = before;
   }
   delete remove;
   Iterator r;
   r.position = after;
   r.container = this;
   return r;
}

Iterator List::begin()
{
   Iterator iter;
   iter.position = first;
   iter.container = this;
   return iter;
}

Iterator List::end()
{
   Iterator iter;
   iter.position = nullptr;
   iter.container = this;
   return iter;
}

Iterator::Iterator()
{
   position = nullptr;
   container = nullptr;
}

string Iterator::get() const
{
   return position->data;
}

void Iterator::next()
{
   position = position->next;
}

void Iterator::previous()
{
   if (position == nullptr)
   {
      position = container->last;
   }
   else
   {
      position = position->previous;
   }
}

bool Iterator::equals(Iterator other) const
{
   return position == other.position;
}

------------------------------------------------------------------------
//List.h
#ifndef LIST_H
#define LIST_H

#include <string>

using namespace std;

class List;
class Iterator;

class Node
{
public:
   //Constructs a node with a given data value.

   Node(string element);
private:
   string data;
   Node* previous;
   Node* next;
friend class List;
friend class Iterator;
};

class List
{
public:
   //Constructs an empty list.

   List();

   List(List& other);
   //Appends an element to the list.
  
   void push_back(string element);
   //Inserts an element into the list.

   void insert(Iterator iter, string element);
   //Removes an element from the list.

   Iterator erase(Iterator iter);
   //Gets the beginning position of the list.

   Iterator begin();
   //Gets the past-the-end position of the list.

   Iterator end();
private:
   Node* first;
   Node* last;
friend class Iterator;
};

class Iterator
{
public:
   //Constructs an iterator that does not point into any list.

   Iterator();
   //Looks up the value at a position.
  
   string get() const;
   //Advances the iterator to the next node.

   void next();
   //Moves the iterator to the previous node.

   void previous();
   //Compares two iterators.

   bool equals(Iterator other) const;
private:
   Node* position;
   List* container;
friend class List;
};

#endif

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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