Doubly linked std::list simple implementation

Question

I've implemented a simple doubly linked list structure. I would appreciate all criticism relevant to code, style, flow, and so forth.

How to implement end iterator and pop_back/pop_front properly? Where memory may leak?

P.S.I didn't make it template, because this is simple version version.

#include <cstddef>
#include <iterator>

using T = int;

class List {
/// Nodes
public:
    class Node {
    public:
        T data;
        Node *next;
        Node *prev;

    public:
        explicit Node(Node *next_, Node *prev_) : next(next_), prev(prev_) {}

        explicit Node(const T &_data, Node *next_, Node *prev_) :
                data(_data), next(next_), prev(prev_) {}

        ~Node() {}
    };
///

/// Iterators
public:
    class Iterator : public std::iterator<std::bidirectional_iterator_tag, T> {
    public:
        Node *position;
        Node *tail;

    public:
        Iterator(Node *node) : position(node) {}

        Iterator(Node *node, Node *_tail) : position(node), tail(_tail) {
        }

        Iterator &operator++() noexcept {
            position = position->next;
            return *this;
        }

        Iterator operator++(int) noexcept {
            auto old = *this;
            position = position->next;
            return old;
        }

        Iterator &operator--() noexcept {
            if (position == nullptr) position = tail;
            else
                position = position->prev;
            return *this;
        }

        Iterator operator--(int) noexcept {
            auto old = *this;
            if (position == nullptr) position = tail;
            else
                position = position->prev;
            return old;
        }

        T &operator*() const noexcept {
            return (position->data);
        }

        bool operator!=(Iterator other) noexcept {
            return position != other.position;
        }

        bool operator==(Iterator other) noexcept {
            return position == other.position;
        }


        ~Iterator() {}
    };
///

/// list
private:
    Node *head = nullptr;
    Node *tail = nullptr;
    size_t size_ = 0;

public:
    List() {}

    void push_back(const T &_data) {
        Node *node = new Node(_data, nullptr, tail);
        if (tail != nullptr) {
            node->prev = tail;
            tail->next = node;
            tail = node;
        } else {
            head = tail = node;
        }
        ++size_;
    }

    void push_front(const T &_data) {
        Node *node = new Node(_data, head, nullptr);
        if (head != nullptr) {
            head->prev = node;
            node->next = head;
            head = node;
        } else {
            head = tail = node;
        }
        ++size_;
    }

    void pop_back() {
        tail = tail->prev;
        if (tail != nullptr) {
            tail->next = nullptr;
        }
        --size_;
    }

    void pop_front() {
        head = head->next;
        if (head != nullptr) {
            head->prev = nullptr;
        }
        --size_;
    }


    size_t size() {
        return size_;
    }

    size_t size() const {
        return size_;
    }

    Iterator begin() {
        return Iterator(head, tail);
    }

    Iterator begin() const {
        return Iterator(head, tail);
    }

    Iterator end() {
        Iterator iter(nullptr, tail);
        return iter;
    }

    Iterator end() const {
        Iterator iter(nullptr, tail);
        return iter;
    }

    bool empty() const {
        return head == nullptr;
    }

    ~List() {
        Node * tmp = nullptr;
        while (head)
        {
            tmp = head;
            head = head->next;
            delete tmp;
        }
        head = tail = nullptr;
    }
};

Answer 1

My favorite container the list. Even doubly linked to make it more fun.

Issues in your current code.

You don't implement the rule of three/five.

Any class that manages resources needs to correctly implement the rule of three (optionally the rule of five). Otherwise you will have issues because of the compiler generated methods.

If you do not define them the compiler will generate the following methods:

• Default Constructor
• Copy Constructor
• Copy Assignment operator

Under some situations it will also generate

• Move Constructor
• Move Assignment operator

Because of the default implementation of these methods a class that "Owns" a pointer will not work as you expect. Note: Owns means that the destructor will delete it. But the general rule is if you define the destructor or any of the above operators you must define them all.

If we look at your current implementation:

{
    List   data;         // List one
    data.push_back(5);

    List   data2(data);  // This is not a copy of data.
                         // Internally this has the same pointers
                         // as data.
}
// Here you get a double delete
// Both destructors will delete the same pointer.

There are simple implementations for most of these.

List& operator=(List const& rhs)
{
    List copy(rhs);          // use the copy and swap idiom
    copy.swap(*this);
    return *this;
}
List(List&& rhs)    noexcept
    : head(nullptr)
    , tail(nullptr)
    , size_(0)
{
    rhs.swap(*this);     // Move construct: Simply swap the data
}
List& operator=(List&& rhs)    noexcept
{
    rhs.swap(*this);     // Move assignment: Simply swap the data
    return *this;        // the return.
}
void swap(List& other)    noexcept
{
    using std::swap;
    swap(head,   other.head);
    swap(tail,   other.tail);
    swap(size_,  other.size_);
}
// The only one that is hard is the copy constructor.
List(List const& rhs)
    : head(nullptr)
    , tail(nullptr)
    , size_(0)
{
    // But since you have iterators defined.
    // that makes it relatively easy.
    for(T const& value: rhs) {
        push_back(value);
    }
}
    

Your implementation is fine. But there is another technique. If you list is circular (head joined to tail) and you add a sentinel node (a marker node at the head/tail that is always there). Then the actual implementation becomes a lot easier because there is no longer any need to check for null (because there is always a sentinel).

