Constructing Nodes of a Hand-made Linked List, How Hard Can it Be? -- Raymond Chen

When designing a circular doubly-linked list, the initial challenge is determining how to manage the construction of new nodes in relation to existing ones. While constructors seem like a natural fit for placing nodes before or after a given node, overloading them can lead to ambiguity and poor design choices. Instead, using distinct tag types or factory methods provides clearer intent, ensuring flexibility while respecting the constraints of guaranteed copy elision for node addresses.

Constructing Nodes of a Hand-made Linked List, How Hard Can it Be?

by Raymond Chen

From the article:

Suppose you are writing your own circular doubly-linked list structure.

struct node
{
    node* prev;
    node* next;
};

A natural choice for the default constructor is to make the node the sole element of a circular doubly-linked list.

struct node
{
    node* prev = this;
    node* next = this;
};

What if you also want to add a node after an existing node? Well, we could add a constructor for that.

struct node
{
    node* prev = this;
    node* next = this;

    node() = default;

    // Construct a node after a specific node
    node(node* other) : 
     prev(other), 
     next(other->next) 
    { 
     prev->next = this; 
     next->prev = this; 
    } 
};

(Note that the ΓÇ£construct after another nodeΓÇ¥ constructor takes the other node by pointer, rather than by reference, so that it wonΓÇÖt be mistaken for a copy constructor.)

But maybe you also want to have a ΓÇ£beforeΓÇ¥ constructor that inserts the new node before an existing node...

View the full article