Cheap dummy head node

It is well known that adding a dummy head node can simplify the insertion and deletion on a linked list, by eliminating the need of special cases (For example: However, a dummy node uses extra memory, which is not always affordable especially when the size of node is large. In this blog, we will show that a dummy node can be as cheap as a pointer to pointer.

Consider the insertion on a sorted linked list:

void ins(node **l, int x) {
    node **p = l;
    while (*p && (*p)->data <= x)
        p = &((*p)->next);
    *p = new node(x, *p);
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s