Doubly linked list class in C++

Question

I would like some feedback regarding my doubly linked list implementation in C++. I have been programming in C++ for about a year and a half and consider myself fairly proficient in the language.

I know someone will say something about it, so I'm going to get it out of the way: Yes, I did use raw pointers for my implementation. I know about smart pointers, and I agree that they are the best choice in almost all situations. However, my goal here was to create a low-level data structure that is as time and space-efficient as possible. I used Valgrind to test my code for memory leaks and found absolutely none, even when working with lists composed of millions of nodes.

I would especially like feedback concerning good design principles, any additional functions I should add, and how I can use features of C++14 and C++17 to improve my implementation (yes, I know about std::list). Of course, if anyone finds bugs in the code, I would like to know that, too!

DLinkedList.hpp:

#ifndef DLINKEDLIST_HPP
#define DLINKEDLIST_HPP

#include <iostream>
#include <stdexcept>
#include <new>

template<typename T> class DLinkedList;  // forward declaration

template<typename T>
struct DNode
{
private:
    T val;
    DNode<T> *next, *prev;
    void *operator new(std::size_t size)
    {
        return ::operator new(size);
    }
    void operator delete(void *ptr) noexcept
    {
        ::operator delete(ptr);
    }

public:
    friend class DLinkedList<T>;
    explicit DNode(T val = {}, DNode<T> *next = nullptr, DNode<T> *prev = nullptr)
        : val(val), next(next), prev(prev) {}
};

template<typename T>
class DLinkedList
{
private:
    DNode<T> *head;
    DNode<T> *tail;
    bool srtd;         // the list is guaranteed to be sorted if true
    std::size_t sz;         // size of the list

    void mergesort(DNode<T> *&head_ref, std::size_t size);
    DNode<T> *merge(DNode<T> *head_left, DNode<T> *head_right, std::size_t right_size);

public:
    explicit DLinkedList(std::size_t num_elems = 0, const T &val = {});
    DLinkedList(const DLinkedList<T> &other);   // copy constructor
    DLinkedList(std::initializer_list<T> li);   // initializer list constructor
    ~DLinkedList() { delete_list(); }
    DLinkedList<T>& operator=(const DLinkedList<T> &other);  // copy assignment

    inline bool empty() const { return !head; }    // is the list empty?
    inline bool sorted() const { return srtd; }    // is the list sorted?
    void insert_before(DNode<T> *node, const T &val);
    void insert_after(DNode<T> *node, const T &val);
    void delete_node(DNode<T> *&node);
    void delete_list();
    inline void push_front(const T &val) { insert_before(head, val); }  // add node to front
    inline void pop_front() { auto node = head; delete_node(node); }   // remove node from front
    inline void push_back(const T &val) { insert_after(tail, val); }    // add node to back
    inline void pop_back() { auto node = tail; delete_node(node); } // remove node from back
    DNode<T>* search_from_front(const T &val) const;
    DNode<T>* search_from_back(const T &val) const;
    std::size_t count(const T &val) const;
    inline std::size_t size() const { return sz; }    // how many nodes in the list?
    void sort();
    void print_list(const char *delim = " ") const;
};

/* General constructor: can be used to create a list with
   any number of nodes, all with the same value. */
template<typename T>
DLinkedList<T>::DLinkedList(std::size_t num_elems, const T &val)
 : head(nullptr), tail(nullptr), srtd(num_elems <= 1), sz(0)
{
    for (std::size_t i = 0; i < num_elems; ++i)
        push_back(val);
}

/* Copy constructor: create a list as a copy of another. */
template<typename T>
DLinkedList<T>::DLinkedList(const DLinkedList<T> &other)
 : head(nullptr), tail(nullptr), sz(0)
{
    auto node = other.head;
    while (node)
    {
        push_back(node->val);
        node = node->next;
    }

    srtd = other.srtd;
}

/* Initializer list constructor: create a list from an initializer list. */
template<typename T>
DLinkedList<T>::DLinkedList(std::initializer_list<T> li)
 : head(nullptr), tail(nullptr), sz(0)
{
    for (const auto &x : li)
        push_back(x);
}

/* Copy assignment: assign a list to another list by copying it. */
template<typename T>
DLinkedList<T>& DLinkedList<T>::operator=(const DLinkedList<T> &other)
{
    if (&other == this)
        return *this;

    std::size_t this_size = sz, new_size = other.sz;
    auto node = head;
    auto node_other = other.head;

    while (this_size <= new_size ? node : node_other) // copy the values up to the smaller size
    {
        node->val = node_other->val;
        node = node->next;
        node_other = node_other->next;
    }

    if (this_size < new_size)  // current list size is less than or equal to new list size
    {
        while (node_other)
        {
            push_back(node_other->val);
            node_other = node_other->next;
        }
    }

    if (this_size > new_size)  // current list is larger than the new list
    {
        std::size_t size_diff = this_size - new_size;
        for (std::size_t i = 0; i < size_diff; ++i)
            pop_back();
    }

    srtd = other.srtd;
    return *this;
}

