C++ linkedlist with static next/prev pointers

Question

I did huge review of linkedlist implementations and all of them include separate new call fornode part for entry, which has *next and T* entry values.

As a person with strong C knowledge, I know what memory fragmentation means and I want to avoid too many dynamic allocations using new keyword. Application will be for embedded systems and as a first part, I have my own new and delete operators, overloaded.

I want that my linkedlist node is part of my class, thus I created some test code. I'm not expert in C++ and I want you to take a look into the code and tell me if this code even makes any sense.

Idea is like this:

• There is one template class LinkedListRoot which holds information about first, last entries and count as number of elements on a list. To add a new entry to list, you have to call add method of root entry.
• There is second template class LinkedListNode which holds information about next element on a list, prev element on linked list and pointer to actual entry. I don't want to dynamically allocate this for every entry, but I want that this is already part of entry when I allocate entry itself.
• Then I have a Widget class which uses linkedlist approach, and class also has LinkedListRoot class which allows me that each widget has children widgets.

I did LinkedList.hpp file:

#pragma once

//Node class
template <typename T>
class LinkedListNode {
public:
    LinkedListNode<T>* prev;
    LinkedListNode<T>* next;
    T* entry;

    //Constructors
    LinkedListNode() {}
    LinkedListNode(T* t) {
        entry = t;
    }

    //Get next node of current node
    LinkedListNode<T>* get_next(void) {
        return next;
    }

    //Get node class
    T* get(void) {
        return entry;
    }
};

//Root class, holding first and last entry
template <typename T>
class LinkedListRoot {
public:
    LinkedListNode<T>* first;
    LinkedListNode<T>* last;
    size_t count;

    //Default constructor
    LinkedListRoot() {
        first = nullptr;
        last = nullptr;
        count = 0;
    }

    //Add new node to root list, put it to the end
    void add(LinkedListNode<T>* node) {
        node->next = nullptr;

        if (first == nullptr || last == nullptr) {
            node->prev = last;
            first = node;
            last = node;
        } else {
            node->prev = last;
            last->next = node;
            last = node;
        }
        count++;
    }

    //Get number of entries
    size_t getCount() const {
        return count;
    }

    //Get first entry
    LinkedListNode<T>* get_first() {
        return first;
    }
};

After that, I have a widget class which accepts parent widget on constructor and adds widget to parents' linked list (if parent is available):

#pragma once

#include "linkedlist.hpp"

//Class uses base class as I want LinkedListNode is 
//included in single new operator call
class Widget: public LinkedListNode<Widget> {
public:
    float x, y, width, height;
    Widget* parent;

    //List of children widgets
    LinkedListRoot<Widget> children;

    //Empty constructor
    Widget() { }

    //Add new child widget to current widget
    void add_child(Widget* widget) {
        //Add to children linkedlistroot
        children.add(widget);
    }

    //For constructor call parent constructor too
    //and give pinter to current class
    Widget(Widget* parent_widget):LinkedListNode(this) {
        parent = parent_widget;
        if (parent != nullptr) {
            parent->add_child(this);
        }
    }
};

And I use this code in the main. Please pay attention to print_list function

#include "stdafx.h"
#include "stdint.h"
#include "stdlib.h"
#include "widget.hpp"

//Root list of widgets
LinkedListRoot<Widget> widgets;

//3 widgets, window1 and window2 should be children of base
Widget *base;
Widget *window1;
Widget *window2;

//Debug widgets
void
print_list(LinkedListRoot<Widget>* top) {
    static int deep = 0;

    //If no top widget, use default one
    if (top == nullptr) {
        top = &widgets;
    }

    //Check if widgets available
    if (top->getCount()) {
        //It doesn't look perfect this for loop arguments
        for (Widget* w = top->get_first()->get(); w != nullptr; w = w->get_next()->get()) {
            //Print tree level and width
            printf("%d: Width: %d\r\n", (int)deep, (int)w->width);

            deep++;
            print_list(&w->children);
            deep--;
        }
    }
}

int main() {
    //Create base widget without parent
    base = new Widget(nullptr);
    base->width = 10;
    //Since we have no parent, manually add widget to root linkedlist
    widgets.add(base);

    //Create 2 windows and set base as parent
    window1 = new Widget(base);
    window1->width = 20;
    window2 = new Widget(base);
    window2->width = 30;

    //Debug widgets
    print_list(nullptr);

    return 0;
}

And it outputs result which seems ok:

0: Width: 10
1: Width: 20 <-- This one is children of first one
1: Width: 30 <-- This one is on same level as one top, children of first one

Is this a good approach at all? Did I miss a point of C++ doing it this way? Is there better solution?

Answer 1

T* get(void) {

Using (void) for an empty parameter list is, to quote Stroustrup, “an abomination”. C++ has had declared argument types from the beginning and has no need for a backward compatibility hack to distinguish an empty parameter list from an absent parameter list.

I don’t see why you need a trivial get_next when next is already public.

---

//Default constructor
LinkedListRoot() {
    first = nullptr;
    last = nullptr;
    count = 0;
}

You should put all of those as default initializers inline in the class definition, and you don’t need to write this constructor at all. If you were to need a constructor, use initialization of members, not assignment in the body of the function.

No copy constructor or destructor or assignment operator? See “Rule of 5”

---

    if (first == nullptr || last == nullptr) {

Don’t write explicit tests against nullptr. Use the contextual bool supplied by that type or class (of smart pointer).

Two out of three lines in your two blocks are the same. So only make the difference conditional.

auto& successor= (!first || !last) ? first : last->next;
node->prev = last;
successor = node;
last = node;

---

class Widget: public LinkedListNode<Widget> {

So you are deriving from the linked list stuff; the payload is part of the same object, as I would have thought from your description initially. So then why do you have:

template <typename T>
class LinkedListNode {
public:
      ⋮
    T* entry;

?

The get function is unnecessary since you have the object already — what you are calling get on! What you need are for the way to access the contents of the list (how would you do that?) to return the object downcast to the proper type.

By how you access the contents, you are exposing get_first and get_next (not at all abstracting the nature of the collection) so they should have return values that become Widget* rather than LinkedListNode<Widget>*.

Also, you need separate const-preserving versions of the accessing functions.

---

You write:

base = new Widget(nullptr);

which is a “naked new”. But I also wonder why Widget doesn’t simply work with nullptr as a default. Looking at the class, I see there is a separate “Empty constructor” but it is broken and does not work as a default constructor. In fact, since it does not initialize the base class, I don’t see how you could use it at all if constructed this way.

You also don’t have copy constructor etc.

---

Summary

• Write classes with complete “housekeeping” value semantics. What happens if the instance is assigned to another, or passed by value? Constructors that are present must result in a properly working object, not a time bomb. Look into “Rule of 5”.

• Look into the “Curiously Recurring Template Pattern” (CRTP).