linked list adding to the tail, confusion

Question

Hello,

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 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.

Answer 2

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 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)                          |
                               head ---> A -+-> B -+-> null
                                                   |
                                      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 3

It's not that head is still pointing to tail. Head is pointing to former tail. When list contained only one element, it was both head and tail. When new node was appended, tail pointer was updated. Head pointer still points to first node, which is correct.

Answer 4

On first calling add, head and tail will point to a newly created memory block. All subsequent calls to add will fall through to the else part, which will only change the tail pointer, by basically modifying the old tail->next to point to the new memory block, and then update tail to also point to this new memory block.

It is an efficient way of appending. If only head was used, then each time you added a new node_temp, you would have to walk all the next pointers starting from head until you reached the previously added node_temp (whose next pointer would be NULL), and then add in the new node. This would then be an O(n) algorithm, rather than the above O(1).