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;
    }

Answer 1

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;
}

Answer 2

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.