linked list adding to the tail, confusion

Question

Visual Studio 2008 C

What I can't understand about this linked list is the adding to the tail in the else part of the if statement.

When the head and tails is assigned the memory address of the node_temp to both tail and head both point to the same memory location.

However, in the else part is the head in fact still pointing to the tail. There is just something I can't explain and don't understand about the else part?

I hope some one can explain better for me.

static struct convert_temp
{
    size_t cel;
    size_t fah;
    struct convert_temp *next;
} *head = NULL, *tail = NULL;

/** Add the new converted temperatures on the list */
void add(size_t cel, size_t fah)
{
    struct convert_temp *node_temp = NULL; /* contain temp data */

    node_temp = malloc(sizeof(*node_temp));

    if(node_temp == NULL)
    {
        fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]\n",
            __FUNCTION__, __LINE__);
        exit(0);
    }

    /* Assign data */
    node_temp->cel = cel;
    node_temp->fah = fah;
    node_temp->next = NULL;

    if(head == NULL)
    {
        /* The list is at the beginning */
        head = node_temp;   /* Head is the first node = same node */
        tail = node_temp;   /* Tail is also the last node = same node */
    }
    else
    {
        /* Append to the tail */
        tail->next = node_temp;
        /* Point the tail at the end */
        tail = node_temp; 
    }
}

Answer 1

The first time you add an element (let's call it A) to the list, head is null and you go through the if part. That means that both head and tail are set to point to A when adding that first element.

Now let's add another element B. This time, head is not null so it goes through the else part, setting tail to point to B but leaving head pointing at A.

This is as expected, you now have head pointing to A, A pointing to B, B pointing to nothing (null) and tail pointing to B.

Let's take it step by step.

Initial state:  head -+-> null
                      |
                tail -+

Insert item A:  head -+-> A ---> null
                      |
                tail -+

Insert item B:  head ---> A -+-> B ---> null
                             |
                tail --------+

Insert item C:  head ---> A ---> B -+-> C ---> null
                                    |
                tail ---------------+

You can see at each stage (other than the initial) that the current tail is set to point to the new node (which already points to NULL for its next node) then the tail pointer is updated to point to the new last node.

In fact, let's go through the addition of C in even more detail (line by line) so you can see what each line of code is doing (I've renamed node_temp to node just to help with formatting):

Starting state:                head ---> A -+-> B ---> null
                                            |
                               tail --------+

node = malloc(sizeof(*node));  node ---> C ----------> ?
 (allocate node C)             head ---> A -+-> B ---> null
                                            |
                               tail --------+

node->next = NULL;             node ---> C --------+
 (ignore payload cel/fah                           |
  for now since it's not       head ---> A -+-> B -+-> null
    relevant to the list                    |
               structure)      tail --------+

tail->next = node;             node ---------------+
 (first in else clause)                            |
                               head ---> A -+-> B -+-> C ---> null
                                            |
                               tail --------+

tail = node;                   node ---------------+
 (second in else clause)                           |
                               head ---> A ---> B -+-> C ---> null
                                                   |
                               tail ---------------+

Then eventually node disappears since it's a local variable and you have your final state:

                               head ---> A ---> B -+-> C ---> NULL
                                                   |
                               tail ---------------+

The advantage of maintaining a tail pointer in a singly-linked list is to avoid having to step through the entire list to find the end when you're trying to add an item to the end.

Traversing the entire list makes insertion at the end an O(n) time operation (time taken is dependent on the number of items in the list). The use of the tail pointer makes that an O(1) time operation (same amount of time irrespective of the list size).

As an aside, a doubly linked list has an extra use for a tail pointer - it gives the ability to quickly begin a traversal from the end of the list to the start, using tail and the prev pointers in lieu of head and the next pointers.

Answer 2

The else-part just updates the tail of the list, since the head doesn't change when you append to a linked list.

It's an optimization to keep a pointer to the tail element buffered, so you don't have to step through the entire list from the head on each append.