insertion in linked list -

Question

I was reading Skeina's book. I could not understand this code. Basically what is the use of double pointer. And what is the use of *l = p? Can anyone please explain by diagram.

void insert_list(list **l, item_type x) {
    list *p; /* temporary pointer */
    p = malloc(sizeof(list));
    p->item = x;
    p->next = *l;
    *l = p;
}

Answer 1

You shouldn't call it a "double pointer" because that would be a pointer to a double. It is a pointer to a pointer, and it is used to allow the function to alter the value of an argument which happens to be a pointer. If you're familiar with C#, it's like an out argument. In this situation the l argument used to get both IN and OUT behavior, but you may often see this used for output only.

Since this function returns type void it very well could have been written without the use of the pointer to a pointer like this:

list * insert_list(list *l, item_type x) {
{
    list *p; /* temporary pointer */
    p = malloc(sizeof(list));
    p->item = x;
    p->next = l; // note that this is not *l here
    return p;
}

This change would require the code that calls the function to update it's own handle to the list since the head of the list is what's being changed.

Answer 2

This function performs a very simple task: it inserts a list node at the position for which it receives a pointer. There is nothing special about double pointers, they are just pointers to pointers. They hold the address of a pointer, which contains the address of an object. void **l contains the address of a list * pointer. *l retrieves this address and *l = p stores it.

malloc is used to allocate a list structure, p receives the address of the allocated structure. The code is somewhat sloppy as p is not checked for NULL before dereferencing it. If malloc fails because of lack of memory, the program will invoke undefined behaviour, hopefully stopping with a segmentation fault or something potentially worse.

The node is initialized, its next pointer is set to the node pointed to by the l argument, and finally the new node's address is stored at the address passed as the l argument. The effect is simple: the node is inserted at *l.

This method is clever ad it allows the same function to insert a new node anywhere is a list. For example:

list *head = NULL;
...
/* Insert a LIST_A node at the beginning of the list */
insert_list(&head, LIST_A);
...
/* insert a LIST_B element as the second node in the list */
insert_list(&head->next, LIST_B);
...
/* find the end of the list */
list *node;
for (node = head; node->next; node = node->next)
    continue;

/* insert a LIST_Z node at the end of the list */
insert_list(&node->next, LIST_Z);

The only tricky thing above is the concept of pointer itself, here is a simple overview:

• Memory can be conceptualized as a (large) array of bytes, addresses are offsets in this array.
• char variables by definition are single bytes,
• int variables occupies a number of bytes specific to the architecture of the system, typically 4 or 8 bytes in current hardware.
• Think of pointers as variables holding the address in memory of another variable. They need to be large enough to hold any valid address in the system, in current systems with more than 4 GB of physical and addressable memory, they are 64 bit long and occupy 8 bytes.
• There is a special address value NULL which represents no object and is used to specify that a given pointer does not point to any real object. The address 0 is used for this purpose. malloc will return NULL if it cannot allocate the memory requested, the return value should be tested, as storing a value at this address is forbidden and usually caught as an invalid access (segmentation fault).

This summary is purposely simplistic. I used the term variable instead of object to avoid the confusion with OOP concepts.