Jump to content

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


Recommended Posts

RaymondChen_5in-150x150.jpgWhen 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

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...