C++ linked list iterator implementation

Question

I'm a first year computer engineering student and would appreciate feedback on some code.

I've created a linked-list with an iterator to be able to range for loops like: for (int i : list) {} where list is Linked_List<int> list;.

Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:

• Use of raw pointers

Linked_List.h

namespace Util
{
    template<typename T>
    class Linked_List
    {
    public:
        struct Iterator;
    private:
        struct Node;
    public:
        Linked_List();
        ~Linked_List() noexcept(false);
        Linked_List(const Linked_List&) = delete;
        Linked_List(Linked_List&&) = delete;
        Linked_List& operator=(const Linked_List&) = delete;
        Linked_List& operator=(Linked_List&&) = delete;

        // Modifiers
        void push_back(T);
        void push_front(T);
        void pop_back();
        void pop_front();

        // Capacity
        bool empty() const;
        unsigned int size() const;

        // Element access
        T back() const;
        T front() const;
        Iterator begin() const;
        Iterator end() const;

        // TODO:
        //Iterator insert(const Iterator, T);
        //Iterator erase(const Iterator);
    private:
        Node* _head;
        Node* _tail;
        unsigned int _size;
    };
};

Linked_List.cpp

#include "pch.h"
#include "Linked_List.h"

namespace Util
{
    template<typename T>
    struct Linked_List<T>::Node
    {
        Node() : prev(nullptr), next(nullptr) {}
        Node(T t) : value(t), prev(nullptr), next(nullptr) {}
        Node* prev;
        Node* next;
        T value;
    };

    template<typename T>
    struct Linked_List<T>::Iterator
    {
        Iterator() : _current(nullptr)
        {
            //
        }
        T& operator*() const
        {
            return _current->value;
        }
        Iterator& operator++()
        {
            _current = _current->next;
            return *this;
        }
        bool operator!=(const Iterator& rhs)
        {
            return _current != rhs._current;
        }
    private:
        friend class Linked_List<T>;
        Iterator(Node* n) : _current(n) {}
        Node* _current;
    };

    template<typename T>
    Linked_List<T>::Linked_List() : _size(0)
    {
        _head = new Node();
        _tail = new Node();
        _head->next = _tail;
        _tail->prev = _head;
    }

    template<typename T>
    Linked_List<T>::~Linked_List() noexcept(false)
    {
        while (!empty())
        {
            pop_back();
        }
        delete head;
        delete tail;
    }

    template<typename T>
    void Linked_List<T>::push_back(T t)
    {
        Node* n = new Node(t);
        n->prev = _tail->prev;
        n->next = _tail;
        _tail->prev->next = n;
        _tail->prev = n;
        ++_size;
    }

    template<typename T>
    void Linked_List<T>::push_front(T t)
    {
        Node* n = new Node(t);
        n->next = _head->next;
        n->prev = _head;
        _head->next->prev = n;
        _head->next = n;
        ++_size;
    }

    template<typename T>
    void Linked_List<T>::pop_back()
    {
        if (empty()) throw Error("pop_back(): on empty list");
        Node* n = _tail->prev;
        _tail->prev->prev->next = _tail;
        _tail->prev = _tail->prev->prev;
        --_size;
        delete n;
    }

    template<typename T>
    void Linked_List<T>::pop_front()
    {
        if (empty()) throw Error("pop_front(): on empty list");
        Node* n = _head->next;
        _head->next->next->prev = _head;
        _head->next = _head->next->next;
        --_size;
        delete n;
    }

    template<typename T>
    bool Linked_List<T>::empty() const
    {
        //return (_head->next == _tail) && (_tail->prev == _head);
        return size() == 0;
    }

    template<typename T>
    T Linked_List<T>::back() const
    {
        if (empty()) throw Error("back(): on empty list");
        return _tail->prev->value;
    }

    template<typename T>
    T Linked_List<T>::front() const
    {
        if (empty()) throw Error("front(): on empty list");
        return _head->next->value;
    }

