Iterator pointer does not reference the first element

Question

I am trying to implement a LinkedList which can be iterated through in c++.

I have therefore made an Iterator class, such that dereferencing an Iterator would return the first element. However, this has not been working. When I then instantiate a new int LinkedList and attempt to access the first element by dereferencing the result of begin(), I do not retrieve the first element of the list, but a 10 digit number such as '1453755360'

My node class is just composed of two right/left node pointers and a data variable

linkedlist class

template <typename T>
class LinkedList{

public:
    LinkedList(){
        count =(0);
        head =(nullptr);
        tail =(nullptr);
    }

    void push_head(T input){

        Node<T> newNode = Node<T>(input);
        newNode.left = nullptr;
        newNode.right = head;

        head = &newNode;
        count++;
    }

    T front(){
        T& data = (head->data);
        return data;
    }

    void push_tail(T input){

        Node<T> newNode = Node<T>(input);
        newNode.right = tail;
        newNode.left = nullptr;

        tail = &newNode;
        count++;
    }

    T back(){
        T& data = (tail->data);
        return data;
    }


    Iterator<T> begin(){
        Iterator<T> test = Iterator<T>(head);
        return test;
    }


private:
    int count;
    Node<T> *head;
    Node<T> *tail;

};

Here is where I am testing the code

    LinkedList<int> ll;

    ll.push_tail(7);
    ll.push_tail(9);

    if (*(ll.begin()) == 9) {
        cout << "pass" << endl;
    } else {
        cout << "returned : " << *(ll.begin()) << endl;
    }

This Node<T> newNode = Node<T>(input); will be destroyed when the scope ends. — alain
– alain, Commented Oct 18, 2017 at 16:14
I am successfully pushing elements into the list, but I cannot retrieve elements from the iterator — A. Floyd
– A. Floyd, Commented Oct 18, 2017 at 16:21

8znr · Accepted Answer · 2017-10-18 16:27:37Z

1

The push_back() implementation requires that if head is null it has to be set, the same for the push_front with respect to the tail.

edited Oct 18, 2017 at 16:27

answered Oct 18, 2017 at 16:21

8znr

3464 silver badges14 bronze badges

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

Comments

Remy Lebeau · Accepted Answer · 2017-10-18 19:03:38Z

You are allocating your node objects on the stack, so they are destroyed automatically when they go out of scope. You are storing pointers to those objects, which leaves the pointers dangling when the objects are destroyed. You need to allocate the nodes on the heap using new instead.

Also, push_front() is not updating tail when the list is empty, and is not updating an existing head to point at the new node when the list is not empty. Similar with push_back().

Try something more like this:

template <typename T>
struct Node
{
    T data;
    Node *left;
    Node *right;

    Node(const T &d = T(), Node *l = nullptr, Node *r = nullptr)
        : data(d), left(l), right(r) {}
};

template <typename T>
class NodeIterator {
public:
    typedef std::ptrdiff_t difference_type;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef std::bidirectional_iterator_tag iterator_category;

    NodeIterator(Node<T> *input = nullptr) : cur(input) {}
    NodeIterator(const NodeIterator &) = default;
    NodeIterator(NodeIterator &&) = default;
    ~NodeIterator() = default;

    NodeIterator& operator=(const NodeIterator &) = default;
    NodeIterator& operator=(NodeIterator &&) = default;

    reference operator*() {
        return cur->data;
    }

    NodeIterator& operator++ () {
        if (cur) cur = cur->right;
        return *this;
    }

    NodeIterator operator++ (int) {
        NodeIterator tmp(*this);
        if (cur) cur = cur->right;
        return tmp;
    }

    NodeIterator& operator-- () {
        if (cur) cur = cur->left;
        return *this;
    }

    NodeIterator operator-- (int) {
        NodeIterator tmp(*this);
        if (cur) cur = cur->left;
        return tmp;
    }

    bool operator==(const NodeIterator &rhs) const {
        return (rhs.cur == cur);
    }

    bool operator!=(const NodeIterator &rhs) const {
        return (rhs.cur != cur);
    }

private:
    Node<T> *cur;
};

template <typename T>
class LinkedList {
public:
    typedef NodeIterator<T> iterator;

    LinkedList() : count(0), head(nullptr), tail(nullptr) {}

    ~LinkedList() {
        while (head) {
            Node<T> *tmp = head;
            head = head->right;
            delete tmp;
        }
    }

    void push_front(const T &input) {
        Node<T> *newNode = new Node<T>(input, nullptr, head);

        if (head) head->left = newNode;
        head = newNode;

        if (!tail) tail = newNode;

        ++count;
    }

    T& front() {
        return head->data;
    }

    void push_back(const T &input) { 
        Node<T> *newNode = new Node<T>(input, tail, nullptr);

        if (!head) head = newNode;

        if (tail) tail->right = newNode;
        tail = newNode;

        ++count;
    }

    T& back() {
        return tail->data;
    }

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

    iterator end() {
        return iterator();
    }

private:
    int count;
    Node<T> *head;
    Node<T> *tail;    
};

Then you can do this:

LinkedList<int> ll;

ll.push_back(7);
ll.push_back(9);

auto iter = ll.begin();
if (*iter == 7) {
    cout << "pass" << endl;
} else {
    cout << "returned : " << *iter << endl;
}

You can even do things like this now:

for (LinkedList<int>::iterator iter = ll.begin(), end = ll.end(); iter != end; ++iter) {
    cout << *iter << endl;
}

for (int i : ll) {
    cout << i << endl;
}

Collectives™ on Stack Overflow

Iterator pointer does not reference the first element

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related