Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using pointers to remove item from singly-linked list

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?

like image 465
codebox Avatar asked Oct 16 '12 12:10

codebox


People also ask

How do you remove an object from a linked list?

Type 1: remove() Method It is used to remove an element from a linked list. The element is removed from the beginning or head of the linked list. Parameters: This function does not take any parameter. Return Value: This method returns the head of the list or the element present at the head of the list.

Can we delete node from a given linked list if only pointer?

Given only a pointer to a node to be deleted in a singly linked list, how do you delete it? A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires a pointer to the head node which contradicts the problem statement.


2 Answers

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.

like image 61
glglgl Avatar answered Sep 21 '22 01:09

glglgl


If you like learning from examples, I prepared one. Let's say that we have the following single-linked list:

Singly-linked list example

that is represented as follows (click to enlarge):

Singly-linked list representation

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:

Singly-linked list example #2

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.

Singly-linked list example #3

Singly-linked list example #4

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.

Singly-linked list example #5

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:

Singly-linked list example #6

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:

Singly-linked list example #7

like image 41
patryk.beza Avatar answered Sep 22 '22 01:09

patryk.beza