/* Insert before a node in the list. */
template<typename T>
void DLinkedList<T>::insert_before(DNode<T> *node, const T &val)
{

    if (empty())  // empty list
    {
        if (node == head)
        {
            head = tail = new DNode<T>(val);
            sz = 1;
            return;
        }
        else
        {
            throw std::invalid_argument("Invalid node pointer.");
        }
    }

    if (!node)
        throw std::invalid_argument("Non-empty list pointer can't be null.");

    ++sz;
    srtd = false;
    auto new_node = new DNode<T>(val, node, node->prev);
    node->prev = new_node;

    if (node == head)   // insert at front of list
    {
        head = new_node;
        return;
    }

    new_node->prev->next = new_node;
}

/* Insert after a node in the list. */
template<typename T>
void DLinkedList<T>::insert_after(DNode<T> *node, const T &val)
{

    if (empty())  // empty list
    {
        if (node == tail)
        {
            head = tail = new DNode<T>(val);
            sz = 1;
            return;
        }
        else
        {
            throw std::invalid_argument("Invalid node pointer.");
        }
    }

    if (!node)
        throw std::invalid_argument("Non-empty list pointer can't be null.");

    ++sz;
    srtd = false;
    auto new_node = new DNode<T>(val, node->next, node);
    node->next = new_node;

    if (node == tail)   // insert at back of list
    {
        tail = new_node;
        return;
    }

    new_node->next->prev = new_node;
}

/* Delete a node from the list. */
template<typename T>
void DLinkedList<T>::delete_node(DNode<T> *&node)
{
    if (empty())
        throw std::out_of_range("Can't delete from empty list.");
    if (!node)
        throw std::invalid_argument("Can't delete null pointer.");

    --sz;
    if (node == head && node == tail)  // list has one element
    {
        head = tail = nullptr;
        delete node;
        node = nullptr;
        return;
    }

    if (node == head)   // delete first element
    {
        head = node->next;
        node->next->prev = nullptr;
        delete node;
        node = nullptr;
        return;
    }

    if (node == tail)  // delete last element
    {
        tail = node->prev;
        node->prev->next = nullptr;
        delete node;
        node = nullptr;
        return;
    }

    node->next->prev = node->prev; // multi-element list where p is not the head or tail
    node->prev->next = node->next;
    delete node;
    node = nullptr;
}

/* Delete every node in the list. */
template<typename T>
void DLinkedList<T>::delete_list()
{
    auto node = head;
    while (node)
    {
        auto current = node;
        node = node->next;
        delete_node(current);
    }

    head = nullptr;
    tail = nullptr;
    srtd = true;  // an empty list is sorted
}

/* Search for a particular value in the list, starting
   from the front. */
template<typename T>
DNode<T>* DLinkedList<T>::search_from_front(const T &val) const
{
    auto node = head;
    while (node)
    {
        if (node->val == val)
            break;
        node = node->next;
    }

    return node;
}

/* Search for a particular value in the list, starting
   from the back. */
template<typename T>
DNode<T>* DLinkedList<T>::search_from_back(const T &val) const
{
    auto node = tail;
    while (node)
    {
        if (node->val == val)
            break;
        node = node->prev;
    }

    return node;
}

/* Count the number of occurrences of a particular
   item in the list. */
template<typename T>
std::size_t DLinkedList<T>::count(const T &val) const
{
    std::size_t num = 0;
    auto node = head;
    while (node)
    {
        if (node->val == val)
            ++num;
        node = node->next;
    }

    return num;
}

/* Sorts a list in ascending order. */
template<typename T>
void DLinkedList<T>::sort()
{
    if (srtd)  // don't sort a sorted list
        return;

    mergesort(head, sz);   // sort the entire list
    srtd = true;
}

/* Mergesort implementation for a linked list. Splits the
   list in half by declaring pointers to the head node and
   to a node halfway down the list. Recursively sorts
   the two halves, then merges the two halves using the
   merge function. */
template<typename T>
void DLinkedList<T>::mergesort(DNode<T> *&head_ref, std::size_t size)
{
    if (size <= 1)  // already sorted
        return;

    auto head_left = head_ref;
    auto head_right = head_ref;
    std::size_t split = size / 2;
    for (std::size_t i = 0; i < split; ++i)   // split the list
        head_right = head_right->next;

    mergesort(head_left, split);                // sort left half
    mergesort(head_right, size - split);        // sort right half
    head_ref = merge(head_left, head_right, size - split);  // merge the two halves
}

/* The merge function. Merges two sorted lists
   in place by rearranging the next and prev pointers
   of the nodes. */
