 Linked List Removal
This code removes an entry from an ordered, singly linked list. It follows up on the previous example of a linked list of structures ordered by a key value. The structure is defined the same way:
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 a NULL next pointer. Entries with a lower key value appear earlier in the list.
When passed a key value to look up, the function needs to remove the entry with a key equal to that value. (If multiple entries with that key value exist, it removes only the first one it finds.)
The function does not change any of the fields in the entry it removes. In the remaining list, it adjusts only next pointers as necessary.
The function is passed the current head of the list, and returns the new head of the list because the head changes if the removed entry is the current head.
The function also returns the deleted entry. It can't do this using the function return value, because that is used to return the new head of the list. Therefore, one of the function arguments is a pointer to a pointer to an entry. This is defined as a * entry_ptr, which is a good way to think of it: a location at which the function can store a pointer to the deleted entry.
Source Code
1. entry *
2. delete_linked_list(
3. entry * current_head,
4. int key_to_delete,
5. entry_ptr * deleted_entry) {
6.
7. entry * current_element, * previous_element;
8.
9. // If the list is empty, then do nothing.
10.
11. if (current_head == NULL) {
12. *deleted_entry = NULL;
13. return NULL;
14. }
15.
16. // Does the head of the list have key_to_delete?
17.
18. if (current_head->key == key_to_delete) {
19. *deleted_entry = current_head;
20. return current_head->next;
21. }
22.
23. // Now find the entry that has the value
24. // in question.
25.
26. previous_element = current_head;
27. current_element = current_head->next;
28. while (current_element != NULL) {
29. if (current_element->key == key_to_delete) {
30. // Delete current_element.
31. previous_element->next =
32. current_element->next;
33. *deleted_entry = current_element;
34. return current_head; // unchanged
35. }
36.
37. // Advance our pointer in the linked list.
38. current_element = current_element->next;
39. }
40.
41. // If we get here, we did not find the entry.
42.
43. *deleted_entry = NULL;
44. return current_head;
45. }
Suggestions
The code begins with a couple of special cases. Are these the proper special cases? The code from lines 26-39 is a loop. How many loop variables does it have? Are they initialized and modified correctly? At line 30, what would be good inputs to the code at that point? Which variables should you consider when thinking of inputs? Which ones can be ignored? The code has multiple return statements. Do they all "clean up" the same variables?
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):
The code should handle no entry being found. Try a list with three elements whose key values are 2, 4, and 9, and the function is called with key_to_delete equal to 5. Deleting an element in the middle of the list is the most common case. Assume a list exists with three elements whose key values are 2, 4, and 9, and the function is called with key_to_delete equal to 4. Try it with a longer list. The list exists with four elements whose key values are 2, 3, 4, and 8, and the function is called with key_to_delete equal to 4.
Explanation of the Bug
The while loop on lines 28-39 is walking through the list. Because it must keep track of the entry before the one it wants to delete (so it can fix up the next pointer), it keeps track of both previous_element and current_element. The initialization code just before the while loop, on lines 26 and 27, makes this apparent.
Therefore, both these pointers need to be advanced for each iteration of the loop. The statement on line 38
current_element = current_element->next;
is correct, but the code also needs to advance previous_element, so line 38 should be preceded by a new line of code:
previous_element = current_element;
This is an F.missing error. It is important that this new line precede the existing one, so the two lines appear in this order:
previous_element = current_element;
current_element = current_element->next;
Under what conditions does the code work? There are special cases handled earlier: the list being empty on lines 11-14, and the entry to delete being at the head on lines 18-21. In addition, if the entry is not found, as discussed in the first hint, the code works because the if() statement on line 29 is never true, so the code that follows (which uses previous_element) never executes. (Because the list is ordered, the code could also be optimized by inserting some code around line 36 to break out of the while loop if current_element->key is greater than key_to_delete.)
The code does work for the second hint, which hits none of the above exceptions. Some analysis reveals that the code works if the element to be deleted is precisely the second one on the list; the if() on line 29 is true on the first iteration, so the code breaks out of the while and previous_element retains its correctly initialized value from line 26.
| 
