What is the double-pointer technique for simplifying the traversal of linked lists?

Question

10 years ago I was shown a technique for traversing a linked list: instead of using a single pointer, you used a double-pointer.

The technique yielded smaller, more elegant code by eliminating the need to check for certain boundary/edge cases.

Does anyone know what this technique actually is? (Trying to remember, but cannot)

Answer 1

I think you mean doubly-linked lists where a node is something like:

struct Node {
(..) data // The data being stored in the node, it can be of any data type
Node *next; // A pointer to the next node; null for last node
Node *prev; // A pointer to the previous node; null for first node
}

Answer 2

I think you mean double pointer as in "pointer to a pointer" which is very efficient for inserting at the end of a singly linked list or a tree structure. The idea is that you don't need a "trailing pointer" to follow your traversal pointer once you find the end (a NULL pointer). Since you can just dereference your pointer to a pointer (it points to the last node's next pointer!) to insert. Something like this:

T **p = list_start;
while(*p) {
   p = &(p->next);
}
*p = new T;

instead of something like this:

T *p = list_start;
T *prev_p = NULL;
while(p) {
   prev_p = p;
   p = p->next;
}
if(prev_p) {
    prev_p->next = new T;
}

NOTE: It is also useful for making efficient removal code for a singly linked list. At any point doing *p = (*p)->next will remove the node you are "looking at" (of course you still need to clean up the node's storage).

Answer 3

You probably mean a doubly-linked list, with one of the pointers going forward and the other going backward. This allows you to get to the next and previous nodes for a given node without having to remember the last one or two nodes encountered (as in a singly-linked list).

But the one thing I discovered which made the code even more elegant was to always have two dummy elements in the list at all times, the first and the last. This gets rid of the edge cases for insertion and deletion since you're always acting on a node in the middle of the list.

For example, an empty list is created:

first = new node
last = new node
first.next = last
first.prev = null
last.next = null
last.prev = first
// null <- first <-> last -> null

Obviously, traversing the list is slightly modified (forward version shown only):

curr = first.next
while curr <> last:
    do something with curr
    curr = curr.next

The insertions are much simpler since you don't have to concern yourself with whether you're inserting at the start or end of the list. To insert before the current point:

if curr = first:
    raise error
add = new node
add.next = curr
add.prev = curr.prev
curr.prev.next = add
curr.prev = add

Deletions are also simpler, avoiding the edge cases:

if curr = first or curr = last:
    raise error
curr.prev.next = curr.next
curr.next.prev = curr.prev
delete curr

All very much cleaner code and at the cost of only having to maintain two extra nodes per list, not a great burden in today's huge memory space environments.

Caveat 1: If you're doing embedded programming where space still might matter, this may not be a viable solution (though some embedded environments are also pretty grunty these days).

Caveat 2: If you're using a language that already provides linked list capabilities, it's probably better to do that rather than roll your own (other than for very specific circumstances).

Answer 4

By "double-pointer", I think you mean "pointer-to-pointer". This is useful because it allows you to eliminate special cases for either the head or tail pointers. For example, given this list:

struct node {
    struct node *next;
    int key;
    /* ... */
};

struct node *head;

If you want to search for a node and remove it from the list, the single-pointer method would look like:

if (head->key == search_key)
{
    removed = head;
    head = head->next;
}
else
{
    struct node *cur;

    for (cur = head; cur->next != NULL; cur = cur->next)
    {
        if (cur->next->key == search_key)
        {
            removed = cur->next;
            cur->next = cur->next->next;
            break;
         }
    }
}

Whereas the pointer-to-pointer method is much simpler:

struct node **cur;

for (cur = &head; *cur != NULL; cur = &(*cur)->next)
{
    if ((*cur)->key == search_key)
    {
        removed = *cur;
        *cur = (*cur)->next;
        break;
    }
}

Answer 5

I agree with the comments about using the STL containers for handling your list dirty work. However, this being Stack Overflow, we're all here to learn something.

Here's how you would normally insert into a list:

typedef struct _Node {
    void * data;
    Node * next;
} Node;

Node * insert( Node * root, void * data ) {
    Node * list = root;
    Node * listSave = root;

    while ( list != null ) {
        if ( data < list->data ) {
            break;
        }

        listSave = list;
        list = list->next;
    }

    Node * newNode = (Node*)malloc( sizeof(Node) );
    newNode->data = data;
    /* Insert at the beginning of the list */
    if ( listSave == list ) {
        newNode->next = list;
        list = newNode;
    }
    /* Insert at the end of the list */
    else if ( list == null ) {
        listSave->next = newNode;
        newNode->next = null;
        list = root;
    }
    /* Insert at the middle of the list */
    else {
        listSave->next = newNode;
        newNode->next = list;
        list = root;
    }

    return list;
}

Notice all the extra checking you have to do depending on whether the insertion occurs at the beginning, end or middle of the list. Contrast this with the double pointer method:

void insert( Node ** proot, void * data ) {
    Node ** plist = proot;

    while ( *plist != null ) {
        if ( data < (*plist)->data ) {
            break;
        }

        plist = &(*plist)->next;
    }

    Node * newNode = (Node *)malloc( sizeof(Node) );
    newNode->data = data;
    newNode->next = *plist;
    *plist = newNode;
}

As Evan Teran indicated, this works well for singly linked lists, but when it's doubly linked, you end up going through just as many if not more manipulations as the single pointer case. The other draw back is that you're going through two pointer dereferences for each traversal. While the code looks cleaner, it probably doesn't run as quickly as the single pointer code.