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: http://www.classes.cs.uchicago.edu/archive/2001/spring/CS117/Lectures/HTML/0406/html/slide_5.html). 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);
}
Advertisements
This entry was posted in Programming. Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s