Exercise excerpt from the book "C Programming: A Modern Approach" by K.N King. I ask for help in understanding if the last part of my solution is incorrect.
Modify the delete_from_list function so that it uses only one pointer variable instead of two (cur and prev).
This is a simple linked list and the function deletes the first node encountered whose .value is equal to the argument n.
Original code:
struct node {
int value;
struct node *next;
};
struct node *delete_from_list(struct node *list, int n)
{
struct node *cur, *prev;
for (cur = list, prev = NULL;
cur != NULL && cur->value != n;
prev = cur, cur = cur->next)
;
if (cur == NULL)
return list;
if (prev == NULL)
list = list->next;
else
prev->next = cur->next;
free(cur);
return list;
}
My solution:
struct node *delete_from_list(struct node **list, int n) {
struct node *ptr = *list;
while (ptr != NULL) {
if (ptr->value == n) {
*list = ptr->next;
free(ptr);
break;
}
list = &(ptr->next);
ptr = ptr->next;
}
return *list;
}
I think this solution is almost correct, but I struggle to understand if the last statement, return *list;, actually returns the beginning of the list. This is my first time using a pointer to a pointer to a struct, so I may be misunderstanding some concept.
I'm more interested in knowing how my solution is incorrect or not, than being given a completely different solution, so as to save your time.
You changed the list parameter to be a pointer to the caller's node* variable that is pointing at the head node of the linked list. That change in itself is fine (but not part of the exercise, FYI):
+------+ +------+
[head] -> | node | -> | node | -> ...
^ +------+ +------+
|
[list]
By using a pointer-to-pointer as the input parameter, there is no longer any reason to return a node* pointer to the head node, since you can just modify the input node* variable to point at the new head node.
If your loop finds the n value in the list, you are trying to do exactly that update. However, you are modifying the input node* variable unconditionally to now point at the next node which follows the removed node.
That works fine if the removed node is the 1st node in the list:
+---------------+
| +------+ | +------+
[head] | xxxx | +-> | node | -> ...
^ +------+ +------+
| ^
[list] FREED!
But it is not OK if the removed node is not the 1st node. You will corrupt your list by losing access to all of the nodes that preceded the removed node:
+----------------------------+
| +------+ +------+ | +------+
[head] | node | -> | xxxx | +-> | node | -> ...
^ +------+ +------+ +------+
| ^ ^
[list] LEAKED! FREED!
You are not performing that safely check, as the original code does.
So, try something more like this instead:
struct node* free_node(struct node *n)
{
struct node *next = n->next;
free(n);
return next;
}
void delete_from_list(struct node **list, int n) {
while (*list != NULL) {
if ((*list)->value == n) {
*list = free_node(*list);
break;
}
list = &((*list)->next);
}
}
Or:
void free_node(struct node **n)
{
struct node *next = (*n)->next;
free(*n);
*n = next;
}
void delete_from_list(struct node **list, int n) {
while (*list != NULL) {
if ((*list)->value == n) {
free_node(list);
break;
}
list = &((*list)->next);
}
}
On the 1st loop iteration, list points at the caller's node* variable which is pointing at the list:
+------+ +------+
[head] -> | node | -> | node | -> ...
^ +------+ +------+
|
[list]
If that 1st node is removed, the caller's node* variable is updated to point at the next node following the removed node, and the function exits:
+---------------+
| +------+ | +------+
[head] | xxxx | +-> | node | -> ...
^ +------+ +------+
| ^
[list] FREED!
Otherwise, on the next loop iteration, list is now pointing at the previous node's next field. If that next node is removed, the previous node's next field is updated to point at the next node following the removed node, and the function exits:
+-----------------+
| |
+------+ +------+ | +------+
[head] -> | node | | xxxx | +-> | node | -> ...
+------+ +------+ +------+
^ ^
| FREED!
[list] -------+
As so on, repeating until the entire linked list has been iterated through.
Now, if changing the signature of the delete_from_list() function is not an option (because the exercise didn't ask you to do that), then you can do this instead, with the same effect:
struct node* delete_from_list(struct node *list, int n) {
struct node **ptr = &list;
while (*ptr != NULL) {
if ((*ptr)->value == n) {
*ptr = free_node(*ptr);
// or: free_node(ptr);
break;
}
ptr = &((*ptr)->next);
}
return list;
}