I'm trying to create a pointer implementation of a doubly-linked list with a custom iterator along with it. I haven't finished it but it gives me a stack overflow error every time I declare a pointer of type dnode (a node in the linked list). I have tried a lot, can't even remember most of it. It's due in 48 hrs. Please help!
The header file(dlist.h)
#ifndef DDList_H
#define DDList_H
const int DEFAULT_CAPACITY = 10;
template <class T>
struct dnode{
T Data;
dnode<T> * prev;
dnode<T> * next;
///constructor
///dnode<T>(): prev(nullptr), next(nullptr), Data(NULL){}
dnode<T>(const T& d, dnode<T> *n = nullptr, dnode<T> *p = nullptr) : Data(d), next(n), prev(p){}
//dnode<T> copy();
~dnode(){delete this;}
};
template <class T>
class DList{
public:
DList();
DList(bool sorted);
DList(const DList &dlst); ///copy constructor
~DList();
void isEmpty();
void insertFirst(T data);
void insertBack(T data);
void insert(T data); ///insert back if unsorted
bool insertBefore(T before, T data); ///inserts data before "before"
bool insertAfter(T before, T data);///inserts data after "after"
bool removeFirst();
bool removeLast();
bool remove(T data);///working on this!!!
bool update(T oldValue, T newValue);///the linked list must be set unsorted
/*not done*/ dnode<T>* find(T data);///returns the node when the data is found
/*not done*/ DList<T> copy();
/*not done*/ void setSorted(bool sorted); ///if it is converted from unsorted to sorted, the linked list must be set unsorted
void destroy(); ///destroy the list. you can call this in destructor
void operator = (const DList &D ); ///overloading assignment operator
/*not done*/ void insertRangeBefore(dnode<T>* before, DList<T> range);
/*not done*/ void insertRangeAfter(dnode<T>* after, DList<T> range);
/*not done*/ bool removeRange(dnode<T>* rangeFirst, dnode<T>* rangeLast); ///remove range from rangeFirst to rangeLast
/*not done*/// DList getSubDList(dnode<T>* rangeFirst, dnode<T>* rangeLast, bool remove=true); ///return a DList from rangeFirst to rangeLast. If remove is true, the range will be removed from the orginal
/*not done*/// void sort();
/*not done*/ void displayForward(void (*displayer)(T));
/*not done*/ void displayBackward(void (*displayer)(T));
bool IsEmpty;
class Iterator {/// Inner class iterator
friend class DList;
private:
dnode<T> *nodePtr;
/// The constructor is private, so only our friends can create instances of iterators.
public:
Iterator();///default constructor
Iterator(dnode<T> *newPtr);
bool operator!=(const Iterator& itr) const;/// Overload for the comparison operator !=
T& operator*() const;/// Overload for the dereference operator *
Iterator operator++(int);/// Overload for the postincrement operator
Iterator& operator++();/// Overload for the prefixincrement operator
};/// End of inner class iterator
Iterator begin() const;
Iterator end() const;
Iterator inserter(Iterator position, const T& data);
Iterator erase(Iterator position);
protected:
private:
dnode<T> *head;
dnode<T> *tail;
bool sorted;
void insertNodeAfter(dnode<T> * p, dnode<T> * before);///insert prepared node after before
void insertNodeBefore(dnode<T> * p, dnode<T> * after);///insert prepared node before after
dnode<T> * deleteNode(dnode<T> * prev) ; ///remove node
dnode<T> * insertionSlotAfter (dnode<T> * p);///it finds after which to insert. returns back if unsorted. returns Null if it is to be inserted by front
};
#endif /// DDList_H
The implementation file(dlist.cpp)
#include <iostream>
#include "dlist.h"
using namespace std;
template <class T>
DList<T>::DList(){
head = tail = nullptr;
IsEmpty = true;
}
template <class T>
DList<T>::DList(bool sorted){
DList();
this->sorted = sorted;
}
template <class T>
DList<T>::DList(const DList &dlst){ ///copy constructor
if (dlst.IsEmpty){
DList();
for( auto & x : dlst ){
inserter(begin(),dlst );
}
}
this->sorted = dlst.sorted;
///not done yet
}
template <class T>
DList<T>::~DList(){///destructor
destroy();
delete head;
delete tail;
}
template <class T>
void DList<T>::isEmpty(){
///bool isEmpty;
if(this->head == NULL && this->tail == NULL){
///cout<<"The Doubly Linked List Is Empty!";
IsEmpty = true;
}
else{
///cout<<"The Doubly Linked List Is Not Empty!";
IsEmpty = false;
}
}
template <class T>
void DList<T>::destroy(){
for (dnode<T> *temp; head != nullptr; ) {
temp = head;
head = head->next;
delete temp;
}
}
template <class T>
void DList<T>::insertFirst(T data){
/*
dnode<T> *newNode;// = new dnode<T>(data, head, head->prev);
newNode->next= this->head;
newNode->prev = this->head->prev;
newNode->Data = data;
head = newNode;///to make the head point to the data. data must be declared as a pointer
delete newNode;///to free up memory
*/
inserter(begin(),data);
}
template <class T>
void DList<T>::insertBack(T data){
/*
dnode<T> *newNode;// = new dnode<T>(data, tail->next, tail);
newNode->next = this->tail->next;
newNode->prev = this->tail;
newNode->Data = data;
tail = newNode;
delete newNode;
*/
inserter(end(), data);
}
template <class T>
void DList<T>::insert(T data){ ///insert back if unsorted
if(!sorted){insertBack(data);}
else insertFirst(data);
this->sorted = false;///the list is unsorted after any kind of insertion
}
template <class T>
bool DList<T>::removeFirst(){///going to use the iterator function in here
if(this->isEmpty){return false;}
else{
delete head->Data;///may not be necessary, not sure
head = this->head->next;
head->prev = nullptr;
if(this->head == this->tail){
head = tail = nullptr;
isEmpty();
}
}
return true;
}
template <class T>
bool DList<T>::removeLast(){///going to use the iterator function in here
if(this->isEmpty){return false;}
else{///list not empty
delete tail->Data;///may not be necessary, not sure
tail = this->tail->prev;
tail->next = NULL;
if(this->head == this->tail){
head = tail = NULL;
isEmpty();
}
}
return true;
}
template <class T>
bool DList<T>::remove(T data){///going to use the iterator function in here
dnode<T>* nodeBefore, nodeAfter;
dnode<T>* nodeFound;
if(isEmpty){return false;}
else{
nodeFound = find(data);
if(nodeFound != head && nodeFound != tail){/// the middle of the list
nodeBefore = nodeFound->prev;
nodeBefore->next = nodeFound->next;
nodeAfter = nodeFound->next;
nodeAfter->prev = nodeFound->prev;
}
else if(nodeFound == head){removeFirst(data);}
else{removeLSast(data);}///nodeFound == tail
}
delete nodeAfter, nodeBefore, nodeFound;
return true;
}
template <class T>
bool DList<T>::update(T oldValue, T newValue){///the linked list must be set unsorted
if(IsEmpty){return false;}
else{
dnode<T>* nodeNeeded, nodeFound;
nodeNeeded->Data = oldValue;
nodeFound = find(nodeNeeded);
nodeFound->newValue;
}
return true;
}
/*
template <class T>
template <class T>
*/
template <class T>
void DList<T>::operator= (const DList &D ){///overloading assignment operator
if( this == &D ){return *this;}
destroy();
for( Iterator itr = D.begin(); itr!= D.end(); ++itr){
insertBack( *itr );
}
}
template <class T>
DList<T>::Iterator::Iterator(dnode<T> *newPtr) : nodePtr(newPtr){}
template <class T>
DList<T>::Iterator::Iterator() : nodePtr(nullptr){}
template <class T>/// Overload for the comparison operator !=
bool DList<T>::Iterator::operator!=(const Iterator& itr) const {
return nodePtr != itr.nodePtr;
}
template <class T> /// Overload for the dereference operator *
T& DList<T>::Iterator::operator*() const {
return nodePtr->next->Data;
}
template <class T>/// Overload for the postincrement operator ++
typename DList<T>::Iterator& DList<T>::Iterator::operator++() {
nodePtr = nodePtr->next;
return *this;
}
template <class T>/// Overload for the postincrement operator ++
typename DList<T>::Iterator DList<T>::Iterator::operator++(int) {
Iterator temp = *this;
nodePtr = nodePtr->next;
return temp;
}
template <class T>///the name of the type is specified by typename and it's "DList<T>::Iterator" not Iterator
typename DList<T>::Iterator DList<T>:: begin() const {
return Iterator(head);
}
template <class T>
typename DList<T>::Iterator DList<T>:: end() const {
return Iterator(tail);
}
template <class T>
typename DList<T>::Iterator DList<T>::inserter(Iterator position,const T& data) {
dnode<T>* newNode = new dnode<T>(data, position.nodePtr->next, position.nodePtr->prev);
if (position.nodePtr == tail){tail = newNode;}
position.nodePtr->next = newNode;
return position;
}
template <class T>
typename DList<T>::Iterator DList<T>:: erase(Iterator position) {
dnode<T> *toDelete = position.nodePtr->next;
position.nodePtr->next = position.nodePtr->next->next;
if (toDelete == tail){tail = position.nodePtr;}
delete toDelete;
return position;
}
Lastly, the main file (just in case)
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include "dlist.cpp"
using namespace std;
int main(){
DList<int> doubleList;
doubleList.insert(1);
doubleList.insert(5);
//doubleList.insert(3);
///doubleList.begin();
return 0;
}
Aucun commentaire:
Enregistrer un commentaire