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?

• user1118321: I'm surprised this compiles: class Widget: public LinkedListNode<Widget>. I don't understand what that would mean conceptually. A Widget is a linked list node of type Widget? Isn't that a circular definition?
• unalignedmemoryaccess: Since linkedlist node is template, I assume you need type. Am I wrong? Cirxular definition is not as linkedlist node has only pointers.
• user1118321: Yes, you need a type. By circular I meant that the type is defined in terms of the type. It must have some use, as it compiles just fine, but its meaning is far from obvious to me.
• unalignedmemoryaccess: @user1118321 thanks for letting me know. Trying to remove it, I have compilation errors, so seems like it should be there. The rest seems ok? With this approach I can achieve that new is only called for Widget class and not second one for LinkedListNode class.
• user1118321: I'm unable to comment on the rest because I don't understand the declaration. Sorry!

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).

• unalignedmemoryaccess: I updated my question and I removed T * entry from LinkedListNode class which is base of Widget class. Now I'm using cast from base class to get Derived class.
• unalignedmemoryaccess: I see now. I checked on web a little, I can use static_cast and return derived class from base one. Testing, it works as expected, probably due to CRTP.
• fievel: Hello, can you detail this point: "Don’t write explicit tests against nullptr."? I find code with explicit nullptr check more readable and the test purpose is clearer in this case in my opinion.
• JDługosz: You are not supposed to edit the code once you have received answers. In my experience, even correcting typos or comments is rolled back by the moderators.
• JDługosz: re more readable: That’s because you are not internalizing the idioms yet. To experienced C++ people, seeing the ==nullptr is an extra cognative detour in the same way that it generated extra (unnecessary) code prior to C++11. (That extra code can go away if the class is outfitted with four extra operators for this exact purpose, but we don’t write those because the idiom is not to do that. Consider the use in guarding before dereference: if (p && p->needs_service()) is clearly "guarding against the real thing we want to test" as opposed to two separate tests that must be gasped.