ReverseList Iterator

[shaoen01]

Hi all,

I am trying to create my own template class reverse list operator. And was wondering how do i reverse the list. I can't seem to use list.reverse() as i am not using the C++ library list, but making my own.

So i am wondering how i should modify List to maybe point to the previous object? Not sure if i should maybe Node<T> *previous; in the Node class or List class. It seems better to put it in the Node class, but i am a bit stuck on how to do it. Any help would be fantastic.

template<typename T> class RLstIter{
List<T> &list;
Node<T> *current;

public:
RLstIter(List<T> &L):list(L){}
};

template<typename T> class List {
Node<T> *head;
friend class ListIter<T>;
friend class RLstIter<T>;

public:
List(): head(0){}
~List(){
while(Node<T> *q = head){
head = head->next;
delete q;
}     
}

void pushH(const T &D){

head = new Node<T>(D,head);
}

void pushT(const T &D){
if(!head)
pushH(D);
else {
Node<T> *q = head;
while(q->next) q = q->next;
q->next = new Node<T>(D,0);
}
}

};

template <typename T> class List;
template <typename T> class ListIter;
template<typename T> class RLstIter;
template <typename T>
class Node {
T data;
Node<T> *next;
public:
friend class List<T>;
friend class RLstIter<T>;
Node(const T &D, Node<T> *N): data(D), next(N){}
};

[seymore15074]

It sounds like you want to create a doubly-linked list. Add a previous node pointer to your Node class and work from there.

[shaoen01]

I made some changes by adding a previous Node to my List class. Based on this output as written in my main(), my output should be "<lark> <kiwi> <joey> <ibis> <hawk> <goat>". I can't seem to find out what is the problem.

template <typename T> class List;
template <typename T> class ListIter;
template<typename T> class RLstIter;
template <typename T>
class Node {
T data;
Node<T> *next;
Node<T> *previous;

public:
friend class List<T>;
friend class ListIter<T>;
friend class RLstIter<T>;
Node(const T &D, Node<T> *N, Node<T> *P){
  data=D;
  next=N;
  previous=P;
}

};

//LIST CLASS//
template<typename T> class List {
Node<T> *head;
Node<T> *before;
Node<T> *tail;

friend class ListIter<T>;
friend class RLstIter<T>;

public:
List(): head(0),tail(0){}
~List(){
while(Node<T> *q = head){

head = head->next;
delete q;
}     
}

void pushH(const T &D){

head = new Node<T>(D,head,0); //previous is 0
}

void pushT(const T &D){
if(!head)
pushH(D);
else {
Node<T> *q = head;
Node<T> *b = 0;
while(q->next) {
q = q->next;
b=q;
}
q->next = new Node<T>(D,0,b);
tail=q->next;
}
}

bool popH(T &D){
if(!head) return false;
D = head->data;
Node<T> *q = head;
head = head->next;
delete q;
return true;
}

};

//Reverse LIST Iterator CLASS//
template<typename T> class RLstIter{
List<T> &list;
Node<T> *current;
int countElement;

public:
RLstIter(List<T> &L):list(L),countElement(0){}
void operator & () { // reset to last element
Node<T> *q = list.tail;
current = q;
}
T operator () () {
return current->data;
}

void operator = (const T &D) {
current->data = D;
}
bool operator ! () {
return current != 0;
}
void operator ++ () {

current = current->previous;
}

};

int main(){
List<string> zoo;
string what;
ListIter<string> i(zoo);
RLstIter<string> j(zoo);

cout<<"breed by pushTail:\n";
zoo.pushT("goat");
zoo.pushT("hawk");
zoo.pushT("ibis");
zoo.pushT("joey");
zoo.pushT("kiwi");
zoo.pushT("lark");
for(&j; !j; ++j) j = "<" + j(), cout << ' ' << j();
cout<<endl;
}