Question: I was at an interview for a C position in which they presented me with an idiom that I haven't previously encountered. This is a trick that simplifies implementation of various algorithms involving linked lists and I'm wondering if anybody else has encountered this.

Say we have a linked list record defined so:

```
typedef struct _record
{
    char* value;
    struct _record* next;
} record;

```

We need a function that inserts a new record so that the entire list remains sorted with respect to the value's in the records. The following implementation is simpler than anything I would have used, albeit less readable.

```
void insert_sorted(record** r, const char* value)
{
    record* newrec = NULL;
    while(*r && strcmp(value, (*r)->value) > 0)
        r = &((*r)->next); /* move r to point to the next field of the record */
    newrec = malloc(sizeof(record));
    newrec->value = strdup(value);
    newrec->next = *r;
    *r = newrec;
}

```

When the function is called, r points to the head pointer of the list. During the while loop, r is updated to point to the `next` field of the record that comes just before the point where we want to put the new record in. The last line of the function either updates the head pointer of the list (if the insertion happens at the beginning) or the `next` field of the previous record, which is quite cool.

A couple of questions:

* Does this idiom have a name or is it mentioned in any literature?
* Are there others like it in the C language?

I thought I knew C pretty well and had pointers and indirection pretty well figured out, but this one took me a while to fully understand.

Answer: 
I don't know if this has a name or even if it's some special idiom but, since memory is relatively plentiful nowadays, my linked lists (where the language libraries don't make them available) are a special variant which simplifies the code greatly.

For a start, they're always doubly-linked since this makes traversal in both directions easier, for both processing and insert/delete operations.

An 'empty' list actually consists of two nodes, the head and the tail. By doing this, inserts and deletes do not need to worry about whether the node they're deleting is the head or tail, they can just assume it's a middle node.

Insertion of a new node y before node x then become a simple:

```
x -> prev -> next = y
y -> next = x
y -> prev = x -> prev
x -> prev = y

```

Deletion of node x is a simple:

```
x -> prev -> next = x -> next
x -> next -> prev = x -> prev
free x

```

Traversal is adjusted to ignore the extraneous head and tail:

```
n = head -> next
while n != tail
    process n
    n = n -> next

```

This all serves to make the code a lot easier to understand without all the special handling of the edge cases, at the cost of a couple of nodes of memory.
I have also come up with this use of a double pointer, I have used it, but I don't really like it. The code that I came up with has this kernel to search for certain objects and remove them from the list:

```
Element** previous = &firstElement, *current;
while((current = *previous)) {
    if(shouldRemove(current)) {
        *previous = current->next;  //delete
    } else {
        previous = &current->next;  //point to next
    }
}

```

The reason I don't like my code is the subtle difference between the two if clauses: the syntax is almost identical, but the effect is entirely different. I do not think, we should write code as subtle as this, but doing it differently makes the code really lengthy. So, either way is bad - you might go for brevity or for readability, it's your choice.