PART 1: Design and implement a class representing an unsorted doubly linked list
ID: 3831643 • Letter: P
Question
PART 1:
Design and implement a class representing an unsorted doubly linked list. The class must have the following requirements:
The linked list and the nodes must be implemented as a C++ templates
The list must be generic – it should not implement arithmetic/logic functions.
It must include a destructor, a copy constructor and the overloaded operator=
It must include functions to insert at the front and at the back of the list
It must include a function to return the length of the list
It must provide an iterator-based interface for the user from front to back
A front iterator pointer
Functions to reset the iterator, walk the iterator and return the info of the iterator
It must include an iterator-based interface for the user from back to front
A back iterator pointer
Functions to reset the iterator, walk the iterator and return the info of the iterator
PART 2:
The implementation of the class LargeInt will use a dynamic physical structure to store the individual digits of an integer, and will provide some basic I/O and arithmetic operations that can be performed on integers.
In particular, the class should include:
A default constructor
1)An operator function to overload the operator +
2)An operator function to overload the operator ==
3)A friend operator function to overload the operator <<
4)A friend operator function to overload the operator >>
An object of the doubly linked list class representing the large integer
An int field specifying the length of the large integer
Note 1: since the LargeInt class does not contain pointers, there is no need for a copy constructor or a destructor.
Note 2: you can assume huge integers are only positive (or 0).
Note 3: your implementation of the huge integer type must be encapsulated as a C++ class, aggregating a list object for the internal representation of the huge integer value. The huge integer type is not a list, nor does it make sense for it to be derived from a list using inheritance.
Note 4: All data members of classes must be private or protected.
Note 5: You may include the implementation of the LargeInt functions in the header file – to avoid linking problems.
Explanation / Answer
#include "ListNode.h"
#include "ListIterator.h"
namespace cs20
{
template<class T> class ListIterator;
template <class T>
class List
{
public:
typedef ListIterator<T> iterator;
typedef ListIterator<T> const_iterator;
List();
List(const List &original);
~List();
List<T> & operator = (const List<T> &original);
void append(const T &t);
bool remove(const T &t);
void clear();
bool contains(const T &t);
bool isEmpty() const;
int getSize() const;
iterator begin()
{ return iterator(head->next); }
const const_iterator cbegin() const
{ return const_iterator(head->next); }
iterator end()
{ return iterator(nullptr); }
const const_iterator cend() const
{ return const_iterator(nullptr); }
iterator back()
{ return iterator(tail==head ? tail->next : tail); }
const const_iterator cback() const
{ return const_iterator(tail == head ? tail->next : tail); }
private:
ListNode<T> *head;
ListNode<T> *tail;
ListNode<T> header;
int size;
inline void deepCopy(const List<T> &original);
inline void makeEmpty();
};
}
#include <iostream>
#include "List.h"
#include "ListNode.h"
namespace cs20
{
template<class T>
List<T>::List()
{
head = tail = &header;
header.next = NULL;
size = 0;
}
template<class T>
List<T>::List(const List &rhs)
{
deepCopy(rhs);
}
template<class T>
List<T>::~List()
{
makeEmpty();
}
template<class T>
List<T> & List<T>::operator = (const List<T> &rhs)
{
if (this == &rhs)
return *this;
makeEmpty();
deepCopy(rhs);
return *this;
}
template<class T>
void List<T>::makeEmpty()
{
node<T>* temp;
while ( listData != NULL )
{
temp = listData;
listData = listData->next;
delete temp;
}
length = 0;
}
template<class T>
inline void List<T>::deepCopy(const List<T> &rhs)
{
// *** Write this code ***
}
template<class T>
bool List<T>::isEmpty() const
{
return size == 0;
}
template<class T>
void List<T>::append(const T &t)
{
ListNode<T> *node = new ListNode<T>(t);
node->previous = tail;
tail->next = node;
node->next = NULL;
tail = node;
size++;
}
template<class T>
bool List<T>::remove(const T &t)
{
if (head->next == NULL)
return false;
ListNode<T> *current = head;
while (current->next != NULL)
{
if (current->next->value == t)
{
ListNode<T> *node = current->next;
current->next = node->next;
if (node->next != NULL)
node->next->previous = current;
delete node;
size--;
return true;
}
current = current->next;
}
return false;
}
template<class T>
void List<T>::clear()
{
makeEmpty();
head = tail = &header;
header.next = NULL;
size = 0;
}
template<class T>
bool List<T>::contains(const T &t)
{
if (head->next == NULL)
return false;
ListNode<T> *current = head->next;
while (current != NULL)
{
if (current->value == t)
return true;
current = current->next;
}
return false;
}
template<class T>
int List<T>::getSize() const
{
return size;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.