template<typename T>
DNode<T>* DLinkedList<T>::merge(DNode<T> *head_left, DNode<T> *head_right, std::size_t right_size)
{
    if (!head_left || !head_right)
        return head_left;

    auto new_left = head_left;  // keep track of the leftmost node

    /* Explanation of the following while loop conditions:
       1. right_size keeps track of the number of unmerged nodes
          in the right sublist. When right_size == 0, the last node
          to be merged was in the right sublist and the sublists
          have been merged.
       2. If head_left == head_right, then all the nodes in the
          left sublist have been merged. Since the right sublist is
          already sorted, the merging is now complete. */
    while(right_size && (head_left != head_right))
    {
        /* When the next node to be merged is from the
        left sublist, simply move the head_left pointer
        to the next node. */
        if (head_left->val <= head_right->val)
        {
            head_left = head_left->next;
        }

        /* When the next node to be merged is from the
        right sublist, put that node in front of the
        node pointed to by head_left. */
        else
        {
            --right_size;
            auto current = head_right;          // the node currently being moved
            head_right = head_right->next;      // point to the next node to be merged

            // remove the node
            current->prev->next = current->next;
            if (current->next)
            {
                current->next->prev = current->prev;
            }
            else    // last node in list
            {
                tail = current->prev;
            }

            // insert the node
            current->prev = head_left->prev;
            current->next = head_left;
            if (head_left == new_left) // move in front of first node in left sublist
            {
                new_left = current;
            }
            if (head_left->prev)
            {
                head_left->prev->next = current;
            }
            head_left->prev = current;
        }
    }

    return new_left;    // update leftmost node pointer
}

/* Print the list with an optional delimiter. */
template<typename T>
void DLinkedList<T>::print_list(const char *delim) const
{
    if (empty())
    {
        std::cout << "Can't print empty list." << std::endl;
        return;
    }

    auto node = head;
    std::cout << node->val;
    while (node->next)
    {
        node = node->next;
        std::cout << delim << node->val;
    }

    std::cout << std::endl;
}

#endif

I will also include two drivers that I used to test the code.

main.cpp:

#include "DLinkedList.hpp"
#include <iostream>
#include <random>
#include <chrono>
#include <iomanip>

using std::cout;
using std::endl;

int main()
{
    DLinkedList<int> list1;

    for (int i = 0; i < 10; ++i)
    {
        list1.push_back(i * 2);
    }
    list1.print_list();

    list1.push_front(-2);
    list1.print_list();

    auto loc_four = list1.search_from_front(4);
    if (loc_four)
    {
        list1.delete_node(loc_four);
    }
    list1.print_list();

    auto loc_six = list1.search_from_front(6);
    if (loc_six)
    {
        list1.delete_node(loc_six);
    }
    list1.print_list();
    cout << "Size of the list: " << list1.size() << endl;

    list1.pop_front();
    list1.pop_back();
    list1.print_list();

    auto loc_twelve = list1.search_from_front(12);
    if (loc_twelve)
    {
        list1.insert_after(loc_twelve, 12);
    }
    list1.print_list();
    cout << "Number of 12's: " << list1.count(12) << endl;

    list1.delete_list();
    list1.print_list();
    cout << "Size of empty list: " << list1.size() << endl;

    DLinkedList<int> list2;
    const int num_nodes = 10000000;
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<> dist {0, num_nodes};
    for (int i = 0; i < num_nodes; ++i)
    {
        list2.push_back(dist(mt));
    }

    auto start = std::chrono::high_resolution_clock::now();
    list2.sort();
    auto stop = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> time = stop - start;
    cout << endl << "Time to sort " << num_nodes << " nodes: " << std::fixed << std::setprecision(3)
         << time.count() << " ms";
}

main2.cpp:

#include "DLinkedList.hpp"

int main()
{
    DLinkedList<int> list1;
    for (int i = 0; i < 20; ++i)
        list1.push_back(i);

    auto list2 = list1;
    list2.print_list();

    DLinkedList<int> list3;
    for (int i = 0; i < 40; ++i)
        list3.push_front(i);

    list2 = list3;
    list2.print_list();
    list2.sort();
    list3 = list2;
    list3.print_list();
    list3 = list1;
    list3.print_list();

    DLinkedList<int> list4 {1,3,5,7,9,11,13,15};
    list4.print_list();

    DLinkedList<int> list5(9, 37);
    list5.print_list();
}

Answer 1

However, my goal here was to create a low-level data structure that is as time and space-efficient as possible.

You don’t realize that unique_ptr is a zero-overhead abstraction. It does not add any size beyond the pointer being wrapped, and it does nothing but make sure you don’t call certain things, and handles the destructor which is code you need to supply anyway.

Try it. Really.

---

