Linked List Iterator

I know there must be lots of these posted, but I search on google and on here, and I'm still having trouble.

We still haven't covered iterators fully and I'm having trouble with it. If anyone has a link to how iterators work (w/anything) that includes code, please let me know.
Anyway, I have a linked list class and an iterator class. I'll just try to post the relevant code.

One of the errors that I get is a warning that a reference to local variable 'it' is returned. I think I understand the error, but I'm not sure how to solve it. Any help is appreciated. Thanks.


**********LINKEDLIST CLASS AND MAIN***********
// LinkedList and main are together. they're not separate files.

Code:

---

#include <iostream>
#include <conio.h>

using namespace std;


template <class T>
class Node
{
public:
    T data;
    Node<T>* next;
    Node<T>* prev;
    Node(){ next = NULL; prev = NULL;}
};

#include "ListIterator.h"

template <class T>
class LL
{
    public:
        LL();
        ListIterator<T> &begin();
        ListIterator<T> &end();
    private:
        Node<T>* head;
        friend class ListIterator<T>;
};

template <class T>
ListIterator<T>& LL<T>::begin()
{
    ListIterator<T> it(head);
    return it;
}

template <class T>
ListIterator<T>& LL<T>::end()
{
    // This is wrong... I'm not sure how to do this...
    ListIterator<T> it(head);
    while(it.hasNext())
    return it;
}

int main()
{ 
    LL<int> obj;
    obj.pushFront(3);
    obj.pushFront(4);
    //obj.printList(cout);
   
    ListIterator<int> iter = obj.begin();

    getch();
    return 0;
}

---

*********LISTITERATOR CLASS*************

Code:

---


using namespace std;
template <class T>
class ListIterator
{
  public:
          Node<T> *current;
          ListIterator() {}
          ListIterator(Node<T>*);
          bool hasNext(); 
      bool hasPrevious();
          T next();
          T previous();
          void insert(T val);
          void remove();
};


//
template <class T>
ListIterator<T>::ListIterator(Node<T> *head)
{
    current = head;
}

   
// Returns true if it has a next node
template <class T>
bool ListIterator<T>::hasNext()
{
        return (current->next == NULL);
}

// Returns true if it has a previous node
template <class T>
bool ListIterator<T>::hasPrevious()
{
        return (current->previous == NULL);
}

// Returns next node's data
template <class T>
T ListIterator<T>::next()
{
        if(!this->hasNext())
                return;
        return (current->next->data);
}

// Returns previous node's data
template <class T> 
T ListIterator<T>::previous()
{
        if(!this->hasPrevious())
                return;
        return (current->prevous->data);
}

template <class T>
void ListIterator<T>::insert(T val)
{
        Node<T> newNode = new Node<T>(val);
        if(this->hasNext())
        {
                newNode->back = current;
                newNode->next = current->next;
                current->next->back = newNode;
                current->next = newNode;
        }
        // Last one in list
        else if(this->hasPrevious())
        {
                newNode->back = current;
                current->next = newNode;               
        }
}

// Remove function
template <class T> 
void ListIterator<T>::remove()
{
        if(current == NULL)
                return;
        current->next->back = current->back;
        current->back->next = current->next;
        delete current;

}

---

Code:

---

template <class T>
ListIterator<T>& LL<T>::begin()
{
    ListIterator<T> it(head);
    return it;
}

---

Simply remove the & from the return type:

Code:

---

template <class T>
ListIterator<T> LL<T>::begin()
{
    ListIterator<T> it(head);
    return it;
}

---

Or even better:

Code:

---

template <class T>
ListIterator<T> LL<T>::begin()
{
    return ListIterator<T> (head);
}

---

Which should return a copy of the unnamed variable. This is helpful because its easier for the compiler to optimized unnamed variables.

Ah, thanks. My professor gave me the code like that. It's working now, somewhat. However, he didn't tell us to overload the postfix (++). I'm assuming this is necessary in order to implement the end function and also to do this?

Code:

---

// in main
ListIterator<int> iter = obj.begin();
    while(iter.hasNext())
    {
        cout << "test";
        cout << iter.next();
        //iter++?
    }

---

Oh, and thanks for the little tip about unnamed variables.

Hey gflores.

We just went over iterators in our class last week, and I was confused too. However, the project I am working on requires them (uses linked lists as well). Here's what I gained from toying with iterators:

Even though we were told to do the iterator++ thing, I didn't find it necessary; the code given to us didn't explain much about it. I started out making an iterator class on my own, based on what I knew it had to do. Iterators are nodes pointing to places inside the list. This is helpful for reading the list without modifying it (like changing the curr node in the list). Using a separate class for iterators is done so that you can create as many iterators as you want (although I suppose you could create a dynamic amount of iterators inside the list, but it seems confusing to do so). The iterator has a current position node, and a constant list to which it is attached to. Give it the same next/prev and getData functions and you can move about the same list (without creating a copy of the list) without changing data. Most of the time I used iterators was to move through the whole list and display each node (among other functions). Some things are still puzzling for me, but I tend to block that out for now ;-).

Here is my iterator class for working through my llist class. If you need any more details about it, I can post my llist class too.

Code:

---