void push_back(const T &_data)
{
    new Node(_data, sent, sent->prev);
    ++size_;
}

void push_front(const T &_data)
{
    new Node(_data, sent->next, sent);
    ++size_;
}

Node::Node(T const& data, Node* next, Node* prev)
    : data(data)
    , next(next)
    , prev(prev)
{
    prev->next = this;
    next->prev = this;
}

void pop_back()
{
    if (size > 0) {
        delete sent->prev;
        --size_;
    }
}
void pop_front()
{
    if (size > 0) {
        delete sent->next;
        --size_;
    }
}

Node::~Node()
{
    prev->next = next;
    next->prev = prev;
}

Next you always copy the objects into the list. That's fine but you should also think about moving objects into the list and emplacing them (building them in place).

void push_back(T const& copy);     // You have this.
void push_back(T&& move);          // Move into the list
template<typename... Args>
void emplace_back(Args...&& args); // Build in-place

You don't need two version of size.

// This version is not necessary.
// The const version will work in all situations.
size_t size() {     
    return size_;
}

size_t size() const {
    return size_;
}

Youre const methods for getting iterators does not return the correct type.

Iterator begin() const {
    return Iterator(head, tail);
}

Iterator end() const {
    Iterator iter(nullptr, tail);
    return iter;
}

Technically you can still use the iterators returned to modify the object. So these should not really callable from a const version of the object. From the const version of begin() and end you should return a const version of the iterator that allows you to read the container but not write to it.

While we are on iterators you should also add cbegin() and cend() that always return const iterators.

Answer 2

Take care to be explicit about compiler generated functions

Effectively your List class violates the Rule of Three/Five/Zero, thus the compiler generated copy/move constructors will create unexpected side effects by implementing a shallow copy mechanism.

Let's suppose you have code like

int main() {
    List l1;
    List l2;

    l1.push_back(5);
    l1.push_back(42);
    l1.push_back(21);

    l2 = l1; // Copy the list
    *l1.begin() = 80; // Change the original list

    for(auto value : l2) {
        std::cout << value << std::endl;
    }
}

The output is

80
42
21

I doubt you really intended that. See the Live Demo please.

Why not making your class a template?

using T = int;

looks strange.

Why not making the List class a template like

template<typename T>
class List {
    // ...
};

Compiles and works the same way here

Prefer smart pointers instead of raw pointers

You should prefer using smart pointers instead of managing new and delete yourself.

I have evolved the demo from above with changing the relevant parts

class Node;
class Node {
public:
    T data;
    std::shared_ptr<Node> next;
    std::shared_ptr<Node> prev;

public:
    explicit Node(std::shared_ptr<Node> next_, std::shared_ptr<Node> prev_) : next(next_), prev(prev_) {}

    explicit Node(const T &_data, std::shared_ptr<Node> next_, std::shared_ptr<Node> prev_) :
            data(_data), next(next_), prev(prev_) {}

    ~Node() {}
};

---

class Iterator : public std::iterator<std::bidirectional_iterator_tag, T> {
public:
    std::weak_ptr<Node> position;
    std::weak_ptr<Node> tail;

public:
    Iterator(std::shared_ptr<Node> node) : position(node) {}

    Iterator(std::shared_ptr<Node>node, std::shared_ptr<Node>_tail) : position(node), tail(_tail) {
    }

    Iterator &operator++() noexcept {
        position = position.lock()->next;
        return *this;
    }

    Iterator operator++(int) noexcept {
        auto old = *this;
        position = position->next;
        return old;
    }

    Iterator &operator--() noexcept {
        if (position == nullptr) position = tail;
        else
            position = position->prev;
        return *this;
    }

    Iterator operator--(int) noexcept {
        auto old = *this;
        if (position == nullptr) position = tail;
        else
            position = position->prev;
        return old;
    }

    T &operator*() const noexcept {
        return (position.lock()->data);
    }

    bool operator!=(Iterator other) noexcept {
        return position.lock().get() != other.position.lock().get();
    }

    bool operator==(Iterator other) noexcept {
        return position.lock().get() == other.position.lock().get();
    }


    ~Iterator() {}
};

Solve the shallow copy problem

As mentioned in my 1st point you have a problem with The Rule of Three/Five. Your List class will be shallow copied. So you should provide the relevant operations.
This will be a lot easier using smart pointers as mentioned in my previous point

List(const List<T>& rhs) {
    copy(rhs);
}

List(List<T>&& rhs) {
    move(std::move(rhs));
}

List& operator=(const List<T>& rhs) {
    copy(rhs);
    return *this;
}

List& operator=(List<T>&& rhs) {
    move(std::move(rhs));
    return *this;
}


void copy(const List<T>& rhs) {
    clear();
    for(auto value : rhs) {
        push_back(value);
    }
}

void move(List<T>&& rhs) {
    head = std::move(rhs.head);
    tail = std::move(rhs.tail);
}

void clear() {
    std::shared_ptr<Node> temp = head;
    std::shared_ptr<Node> next;
    do {
        if(temp) {
            next = temp->next;
        }
        temp = nullptr;
    } while(next);
}

~List() {
}

Output is as expected for the example mentioned in the 1st paragraph:

5
42
21

Again you can check the improved code here.