#ifndef DLINKEDLIST_HPP
#define DLINKEDLIST_HPP

Also, use #pragma once. And pick a name for the symbol here that you know will never clash with anything else in the project including other third-party libraries. That is, use a UUID.

---

template<typename T> class DLinkedList;  // forward declaration

Yes, I can see that this ends in a semicolon without a body. Comments should be meaningful, not just add noise to the file.

---

DNode<T> *next, *prev;

The style in C++ is to put the * or & with the type, not the identifier. This is called out specifically near the beginning of Stroustrup’s first book, and is an intentional difference from C style.

And, don’t define more than one symbol at a time.

But really, as noted above, it should be

unique_ptr<D> next;
D* prev;  // back-pointer is non owning

---

void *operator new(std::size_t size)
{
    return ::operator new(size);
}
void operator delete(void *ptr) noexcept
{
    ::operator delete(ptr);
}

I have not seen this in a while — a class-specific new/delete. But what is the point here? It just calls the global one.

Since this class is exposed, users could declare things of this type in other ways. So always supply the array form of new/delete as well. And, operator delete can take a size parameter now, too.

---

The DNode is not meant to be used alone or for anything else, right? So make it nested inside of DLinkedList.

---

explicit DNode(T val = {}, DNode<T> *next = nullptr, DNode<T> *prev = nullptr)
    : val(val), next(next), prev(prev) {}

Use the uniform initialization syntax for the member initializers, too.

    : val{val}, next{next}, prev{prev} {}

(BTW, good for using nullptr and for using uniform initialization syntax for some things.)

The val is a sink parameter, so you can take by value (which you are) but also use move.

 : val{std::move(val)}

But... this is meant to be used internally when creating nodes to insert values. You know where it is being called and how. So use an rvalue reference to avoid copying it here.

Likewise, the insert should take by value and “sink” it deeper in its own call to construct the node. If done right, the parameter you pass is only copied once, directly into the newly-allocated node, with intermediate locations being completely elided.

Considering the inherent slowness of linked lists, thus they are only used in a few special cases including when T is large and/or expensive to copy. So make your implementation handle that specific case especially well! Allow emplace insertion to construct directly in the final node location.

---

void print_list(const char *delim = " ") const;

Make this a non-member free function. It can be written without any private knowledge of the class. In fact, it is so simple to write that I wonder why it needs to be specific to this list class at all, rather than working with any kind of collection or range!

template<typename Collection>
void print_collection (const Collection& cl, string_view delim = " ")
{
    for (auto item : cl) {
        cout << cl << delim
    }
    // plus usual headache of not printing an extra delimiter, which
    // should be a reusable pattern of some kind itself!!
}

Hmm, I don’t see public begin, cbegin, end, cend. So your list will not work with any of the reusable algorithms and other templates or the built-in range-for loop. Why not?

---

The insert_before and insert_after functions are nearly the same. They should share a common bottom half at the very least; and the top half is identical in both? That would be a no-brainer to move to a helper function.

Answer 2

It seems to me that move semantics would be valuable for a linked list, so that you can avoid copying the whole list when you could just copy two pointers and values. Since you have a custom destructor and copy constructor/assignment operator, you'd need to add the move constructor/assignment operator manually as well.

In insert_before you mark the list as not sorted. That's a reasonable decision, but it may be worth checking whether you've put it in the right place. Similarly, it would seem not out of place in this class to have some sort of insert_sorted or search_first_larger functionality to expressly facilitate maintaining the sorted invariant.

Also about sorting, it may be worth considering element types that cannot be compared and therefore cannot be sorted, even if just to provide more helpful error messages.

if (empty())
{
    std::cout << "Can't print empty list." << std::endl;
    return;
}

I disagree. An empty list isn't really a special case as far as printing is concerned. Even if it were, printing a complaint would probably not be the way to handle that case!

/* General constructor: can be used to create a list with
any number of nodes, all with the same value. */

This does not seem very useful to me, because the value stored in each node is private and seemingly immutable. It would only be really useful if you actually want a list of the same thing over and over, in which case a linked list is probably overkill.

Similarly, perhaps I'm missing something as the code is quite long, but I can't see any way to actually extract the values stored in the list.

There isn't much else that sticks out to me that JDlugosz has not already said. I do disagree with JDlugosz about unique_ptr being preferable here, but there's a lot of other helpful points in that answer.

Answer 3

Why does print_list() write to std::cout? It's very limiting if it can't write to any other stream.

Worse still, if it produces an error, it's indistinguishable from a legitimate output. Error messages should go to std::cerr - or better, in a library, be communicated back to the calling program (e.g. via exceptions). In this case, an empty list seems like quite a reasonable thing to want to see.

Also, a library function like this has no business flushing its output stream with std::endl. Print a plain newline, and let the caller decide if the stream should be flushed.