Linked List Insertion

This function inserts an entry into an ordered, singly linked list. Each entry in the list is a structure that contains an integer key value, a next pointer, and some other data. The structure is defined as follows:

typedef struct _entry {
    int key;
    int data;
    char name[20];
    struct _entry * next;
} entry, * entry_ptr;

The head of the linked list is saved in a pointer that is stored outside the list itself. Within the list, the next pointer in each entry points to the next element in the list. The end of the linked list is denoted by the next pointer of the last entry being set to NULL.

The order of the list is determined by the key value. Entries with a lower key value appear earlier in the list.

The function is passed a pointer to the structure that will be inserted as the new entry. The code reads the key value to determine the proper order in the list, sets the next pointer as needed, and does not change any other elements in the structure.

The function is also passed a pointer to the current head of the list, and it returns the new head of the list, because this changes if the new entry needs to be inserted at the head of the list.

Source Code

 1.     entry *
 2.     insert_linked_list(
 3.         entry * current_head,
 4.         entry * new_element) {
 5.
 6.         entry * current_element;
 7.
 8.         // If the list is empty, then just return
 9.         // new_element;
10.
11.        if (current_head == NULL) {
12.             new_element->next = NULL;
13.             return new_element;
14.         }
15.
16.         // If new_element should be the first on the list,
17.         // attach the current list to new_element and return
18.         // new_element as the new head of the list.
19.
20.         if (new_element->key < current_head->key) {
21.             new_element->next = current_head;
22.             return new_element;
23.         }
24.
25.         // Now walk the list, comparing key values. Exit the
26.         // while loop when current_element points to the
27.         // value after which we should insert new_element.
28.
29.         current_element = current_head;
30.         while (current_element->next != NULL) {
31.            if (new_element->key <
32.                    current_element->next->key) {
33.                break;
34.            }
35.            current_element = current_element->next;
36.         }
37.
38.         // Insert new_element after current_element
39.         // and return.
40.
41.         new_element->next = current_element->next;
42.         current_element->next = new_element;
43.         return new_element;
44.     }

Suggestions

Because the function has only one local variable, current_element, mark the section of the function in which current_element is used.
The function has several return statements. Verify that they all leave the list in a consistent and correct state.
Identify where the main part of the algorithm is. What is the "goal" of this part of the code?
Where in the code is the actual modification to the list done? Is this code correct?

Hints

Walk through the code with the following parameters to the function (assume in all cases that head properly points to the first element, the list is ordered correctly, and the next pointers are correct, so the last element's next pointer is NULL):

Because the code special-cases inserting at the head of the list, try the case where the list exists with one element whose key value is 7, and a new entry is inserted whose key is 4.
Then test inserting in the middle of the list: A list exists with two elements, key values 5 and 9, and a new entry is inserted whose key value is 6.

Explanation of the Bug

The code is fine until the return statement at line 43:

return new_element;

The two special cases at the top catch both situations in which the head of the list changes to new_element: Lines 11-14 handle the list being empty, and lines 20-23 handle the new element becoming the head of the list. In both cases, the code immediately returns new_element as the new head of the list.

For example, in the first hint, the existing list is non-empty, but the new entry becomes the new head of the list, so the list is modified on line 21 and the new head is returned on line 22.

On the other hand, with the second hint, the new entry has to go between the two existing entries. The while loop on lines 30-36 exits with current_element pointing to the first entry in the list, the one with a key value of 5 (in fact, the while loop exits during the first iteration). The code on lines 41 and 42 properly inserts the new entry after the first entry and adjusts the next pointers.

So, if you reach the return statement at line 43, it will be in a situation where the head of the list has not changed. Therefore, the code has a B.variable error; it should return the old head of the list, not the new element. So, line 43 should be as follows:

return current_head;

Table of Contents