Using pointers to remove item from singly-linked list
Solution 1
At the beginning, you do
pp = &list_head;
and, as you traverse the list, you advance this "cursor" with
pp = &(*pp)->next;
This way, you always keep track of the point where "you come from" and can modify the pointer living there.
So when you find the entry to be deleted, you can just do
*pp = entry->next
This way, you take care of all 3 cases Afaq mentions in another answer, effectively eliminating the NULL
check on prev
.
Solution 2
If you like learning from examples, I prepared one. Let's say that we have the following single-linked list:
that is represented as follows (click to enlarge):
We want to delete the node with the value = 8
.
Code
Here is the simple code that do this:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct node_t {
int value;
node_t *next;
};
node_t* create_list() {
int test_values[] = { 28, 1, 8, 70, 56 };
node_t *new_node, *head = NULL;
int i;
for (i = 0; i < 5; i++) {
new_node = malloc(sizeof(struct node_t));
assert(new_node);
new_node->value = test_values[i];
new_node->next = head;
head = new_node;
}
return head;
}
void print_list(const node_t *head) {
for (; head; head = head->next)
printf("%d ", head->value);
printf("\n");
}
void destroy_list(node_t **head) {
node_t *next;
while (*head) {
next = (*head)->next;
free(*head);
*head = next;
}
}
void remove_from_list(int val, node_t **head) {
node_t *del, **p = head;
while (*p && (**p).value != val)
p = &(*p)->next; // alternatively: p = &(**p).next
if (p) { // non-empty list and value was found
del = *p;
*p = del->next;
del->next = NULL; // not necessary in this case
free(del);
}
}
int main(int argc, char **argv) {
node_t *head;
head = create_list();
print_list(head);
remove_from_list(8, &head);
print_list(head);
destroy_list(&head);
assert (head == NULL);
return EXIT_SUCCESS;
}
If you compile and run this code you'll get:
56 70 8 1 28
56 70 1 28
Explanation of the code
Let's create **p
'double' pointer to *head
pointer:
Now let's analyze how void remove_from_list(int val, node_t **head)
works. It iterates over the list pointed by head
as long as *p && (**p).value != val
.
In this example given list contains value
that we want to delete (which is 8
). After second iteration of the while (*p && (**p).value != val)
loop (**p).value
becomes 8
, so we stop iterating.
Note that *p
points to the variable node_t *next
within node_t
that is before the node_t
that we want to delete (which is **p
). This is crucial because it allows us to change the *next
pointer of the node_t
that is in front of the node_t
that we want to delete, effectively removing it from the list.
Now let's assign the address of the element that we want to remove (del->value == 8
) to the *del
pointer.
We need to fix the *p
pointer so that **p
was pointing to the one element after *del
element that we are going to delete:
In the code above we call free(del)
, thus it's not necessary to set del->next
to NULL
, but if we would like to return the pointer to the element 'detached' from the list instead of the completely removing it, we would set del->next = NULL
:
Solution 3
Reconnecting the list once a node is to be removed is more interesting. Let's consider at least 3 cases:
1.Removing a node from the beginning.
2.Removing a node from the middle.
3.Removing a node from the end.
Removing from the beginning
When removing the node at the beginning of the list, there is no relinking of nodes to be performed, since the first node has no preceding node. For example, removing node with a:
link
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
However, we must fix the pointer to the beginning of the list:
link
|
+-------------+
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
Removing from the middle
Removing a node from the middle requires that the preceding node skips over the node being removed. For example, removing the node with b:
link
|
v
--------- --------- ---------
| a | --+--+ | b | --+---> | c | 0 |
--------- | --------- ---------
| ^
+----------------+
This means that we need some way to refer to the node before the one we want to remove.
Removing from the end
Removing a node from the end requires that the preceding node becomes the new end of the list (i.e., points to nothing after it). For example, removing the node with c:
link
|
v
--------- --------- ---------
| a | --+---> | b | 0 | | c | 0 |
--------- --------- ---------
Note that the last two cases (middle and end) can be combined by saying that "the node preceding the one to be removed must point where the one to be removed does."
Solution 4
In the first approach, you delete a node by unlink it from the list.
In the second approach, you replace the to-be-deleted node with the next node.
Apparently, the second approach simplifies the code in an elegant way. Definitely, the second approach requires better understanding of the linked list and the underlying computation model.
Note: Here is a very relevant but slightly different coding question. Good for testing one's understanding: https://leetcode.com/problems/delete-node-in-a-linked-list/
Solution 5
I prefer the Dummy node approach, an example layout:
|Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL
^ ^
| |
curr curr->next // << toDel
and then, you traverse to the node to delete (toDel = curr>next)
tmp = curr->next;
curr->next = curr->next->next;
free(tmp);
That way, you don't need to check if it's the first element, because the first element is always Dummy and never gets deleted.
codebox
Updated on July 08, 2022Comments
-
codebox almost 2 years
In a recent Slashdot Interview Linus Torvalds gave an example of how some people use pointers in a way that indicates they don't really understand how to use them correctly.
Unfortunately, since I'm one of the people he's talking about, I also failed to understand his example:
I've seen too many people who delete a singly-linked list entry by keeping track of the "prev" entry, and then to delete the entry, doing something like
if (prev) prev->next = entry->next; else list_head = entry->next;
and whenever I see code like that, I just go "This person doesn't understand pointers". And it's sadly quite common. People who understand pointers just use a "pointer to the entry pointer", and initialize that with the address of the list_head. And then as they traverse the list, they can remove the entry without using any conditionals, by just doing
*pp = entry->next
Can someone provide a bit more explanation about why this approach is better, and how it can work without a conditional statement?
-
fuz over 11 yearsIs the &* really needed here? seems a little bit superfluous.
-
glglgl over 11 years@FUZxxl It is needed, as
pp
is a pointer to a node pointer. So we first have to dereference it, then access thenext
in the usual way, and then take its address again. -
hasnobrains over 8 yearsIn case you removing tail node of the list and you need to track the
tail
how you will do it using thispp
? -
Amit Singh Tomar almost 8 years@glglgl, isn't this (*pp)->next enough to get the address to be stored in pp, why & ?
-
cyber_raj almost 8 years@Amit (*pp)->next will give you next node address whereas we want not the next node address but the address where this address (next node address) is stored thus &.
-
Max Heiber over 7 yearsIs
curr->next-next
a typo? -
Lion Lai over 6 yearsYou can also use
*pp = (*pp)->next
. Am I correct? -
glglgl over 6 years@ZianLai No. You want
pp
to point somewhere different, not to change the data wherepp
points to. -
Alexandre Thenorio over 6 yearsNot being a C coder there is something I don't understand here. Don't you have to have a conditional to handle removal of the last element of the list as that will not have a NEXT pointer in the same way you have to handle the head in the first case?
-
abetancort over 3 yearsPerfect implementation of
void rem2(list_entry **pp, int match_val)
it addresses Linus Torvalds concern of many developers not understanding pointers well, specially the subtleties of pointers to pointers. He uses it as an example that many don’t know how delete of multiple elements of a linked using just a two branch condition because it requires the use of a pointer to pointer. -
Pavan Manjunath over 3 years@MaxHeiber It seems like it. I fixed the typo.