I need help writing the blank functions in this Double Linked List Header file.
ID: 3833153 • Letter: I
Question
I need help writing the blank functions in this Double Linked List Header file. The insertAhead and the insertBehind must contain a TRY CATCH
I have added the Node Header/Implementation at the bottom
//#ifdef _DOUBLE_LINKED_LIST
//#define _DOUBLE_LINKED_LIST
//#include "Node.h"
template
class DoubleLinkedList
{
public:
DoubleLinkedList();
//Initialized pointers to nullptr and the size to 0
~DoubleLinkedList();
//Deallocates all nodes
bool isEmpty() const;
//Returns true if m_size is zero, false otherwise
//Does not alter the list (hence it's const)
int size() const;
//returns the size of the list
//NOTE: Unlike Java, C++ does not allow variables and methods to have the same name. Hence, the m_ convention for the member variables.
//Does not alter the list (hence it's const)
void pushFront(T value);
//Puts the value of some type, T, in a node
//Puts that node at the front of the list
//Increase m_size by 1
void pushBack(T value);
//Puts the value of some type, T, in a node
//Puts that node at the end of the list
//Increase m_size by 1
bool removeBack();
//One element is removed from the back of the list.
//Returns true if the back element was removed, false if the list is empty.
bool removeFront();
//One element is removed from the front of the list.
//returns True if the front element was removed, false if the list is empty.
bool remove(T value);
//deletes the node containing the passed value
//This method is in charge of deleting a node to prevent memory leaks. Any memory leaks will result in loss of points
//Ensure that m_front is set to the next node in the list. If the list has exactly one node, delete it and set the front and back pointers to nullptr
//returns true if the node was removed, false otherwise
void insertAhead(T listValue, T newValue) throw (std::runtime_error);
//Assumes listValue is in the list a node is created, newValue is placed in it, and the node placed ahead of the first occurence of listValue. Also, size increased by 1.
//Example given list of ints 5, 8, 3, 9 and a new value, 11 is inserted ahead of 8 the new list will be: 5, 11, 8, 3, 9
//throws std::exception if listValue isn't in the list
void insertBehind(T listValue, T newValue) throw (std::runtime_error);
//Assumes listValue is in the list a node is created, newValue is placed in it, and the node placed ahead of the first occurrence of listValue. Also, size increased by 1.
//Example given list of ints 5, 8, 3, 9 and a new value, 11 is inserted behind 8 the new list will be: 5, 8, 11, 3, 9
//throws std::exception if listValue isn't in the list
Node* find(T value) const;
//Assumes T is comparable with ==
//returns a pointer to the first node in the list (from front to back) that contains the value or nullptr if not found
void printList() const;
//Assumes The type T is overloaded to be printable via the << operator
//If the list is empty, prints ""
//If the list is not empty, then print its content separated by spaces
//NOTE: this method is used to test other parts of your list. Make sure you pass the print tests before moving on!
void printListReverse() const;
private:
Node* m_front;
//A pointer that is that is always looking at the front (first) node
Node* m_back;
//A pointer that is that is always looking at the back (last) node
int m_size;
//The current size of the list. (e.g., if there are three nodes in the list the size is 3. If there are no nodes in the list, the size is zero)
}; // end class
template
DoubleLinkedList::DoubleLinkedList()
//Initialized pointers to nullptr and the size to 0
{
m_front= nullptr;
m_back = nullptr;
m_size = 0;
}
template
DoubleLinkedList::~DoubleLinkedList()
//Deallocates all nodes
{
}
template
bool DoubleLinkedList::isEmpty() const
//Returns true if m_size is zero, false otherwise
//Does not alter the list (hence it's const)
{
return m_size == 0;
}
template
int DoubleLinkedList::size() const
//returns the size of the list
//NOTE: Unlike Java, C++ does not allow variables and methods to have the same name. Hence, the m_ convention for the member variables.
//Does not alter the list (hence it's const)
{
return m_size;
}
template
void DoubleLinkedList::pushFront(T value)
//Puts the value of some type, T, in a node
//Puts that node at the front of the list
//Increase m_size by 1
{
Node * p = new Node;
p->setValue(value);
p->setNext(nullptr);
p->setPrevious(nullptr);
if ( isEmpty() )
{
m_front = m_back = p;
m_size++;
p = nullptr;
return;
}
// at least one node
p->setNext(m_front);
m_front->setPrevious(p);
m_front = p;
m_size++;
p = nullptr;
return;
}
template
void DoubleLinkedList::pushBack(T value)
//Puts the value of some type, T, in a node
//Puts that node at the end of the list
//Increase m_size by 1
{
Node * p = new Node;
p->setValue(value);
p->setNext(nullptr);
p->setPrevious(nullptr);
if (isEmpty())
{
m_front = m_back = p;
m_size++;
p = nullptr;
return;
}
p->setPrevious(m_back);
m_back->setNext(p);
m_back = p;
m_size++;
p = nullptr;
return;
}
template
bool DoubleLinkedList::removeBack()
//One element is removed from the back of the list.
//Returns true if the back element was removed, false if the list is empty.
{
return false; //dummy statement
}
template
bool DoubleLinkedList::removeFront()
//One element is removed from the front of the list.
//returns True if the front element was removed, false if the list is empty.
{
return false; // dummy statement
}
template
bool DoubleLinkedList::remove(T value)
//deletes the node containing the passed value
//This method is in charge of deleting a node to prevent memory leaks. Any memory leaks will result in loss of points
//Ensure that m_front is set to the next node in the list. If the list has exactly one node, delete it and set the front and back pointers to nullptr
//returns true if the node was removed, false otherwise
{
return false; // dummy statement
}
template
void DoubleLinkedList::insertAhead(T listValue, T newValue) throw (std::runtime_error)
//Assumes listValue is in the list a node is created, newValue is placed in it, and the node placed ahead of the first occurence of listValue. Also, size increased by 1.
//Example given list of ints 5, 8, 3, 9 and a new value, 11 is inserted ahead of 8 the new list will be: 5, 11, 8, 3, 9
//throws std::exception if listValue isn't in the list
{
}
template
void DoubleLinkedList::insertBehind(T listValue, T newValue) throw (std::runtime_error)
//Assumes listValue is in the list a node is created, newValue is placed in it, and the node placed ahead of the first occurrence of listValue. Also, size increased by 1.
//Example given list of ints 5, 8, 3, 9 and a new value, 11 is inserted behind 8 the new list will be: 5, 8, 11, 3, 9
//throws std::exception if listValue isn't in the list
{
}
template
Node* DoubleLinkedList::find(T value) const
//Assumes T is comparable with ==
//returns a pointer to the first node in the list (from front to back) that contains the value or nullptr if not found
{
return nullptr; // dummy statement
}
template
void DoubleLinkedList::printList() const
//Assumes The type T is overloaded to be printable via the << operator
//If the list is empty, prints ""
//If the list is not empty, then print its content separated by spaces
//NOTE: this method is used to test other parts of your list. Make sure you pass the print tests before moving on!
{
if (isEmpty())
{
cout << "";
return;
}
const Node * walker = m_front;
while (walker != nullptr)
{
cout << walker->getValue();
if (walker->getNext() != nullptr)
cout << " ";
walker = walker->getNext();
} // end while
cout << endl;
return;
}
template
void DoubleLinkedList::printListReverse() const
//Assumes The type T is overloaded to be printable via the << operator
//If the list is empty, prints ""
//If the list is not empty, then print its content separated by spaces
//NOTE: this method is used to test other parts of your list. Make sure you pass the print tests before moving on!
{
if (isEmpty())
{
cout << "";
return;
}
const Node * walker = m_back;
while (walker != nullptr)
{
cout << walker->getValue();
if (walker->getNext() != nullptr)
cout << " ";
walker = walker->getPrevious();
} // end while
cout << endl;
return;
}
//#endif
//Node Implementation
#ifndef _NODE
#define _NODE
#include <iostream>
#include <string>
#include <stdexcept>
using namespace::std;
using namespace::std;
template<class T>
class Node
{
public:
Node();
//initialize next and previous to nullptr
//initialize the m_value to T()
// Assumes that the type T has a parmeterless constructor
//m_value = T();
T getValue() const;
Node<T> * getNext() const;
Node<T> * getPrevious() const;
void setValue(T parm);
void setNext(Node<T> * parm);
void setPrevious(Node<T> * parm);
private:
T value;
// Value in the node
Node<T> * previous;
// pointer to previous node, use nullptr if none
Node<T> * next;
// pointer to next node, use nullptr if none
};
template<class T>
Node<T>::Node()
{
value = T();
previous = nullptr;
next = nullptr;
}
template<class T>
T Node<T>::getValue() const
{
return value;
}
template<class T>
Node<T> * Node<T>::getNext() const
{
return next;
}
template<class T>
Node<T> * Node<T>::getPrevious() const
{
return previous;
}
template<class T>
void Node<T>::setValue(T parm)
{
value = parm;
}
template<class T>
void Node<T>::setNext(Node<T> * parm)
{
next = parm;
}
template<class T>
void Node<T>::setPrevious(Node<T> * parm)
{
previous = parm;
}
#include "DoubleLinkedList.h"
#endif
Explanation / Answer
PROGRAM CODE:
//#ifdef _DOUBLE_LINKED_LIST
//#define _DOUBLE_LINKED_LIST
//#include "Node.h"
template
class DoubleLinkedList
{
public:
DoubleLinkedList();
//Initialized pointers to nullptr and the size to 0
~DoubleLinkedList();
//Deallocates all nodes
bool isEmpty() const;
//Returns true if m_size is zero, false otherwise
//Does not alter the list (hence it's const)
int size() const;
//returns the size of the list
//NOTE: Unlike Java, C++ does not allow variables and methods to have the same name. Hence, the m_ convention for the member variables.
//Does not alter the list (hence it's const)
void pushFront(T value);
//Puts the value of some type, T, in a node
//Puts that node at the front of the list
//Increase m_size by 1
void pushBack(T value);
//Puts the value of some type, T, in a node
//Puts that node at the end of the list
//Increase m_size by 1
bool removeBack();
//One element is removed from the back of the list.
//Returns true if the back element was removed, false if the list is empty.
bool removeFront();
//One element is removed from the front of the list.
//returns True if the front element was removed, false if the list is empty.
bool remove(T value);
//deletes the node containing the passed value
//This method is in charge of deleting a node to prevent memory leaks. Any memory leaks will result in loss of points
//Ensure that m_front is set to the next node in the list. If the list has exactly one node, delete it and set the front and back pointers to nullptr
//returns true if the node was removed, false otherwise
void insertAhead(T listValue, T newValue) throw (std::runtime_error);
//Assumes listValue is in the list a node is created, newValue is placed in it, and the node placed ahead of the first occurence of listValue. Also, size increased by 1.
//Example given list of ints 5, 8, 3, 9 and a new value, 11 is inserted ahead of 8 the new list will be: 5, 11, 8, 3, 9
//throws std::exception if listValue isn't in the list
void insertBehind(T listValue, T newValue) throw (std::runtime_error);
//Assumes listValue is in the list a node is created, newValue is placed in it, and the node placed ahead of the first occurrence of listValue. Also, size increased by 1.
//Example given list of ints 5, 8, 3, 9 and a new value, 11 is inserted behind 8 the new list will be: 5, 8, 11, 3, 9
//throws std::exception if listValue isn't in the list
Node* find(T value) const;
//Assumes T is comparable with ==
//returns a pointer to the first node in the list (from front to back) that contains the value or nullptr if not found
void printList() const;
//Assumes The type T is overloaded to be printable via the << operator
//If the list is empty, prints ""
//If the list is not empty, then print its content separated by spaces
//NOTE: this method is used to test other parts of your list. Make sure you pass the print tests before moving on!
void printListReverse() const;
private:
Node* m_front;
//A pointer that is that is always looking at the front (first) node
Node* m_back;
//A pointer that is that is always looking at the back (last) node
int m_size;
//The current size of the list. (e.g., if there are three nodes in the list the size is 3. If there are no nodes in the list, the size is zero)
}; // end class
template
DoubleLinkedList::DoubleLinkedList()
//Initialized pointers to nullptr and the size to 0
{
m_front= nullptr;
m_back = nullptr;
m_size = 0;
}
template
DoubleLinkedList::~DoubleLinkedList()
//Deallocates all nodes
{
}
template
bool DoubleLinkedList::isEmpty() const
//Returns true if m_size is zero, false otherwise
//Does not alter the list (hence it's const)
{
return m_size == 0;
}
template
int DoubleLinkedList::size() const
//returns the size of the list
//NOTE: Unlike Java, C++ does not allow variables and methods to have the same name. Hence, the m_ convention for the member variables.
//Does not alter the list (hence it's const)
{
return m_size;
}
template
void DoubleLinkedList::pushFront(T value)
//Puts the value of some type, T, in a node
//Puts that node at the front of the list
//Increase m_size by 1
{
Node * p = new Node;
p->setValue(value);
p->setNext(nullptr);
p->setPrevious(nullptr);
if ( isEmpty() )
{
m_front = m_back = p;
m_size++;
p = nullptr;
return;
}
// at least one node
p->setNext(m_front);
m_front->setPrevious(p);
m_front = p;
m_size++;
p = nullptr;
return;
}
template
void DoubleLinkedList::pushBack(T value)
//Puts the value of some type, T, in a node
//Puts that node at the end of the list
//Increase m_size by 1
{
Node * p = new Node;
p->setValue(value);
p->setNext(nullptr);
p->setPrevious(nullptr);
if (isEmpty())
{
m_front = m_back = p;
m_size++;
p = nullptr;
return;
}
p->setPrevious(m_back);
m_back->setNext(p);
m_back = p;
m_size++;
p = nullptr;
return;
}
template
bool DoubleLinkedList::removeBack()
//One element is removed from the back of the list.
//Returns true if the back element was removed, false if the list is empty.
{
if(isEmpty())
return false;
else{
m_back = m_back->getPrevious();
m_back.setNext(nullptr);
m_size--;
return true;
}
}
template
bool DoubleLinkedList::removeFront()
//One element is removed from the front of the list.
//returns True if the front element was removed, false if the list is empty.
{
if(isEmpty())
return false;
else{
m_front = m_front->getNext();
m_front.setPrevious(nullptr);
m_size--;
return true;
}
}
template
bool DoubleLinkedList::remove(T value)
//deletes the node containing the passed value
//This method is in charge of deleting a node to prevent memory leaks. Any memory leaks will result in loss of points
//Ensure that m_front is set to the next node in the list. If the list has exactly one node, delete it and set the front and back pointers to nullptr
//returns true if the node was removed, false otherwise
{
if (isEmpty())
{
return nullptr;
}
Node * walker = m_front;
if(walker->getValue() == value)
{
return removeFront();
}
while (walker.getNext() != nullptr)
{
if (walker->getNext()->getValue() == value)
{
if(walker->getNext()->getNext() != nullptr)
walker->setNext(walker->getNext()->getNext());
else walker->setNext(nullptr);
m_size--;
return true;
}
walker = walker->getNext();
} // end while
return nullptr;
}
template
void DoubleLinkedList::insertAhead(T listValue, T newValue) throw (std::runtime_error)
//Assumes listValue is in the list a node is created, newValue is placed in it, and the node placed ahead of the first occurence of listValue. Also, size increased by 1.
//Example given list of ints 5, 8, 3, 9 and a new value, 11 is inserted ahead of 8 the new list will be: 5, 11, 8, 3, 9
//throws std::exception if listValue isn't in the list
{
Node * p = new Node;
p->setValue(newValue);
p->setNext(nullptr);
p->setPrevious(nullptr);
bool done = false;
Node * walker = m_front;
if(walker->getValue() == listValue)
{
pushFront(newValue);
}
else{
while (walker.getNext() != nullptr)
{
if (walker->getValue() == value)
{
p->setPrevious(walker->getPrevious());
p->setNext(walker);
walker->setPrevious(p);
done = true;
}
walker = walker->getNext();
}
}
if(!done)
throw std::exception;
}
template
void DoubleLinkedList::insertBehind(T listValue, T newValue) throw (std::runtime_error)
//Assumes listValue is in the list a node is created, newValue is placed in it, and the node placed ahead of the first occurrence of listValue. Also, size increased by 1.
//Example given list of ints 5, 8, 3, 9 and a new value, 11 is inserted behind 8 the new list will be: 5, 8, 11, 3, 9
//throws std::exception if listValue isn't in the list
{
Node * p = new Node;
p->setValue(newValue);
p->setNext(nullptr);
p->setPrevious(nullptr);
bool done = false;
Node * walker = m_front;
while (walker.getNext() != nullptr)
{
if (walker->getValue() == value)
{
p->setNext(walker->getNext());
walker->getNext()->setPrevious(p);
walker->setNext(p);
p->setPrevious(walker);
done = true;
}
walker = walker->getNext();
}
if(!done)
throw std::exception;
}
template
Node* DoubleLinkedList::find(T value) const
//Assumes T is comparable with ==
//returns a pointer to the first node in the list (from front to back) that contains the value or nullptr if not found
{
if (isEmpty())
{
return nullptr;
}
const Node * walker = m_front;
while (walker != nullptr)
{
if (walker->getValue() == value)
return walker;
walker = walker->getNext();
} // end while
return nullptr;
}
template
void DoubleLinkedList::printList() const
//Assumes The type T is overloaded to be printable via the << operator
//If the list is empty, prints ""
//If the list is not empty, then print its content separated by spaces
//NOTE: this method is used to test other parts of your list. Make sure you pass the print tests before moving on!
{
if (isEmpty())
{
cout << "";
return;
}
const Node * walker = m_front;
while (walker != nullptr)
{
cout << walker->getValue();
if (walker->getNext() != nullptr)
cout << " ";
walker = walker->getNext();
} // end while
cout << endl;
return;
}
template
void DoubleLinkedList::printListReverse() const
//Assumes The type T is overloaded to be printable via the << operator
//If the list is empty, prints ""
//If the list is not empty, then print its content separated by spaces
//NOTE: this method is used to test other parts of your list. Make sure you pass the print tests before moving on!
{
if (isEmpty())
{
cout << "";
return;
}
const Node * walker = m_back;
while (walker != nullptr)
{
cout << walker->getValue();
if (walker->getNext() != nullptr)
cout << " ";
walker = walker->getPrevious();
} // end while
cout << endl;
return;
}
//#endif
//Node Implementation
#ifndef _NODE
#define _NODE
#include <iostream>
#include <string>
#include <stdexcept>
using namespace::std;
using namespace::std;
template<class T>
class Node
{
public:
Node();
//initialize next and previous to nullptr
//initialize the m_value to T()
// Assumes that the type T has a parmeterless constructor
//m_value = T();
T getValue() const;
Node<T> * getNext() const;
Node<T> * getPrevious() const;
void setValue(T parm);
void setNext(Node<T> * parm);
void setPrevious(Node<T> * parm);
private:
T value;
// Value in the node
Node<T> * previous;
// pointer to previous node, use nullptr if none
Node<T> * next;
// pointer to next node, use nullptr if none
};
template<class T>
Node<T>::Node()
{
value = T();
previous = nullptr;
next = nullptr;
}
template<class T>
T Node<T>::getValue() const
{
return value;
}
template<class T>
Node<T> * Node<T>::getNext() const
{
return next;
}
template<class T>
Node<T> * Node<T>::getPrevious() const
{
return previous;
}
template<class T>
void Node<T>::setValue(T parm)
{
value = parm;
}
template<class T>
void Node<T>::setNext(Node<T> * parm)
{
next = parm;
}
template<class T>
void Node<T>::setPrevious(Node<T> * parm)
{
previous = parm;
}
#include "DoubleLinkedList.h"
#endif