    template<typename T>
    unsigned int Linked_List<T>::size() const
    {
        return _size;
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::begin() const
    {
        return Iterator(_head->next);
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::end() const
    {
        return Iterator(_tail);
    }
};

I haven't yet figured out how to implement:

• Iterator insert(const Iterator, T);
• Iterator erase(const Iterator);

Answer 1

Comment

Flaws I already know of but choose to ignore because of how the teacher in class implements stuff:`

• Use of raw pointers

Not sure that is a flaw. Creating a container I would expect to see RAW pointers.

Overview

There is definitely a bug in your constructor where you build two Sentinels it should only be one. Otherwise your iterators for an empty list will iterate once.

Additionally your Node always contains a value (even for the Sentinel). This means your type T (the value type) must be default constructible (not all types are so you class is limited to objects of this type).

There are some requirements for Iterators that you don't implement. The iterator type is supposed to have a couple of internal types. The standard algorithms use these internal types (or they use std::iterator_traits<Your Interator>::UsefulTypeInfo) which default to point at your type object. Since your Iterator does not implement these types it may not be standard compliant and fail in some algorithms.

Talking of missing type information your container is also missing some type information.

Also you provide the pre-increment on your iterator but your don't provide the post-increment function. So you are missing at least one function. There is at least one more function you are missing (but I assume this is becausew your teacher has not got that far so I will leave it up to him).

There are lots of parts to this class that look like the teacher will get you to fill in at a later date. So there is still a lot of work to do to complete this task.

Code Review

That's a bit wierd.

        ~Linked_List() noexcept(false);

This makes the class act like a C++03 class. Exceptions are allowed to propagate out of the destructor. Not usual but it's OK. I assume this will be modified in future class.

---

I assume these are deleted to make the first version easy to write.

        Linked_List(const Linked_List&) = delete;
        Linked_List(Linked_List&&) = delete;
        Linked_List& operator=(const Linked_List&) = delete;
        Linked_List& operator=(Linked_List&&) = delete;

Probably come back in a later class and implement these.

---

This is a bit strange passing by value.

        void push_back(T);
        void push_front(T);

I would expect you to pass by reference to avoid a copy.

---

Personally I hate the unsigned int as a size value. But it's very common and what was adopted by the standard container (they regretted that).

        unsigned int size() const;

So I would keep it. But if you look up the history of why the standard committee choose unsigned then regretted it its an interesting story.

But saying that. I would use std::size_t as that conveys intentions more.

---

Return by value? Just like the insert by value you are potentially creating an unneeded copy.

        T back() const;
        T front() const;

I am now assuming this is because you have not been tought about references and thus the teacher will expand on this in later classes and show you how to provide both normal reference and const reference versions of these methods.

---

Sure this is fine as a starting point.

        Iterator begin() const;
        Iterator end() const;

But you will see that the standard containers have a lot more of these. Also since these methods are const should they not be returning a const version of the iterator. Maybe that is for a later class.

---

OK. A very basic Node.

    template<typename T>
    struct Linked_List<T>::Node
    {
        Node() : prev(nullptr), next(nullptr) {}
        Node(T t) : value(t), prev(nullptr), next(nullptr) {}
        Node* prev;
        Node* next;
        T value;
    };

But the lack of interesting constructors means you will have to do some manual work setting up the chain when this could have been done in the constructor here. I'll point it out when we get to creating a node.

---

OK so a very basic Iterator.

    template<typename T>
    struct Linked_List<T>::Iterator
    {
         // Nothing interesting here.
    };

---

You create a Sentinel for both both the beginning and end. That seems a bit strange. I would expect to only see one Sentinel value at the end.

    template<typename T>
    Linked_List<T>::Linked_List() : _size(0)
    {
        _head = new Node();
        _tail = new Node();
        _head->next = _tail;
        _tail->prev = _head;
    }

I would have expected this:

    template<typename T>
    Linked_List<T>::Linked_List()
        : _head(new Node)
        , _tail(_head)
        , _size(0)
    {}

This way if the list is empty both head and tail point at the same node. Thus if you generate iterators for head and tail they will both generate the end iterator (which will compare equal).

Additionally there is a bug in your version.

        _head = new Node();   // Assume this works
        _tail = new Node();   // Assume this fails and throws.
                              // Because your constructor has not finished
                              // when the exception is thrown this object
                              // will not be fully constructed and therefore
                              // will not have its destructor called. This 
                              // means you will leak the value pointed at by
                              // _head

---

Your destructor should work. But this is rather heavy handed. You are inside the class and thus are expected to understand the implementation details. You could write this much more simply and efficiently (as pop_back() has to make sure the chain stays valid after each call).

    template<typename T>
    Linked_List<T>::~Linked_List() noexcept(false)
    {
        while (!empty())
        {
            pop_back();
        }
        delete head;
        delete tail;
    }

I would simply write like this:

   Linked_List<T>::~Linked_List()
   {
       Node* current = _head;
       while(current != nullptr) {
            Node* old = current;
            current = current->next;
            delete old;
       }
   }

---

You know I mentioned above in the Node description that the constructor could be made more useful. This is where it would work nicely.

    Node(T value, Node* nextNode)
        : prev(nextNode->prev)
        , next(nextNode)
        , value(value)
    {
        if (prev) {
            prev->next = this;
        }
        next->prev = this; // There is always a next.
    }
    template<typename T>
    void Linked_List<T>::push_back(T t)
    {
        Node* n = new Node(t, tail);  // insert before tail.
        tail = n->next;
    }

    template<typename T>
    void Linked_List<T>::push_front(T t)
    {
        Node* n = new Node(t, head);  // insert before head
        head = n;
    }

Personally I think that is much easier to read.

---

Personally I would not check if it is empty. It is the responsibility of the caller to check before calling X_pop(). If you provide the check and it is not needed you are forcing the user to use sub-optimal code. See example below:

    template<typename T>
    void Linked_List<T>::pop_back()
    {
        if (empty()) throw Error("pop_back(): on empty list");
        Node* n = _tail->prev;
        _tail->prev->prev->next = _tail;
        _tail->prev = _tail->prev->prev;
        --_size;
        delete n;
    }

    template<typename T>
    void Linked_List<T>::pop_front()
    {
        if (empty()) throw Error("pop_front(): on empty list");
        Node* n = _head->next;
        _head->next->next->prev = _head;
        _head->next = _head->next->next;
        --_size;
        delete n;
    }

Here is a very common use case:

    while(list.empty()) {
         list.pop_back();    // This is guaranteed to only be called if
                             // if the list is not empty. So the check
                             // inside `pop_back()` is redudant and therefore
                             // a waste of cycles.
    }

One of the big philosophies of C++ is to never charge people for something they don't need. Now there is also an argument to having the check. BUT this can be provided by having an explicit checked pop_back() version: checked_pop_back().

    list.checked_pop_back(); // Do I need to make a check before this call?

---

Simply go for checking the size(). If your object is in a consistent state then you can simply check the variable without having to pay the expense of the functions call.

    template<typename T>
    bool Linked_List<T>::empty() const
    {
        //return (_head->next == _tail) && (_tail->prev == _head);
        return size() == 0;
    }

I would just write:

    bool Linked_List<T>::empty() const {return _size == 0;}

---

Again with the un-needed checks.

    template<typename T>
    T Linked_List<T>::back() const
    {
        if (empty()) throw Error("back(): on empty list");
        return _tail->prev->value;
    }

    template<typename T>
    T Linked_List<T>::front() const
    {
        if (empty()) throw Error("front(): on empty list");
        return _head->next->value;
    }

---

These look fine:

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::begin() const
    {
        // Though with the fix I suggested above this changes.
        return Iterator(_head->next);

        // If you only have the tail `Sentinel` this becomes
        return Iterator(_head);
    }

    template<typename T>
    typename Linked_List<T>::Iterator Linked_List<T>::end() const
    {
        return Iterator(_tail);
    }

---

I haven't yet figured out how to implement:

Iterator insert(const Iterator, T); Iterator erase(const Iterator);

If you have to insert before the iterator? Then you can simply implement like I did above:

Iterator insert(const Iterator iterator, T value) {
    Node* n = new Node(value, iterator->_current);
    return Iterator(n);
}

Lets assume erase returns the iterator to the next element.

Iterator erase(const Iterator iterator)
    Node* current = iterator->_current;
    if (current == _tail) // can't delete the tail
        return iterator;
    }

    // otherwise unlink from previous item.
    if (current->prev == nullptr) {
        head = current->next;
    }
    else {
        current->prev->net = current->next;
    }
    // Next unlink from the next item.
    current->next->prev=current->prev;

    // Get the next item so we can return it.
    Node* result = current->next;

    // Delete the old value.
    delete current;

    // return the new result.
    return Iterator(result);
}

Answer 2

Your Linked_List and your Iterator both should have a serial number to allow for fast failure of iterating over a list that is modified by something other than that iterator.

The Problem:

When you implement Iterator::remove, it has to hold on to a pointer just before (or just after or both) the node that was just removed. If that node is then removed by some means (direct call to Linked_List::pop_*() or removal by another iteration), the saved pointer will end up pointing to deallocated memory.

Solution:

Each change to the Linked_List should change the serial number (+= 1 works). Each time an Iterator is created, it should take a snapshot of the serial number. Before performing any operation with the Iterator, it should compare its copy of the serial number to the actual Linked_List serial number and raise an exception if they are different. When an Iterator is used to modify the Linked_List, the serial number will change and that Iterator should capture this new value.