//Iterator class, friend of LList class.
template <class T>
class Iterator
{
        private:
                Node<T> *Pos;
                const LList<T> *theList;
        public:
                Iterator() { return; }
                Iterator(const LList<T> &l):theList(&l) { Pos = l.curr; }
              //below is useful for current project, although doesn't change anything
                Iterator(const Poly &p):theList(&p.P) { Pos = p.P.curr; }

                bool next()
                {
                        if ((Pos == NULL) || (Pos->getNext() == NULL)) return false;
                        Pos = Pos->getNext();
                        return true;
                }
                bool prev()
                {
                        if ((Pos == NULL) || (Pos == theList->head )) return false;
                        Node<T> *temp = Pos;
                        Pos = theList->head;
                        while (Pos->getNext() != temp)
                                Pos = Pos->getNext();
                        return true;
                }
                Node<T>* getNext() { return Pos->getNext(); }
                void reset() { Pos = theList->head; }
                void seekStart()
                {
                        Pos = theList->head->getNext();
                        if (Pos == NULL)
                                Pos = theList->head;
                }
                void seekEnd() { while(next()); }
                const T& getData() { return Pos->getItem(); }
};

---

Now here's an example of how I use it:

Code:

---

double Poly::solve(double x)
{
        Term temp;
        double total = 0;
        Iterator<Term> it(P);
        it.seekStart();
        do
        {
                temp = it.getData();
                total += temp.eval(x);
        } while (it.next());
        return total;
}

---

P.S. > My guess is that the ++ concept is just a more fancy way of calling next(), although I'm not positive.

Ok, looking at my example code, it doesn't help that it's a member function to another class, so here's an example I just wrote up to display all terms of the polynomial outside of the class (inside main()):

Code:

---

        Iterator<Term> it(c);
        it.seekStart();
        do
        {
                cout << it.getData() << " ";
        } while (it.next());
        cout << endl;

---

This just loops through the entire list to display each node(term).

Ok, so I did a bit more researching online and I added some more code.
I've overloaded ++ and -- (both prefix) and != and added getData (thanks neandrake). I also got the for loop (which I had seen in various places) to work, sort of.

Everything works now, but I kinda did some bad coding in the end() function. I could use some help figuring that out.

I have three questions.
1. Should end() return the itereator when it's at null or the last node?t
2. Can you overload the dereference operator? So that '*iter' returns the data from the node that iter is pointing to?
3. Is it correct that begin and end don't return a reference?

Code:

---

// prefix ++
template <class T>
ListIterator<T>& ListIterator<T>::operator++()
{
    current = current->next;
    return *this;
}

template <class T>
ListIterator<T>& ListIterator<T>::operator--()
{
    // prefix --
    current = current->prev;
    return *this;
}

template <class T>
bool ListIterator<T>::operator!=(ListIterator<T> rhs)
{
    //return true;
    return (current != rhs.current);
}

template <class T>
T& ListIterator<T>::getData()
{
    return current->data; 
}

---

***Linked List and Main***

Code:

---

// Need help here
template <class T>
ListIterator<T> LL<T>::end()
{
    ListIterator<T> iter(head);
    if(head == NULL)
        return iter;
    while(iter.hasNext())
    {
        ++iter;
    }
    ++iter;
    return iter;
}

int main()
{
    LL<int> obj;
    obj.pushFront(3);
    obj.pushFront(4);
    obj.pushFront(5);
   
    // prints out 5 4 3 using recursive printList
    obj.printList(cout);
    cout << endl;
   
    // prints out 5 4 3 using iterator
    for(ListIterator<int> iter = obj.begin(); iter != obj.end(); ++iter)
        cout << iter.getData() << " ";

    getch();
    return 0;
}

---

1) end() function seems fine, should point to the last node, the one befure null.
2) I believe it's possible to do so, but you could easily overload something else like the () to do the same things, so (iter) would return the data. However, using parenthesis could cause problems when it is used in an if or loop condition. The * reference could also cause problems if you happen to use pointers to iterators.
3) It is fine that you don't return a reference, however it is recommended. Less memory usage, and the returned iterator would only be temporary.

Also, check to make sure you should be returning an iterator instead of a node with end() and begin(). Choose one or the other; I would recommend node because if you return an iter, you have to compare it to an iter (doesn't seem like it would always be the case).

You are probably aware that iterators are commonly used in the Standard Template Library. The routine iterator syntax in STL is such that end() refers to one past the last node/link/element. It is not a dereferencable address so it doesn't matter what is there, just that you can reach it.

3.) Yeah, that seems the best way (to return a reference), but when I do, I get the error in the first post. I found one other place that doesn't return a reference, so maybe it's correct this way too.

Ok, I looked over your code a little (I can't really spend time right now, I don't have a mouse and can't browse easily). Some things I've noticed. The problem with your end function I think has to do with:

Code:

---

while (it.hasNext());

---

If you check your hasNext() function, it just returns a bool value saying if there is a next node. I didn't see anything that actually advances current. Make a next() function that does:

Code:

---

current = current->next;

---

That sets the current node to the current's next node. This should advance to the next node and return true, otherwise false if there is no next node. From the looks of your code, it seems that you can call hasNext() inside next to do an easy error check whether it should change current:

Code:

---

bool ListIterator<T>::next()
{
if (hasNext()) { current = current->next; return true;}
return false;
}

---

Also, I didn't have time to check, but check your code. Some times your functions return nodes, other times iterators. My guess is that would only want to return node references. When I get my mouse back, I will be able to look at your code more thouroughly.

-christoph