The Algorithm Design Manual Second Edition

Insertion into a List

Insertion into a singly-linked list is a nice exercise in pointer manipulation, as shown

below. Since we have no need to maintain the list in any particular order, we might

as well insert each new item in the simplest place. Insertion at the beginning of the

list avoids any need to traverse the list, but does require us to update the pointer

(denoted l) to the head of the data structure.

void insert_list(list **l, item_type x)

{

list *p;

/* temporary pointer */

p = malloc( sizeof(list) );

p->item = x;

p->next = *l;

*l = p;

}

Two C-isms to note. First, the malloc function allocates a chunk of memory

of sufficient size for a new node to contain x. Second, the funny double star (**l)

denotes that l is a pointer to a pointer to a list node. Thus the last line, *l=p;