4
\$\begingroup\$

This is a working but very simple doubly linked list. I wrote it to get more familiar with certain language concepts and because I've never made one in C++. (For convenience reasons this is not split into separate files for declaration/definition)

Things I'm mainly interested in:

  • Is the overall implementation correct?

  • Are the various constructors/operators implemented correctly? I'm still not very sure about these so this is an important concern.

  • How is const usage?

  • Where, if possible, can constexpr be used to make this more robust?

  • Is this well written/easy to read? What could be improved to make it better in that regard?

and anything else you notice.

Code:

#include <iostream>
#include <cassert>
#include <initializer_list>
#include <utility>

template<typename T>
class DoublyLinkedList {
public:
    DoublyLinkedList()
        : head{nullptr}
        , tail{nullptr}
        , list_size{0}
    {}

    DoublyLinkedList(std::initializer_list<T> init_list)
        : DoublyLinkedList{}
    {
        for (auto const& value : init_list) {
            push_back(value);
        }
    }

    DoublyLinkedList(DoublyLinkedList const& rhs)
        : DoublyLinkedList{}
    {
        Node* node = rhs.head;
        while (node) {
            push_back(node->data);
            node = node->next;
        }
    }

    DoublyLinkedList(DoublyLinkedList&& rhs) noexcept
        : head{rhs.head}
        , tail{rhs.tail}
        , list_size{rhs.list_size}
    {
        rhs.head = nullptr;
        rhs.tail = nullptr;
        rhs.list_size = 0;
    }

    ~DoublyLinkedList() noexcept {
        clear();
    }

    DoublyLinkedList& operator=(DoublyLinkedList const& rhs) {
        DoublyLinkedList tmp(rhs);
        *this = std::move(tmp);
        return *this;
    }

    DoublyLinkedList& operator=(DoublyLinkedList&& rhs) noexcept {
        if (this == &rhs) {
            return *this;
        }

        clear();

        head = rhs.head;
        tail = rhs.tail;
        list_size = rhs.list_size;

        rhs.head = nullptr;
        rhs.tail = nullptr;
        rhs.list_size = 0;

        return *this;
    }

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

    int const& size() const {
        return list_size;
    }

    void clear() {
        Node* node = head;
        while (node) {
            Node* delete_this = node;
            node = node->next;
            delete delete_this;
        }

        head = nullptr;
        tail = nullptr;

        list_size = 0;
    }

    void push_front(T const& value) {
        if (!head) {
            head = new Node{nullptr, nullptr, value};
            tail = head;
        }
        else {
            head->prev = new Node{head, nullptr, value};
            head = head->prev;
        }

        ++list_size;
    }

    void push_back(T const& value) {
        if (!tail) {
            push_front(value);
            return;
        }

        tail->next = new Node{nullptr, tail, value};
        tail = tail->next;

        ++list_size;
    }

    void insert_after(int const& position, T const& value) {
        int i = 0;
        Node* node = head;
        while (node) {
            if (i++ == position) {
                Node* new_node = new Node{node->next, node, value};
                new_node->next->prev = new_node;
                node->next = new_node;
                ++list_size;
                return;
            }
            node = node->next;
        }
    }

    void erase(int const& position) {
        if (position <= 0) {
            pop_front();
            return;
        }

        if (position >= list_size - 1) {
            pop_back();
            return;
        }

        int i = 1;
        Node* node = head->next;
        while (node) {
            if (i++ == position) {
                node->prev->next = node->next;
                node->next->prev = node->prev;
                delete node;
                --list_size;
                return;
            }
            node = node->next;
        }
    }

    void pop_front() {
        if (head->next) {
            Node* node = head->next;
            delete head;
            head = node;
            head->prev = nullptr;
        }
        else {
            delete head;
            head = nullptr;
            tail = nullptr;
        }
        --list_size;
    }

    void pop_back() {
        if (tail->prev) {
            Node* node = tail->prev;
            delete tail;
            tail = node;
            tail->next = nullptr;
        }
        else {
            delete tail;
            tail = nullptr;
            head = nullptr;
        }
        --list_size;
    }

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

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

    int find_first_of(int const& start, T const& value) const {
        if (start < 0 || start >= list_size - 1) {
            return -1;
        }

        int position = 0;
        Node* node = head;
        while (node) {
            if (node->data == value && position++ >= start) {
                return position;
            }
            node = node->next;
        }

        return -1;
    }

private:
    struct Node {
        Node(Node* n, Node* p, T d)
            : next{n}
            , prev{p}
            , data{d}
        {}

        Node* next;
        Node* prev;
        T data;
    };

    Node* head;
    Node* tail;
    int list_size;
};

int main() {
    DoublyLinkedList<int> dll{1, 2, 3};
    assert(dll.size() == 3);

    assert(dll.find_first_of(0, 2) == 1);

    dll.erase(1);
    assert(dll.size() == 2);

    dll.pop_front();
    assert(dll.size() == 1);

    dll.pop_back();
    assert(dll.size() == 0);
    assert(dll.is_empty());

    dll.push_back(1);
    assert(dll.size() == 1);
    assert(!dll.is_empty());

    dll.push_back(1);
    assert(dll.size() == 2);

    dll.insert_after(0, 3);
    assert(dll.find_first_of(0, 3) == 1);
}
\$\endgroup\$
3
\$\begingroup\$
  • push_front can be streamlined. The new node will become a head no matter what, and its next will point the old head no matter what, so consider

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

    (Same applies to push_back).

  • Same technique applies to pop_front and pop_back, e.g.:

    void pop_front()
    {
        Node * node = head;
        head = head->next;
        delete node;
        if (head) {
            head->prev = nullptr;
        } else {
            tail = nullptr;
        }
        --list_size;
    }
    
  • I don't see the value of push_back calling push_front.

  • OTOH, clear should call pop_front, just like constructors call push_back.

  • Using int as a position is dangerous and limiting. Consider size_t.

  • insert_after, erase, and find_first_of would benefit from the private Node * at(size_t position) utility method.

  • The list sorely misses iterators. Once they are implemented, an entire <algorithm> library is to your service for free.

  • I don't follow why an int parameter is passed by a reference.

\$\endgroup\$
  • \$\begingroup\$ I looked at several ways to implement STL compatible iterators none of them were complete. Do you happen to have a good introduction to this topic? \$\endgroup\$ – yuri Apr 5 '18 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.