Problems with Doubly-Linked List iterator implementation

Question

I am having some problems with a simple Doubly-Linked list class.

Here is all my code for it:

/*
 * DLList.h
 *
 *  Created on: Nov 19, 2013
 *      Author: tyler
 */

#ifndef DLLIST_H_
#define DLLIST_H_
#include <iostream>
using namespace std;

template <typename T>
class DLList{
private:
struct DLLNode{
private:
    T data_;
    bool visited_;
    DLLNode* next_;
    DLLNode* prev_;
public:

    DLLNode(T data){
        this->data_ = data;
        visited_ = false;
        next_ = NULL;
        prev_ = NULL;
    }

    void setData(T data){
        this->data_ = data;
    }

    void visit(){
        visited_ = true;
    }

    void unvisit(){
        visited_ = false;
    }

    void setNext(DLLNode* next){
        this->next_ = next;
    }

    void setPrev(DLLNode* prev){
        this->prev_ = prev;
    }

    T& getData(){
        return data_;
    }

    bool getVisited(){
        return visited_;
    }

    DLLNode* getNext(){
        return next_;
    }

    DLLNode* getPrev(){
        return prev_;
    }
};

    DLLNode* head_;
    DLLNode* tail_;

public:
    DLList(){
        head_ = NULL;
        tail_ = NULL;
    }

    class DLLiterator{
    private:
        DLLNode* node;
    public:
        DLLiterator(){
            node = head_;
        }
        T& operator*(const DLLiterator& iter){
            return iter.node->getData();
        }
        DLLiterator& operator++(const DLLiterator& iter){
            if(node->getNext() != NULL)
                node = node->getNext;
            else
                node = NULL;
            return *this;
        }
    };   

    bool isEmpty(){
        return (head_ == NULL);
    }

    void addNodeEnd(T data){
        DLLNode* temp = new DLLNode(data);

        if(isEmpty()){
            head_ = temp;
            tail_ = temp;
        }
        else{
            DLLNode* curr;
            curr = tail_;
            curr->setNext(temp);
            temp->setPrev(curr);
            tail_ = temp;
        }
    } 

    bool contains(T data){
        for(DLLNode* start = head_; start != NULL; start = start->getNext()){
            if(start->getData() == data)
                return true;
        }
        return false;
    }

    void remove(T data){
        for(DLLNode* curr = head_; curr != NULL; curr = curr->getNext()){
            DLLNode* key = curr;
            if(curr->getData() == data){
                if(curr == head_){
                    head_ = key->getNext();
                    key->getNext()->setPrev(NULL);
                    delete key;
                }
                if(curr == tail_){
                    tail_ = key->getPrev();
                    key->getPrev()->setNext(NULL);
                    delete key;
                }
                else{
                    DLLNode* prev;
                DLLNode* next;
                    prev = key->getPrev();
                    next = key->getNext();
                    prev->setNext(next);
                    next->setPrev(prev);
                    delete key;
                }
            }
        }
    }

    void printList(){
        for(DLLNode* curr = head_; curr != NULL; curr = curr->getNext()){
            cout << curr->getData() << "\n";
        }
    }
};



#endif /* DLLIST_H_ */

My problem is that I don't know how to actually use the iterator in an outside class. Everything else is tested and seems to be working fine. Still need to add a simple destructor, but my focus right now is the iterator. Any help would be great.

I tried just doing:

DLLiterator iter;

but that is clearly wrong...

EDIT: This is the operator++ code now:

iterator operator++(){
    if(node_->getNext() != NULL)
        node_ = node_->getNext;
    else
        node_ = NULL;
    return *this;
}

but now it's asking for an int as an argument...?

Quite a lump of code with slightly broken indenting, but if you're asking how to declare an iterator of your linked list: Like this: DLList<int>::iterator iter; — Grimm The Opiner
– Grimm The Opiner, Commented Nov 20, 2013 at 16:37
IMO you should change your * and ++ operator overload function to "not accept" any input parameter. — Abhishek Bansal
– Abhishek Bansal, Commented Nov 20, 2013 at 16:42

Mike Seymour · Accepted Answer · 2013-11-20 16:42:30Z

1

Outside the class, you'd have to use the qualified name DLList<whatever>::DLLiterator. You can see that there's little point adding the wart to the nested name, unless you like your names to be hard to read: it just partly duplicates the scope name. I'd rename it iterator.

Now your problem is that it tries to initialise itself using a member of the list, head_, but it doesn't have access to a list to extract the head from. You probably want to follow the example of the standard containers, and create an iterator via a member of the list:

iterator begin() {return iterator(head_);}

and modify the iterator's constructor accordingly.

In C++11, this means users won't usually have to write out the nasty qualified name at all; you could get an iterator with

auto it = list.begin();

Finally, remove the arguments from the iterator's operator* and operator++. Since they are member functions, their operand is passed implicitly as this, not explicitly as an argument.

answered Nov 20, 2013 at 16:42

Mike Seymour

256k30 gold badges467 silver badges658 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

tbgeorge Over a year ago

That really helped, but now the operator++ is asking for an int as an argument... see the edit.

Mike Seymour Over a year ago

@tbgeorge: You've only implemented pre-increment, ++it. If you also want post-increment, it++, then you'll need operator++(int) as well. (The dummy argument indicates that it's post-increment, but doesn't have any other meaning). That will need to copy of iterator before incrementing it, and return that copy by value.

tbgeorge Over a year ago

Ok, I fixed that but now I get this:

error: cannot convert ‘DLList<T>::DLLNode::getNext<std::basic_string<char> >’ from type ‘DLList<std::basic_string<char> >::DLLNode* (DLList<std::basic_string<char> >::DLLNode::)()’ to type ‘DLList<std::basic_string<char> >::DLLNode*’

from this line node_ = node_->getNext;

Mike Seymour Over a year ago

@tbgeorge: Look at the line the compiler's pointing you to, and figure out what's wrong. (HINT: to call a function, use ()).

tbgeorge Over a year ago

Wow, I'm dumb, completely looked over that. Thanks.

Collectives™ on Stack Overflow

Problems with Doubly-Linked List iterator implementation

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related