C function to find and delete a node from a singly linked list I'm looking for the most commonly used style for writing the delete_item() function of a singly linked list, that find a matching item and deletes it. Is what I have the 'typical' or 'normal' solution? Are there more elegant ones?

What seems inelegant to me about my solution below, although I don't know a better way to express it, is that the code needs to check the first record individually (i.e. a special case), then as it goes through the iteration, it's not checking iter, it's checking iter-&gt;next, ahead of the iterator's present location, because in a singly linked list you can't go backwards.

So, is there a cleaner way to write the delete_item() function?

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

struct node {
    int x;
    struct node *next;
};

struct node *head;

struct node *create_item(int x);
void print_list();
void delete_item(int x);

int main(int argc, int argv) {

    struct node *n;
    int i;

    // initialise a linked list with a few items
    head = create_item(1);
    n = head;

    for (i = 2; i &lt; 10; i++) {
        n-&gt;next = create_item(i);
        n = n-&gt;next;
    }

    // before
    print_list();

    // delete 7.
    delete_item(7);

    // after
    print_list();

    // lets delete all odd numbers for effect.
    delete_item(1);
    delete_item(3);
    delete_item(5);
    delete_item(9);

    print_list();
}

struct node *create_item(int x) {
    struct node *new;

    new = (struct node *) malloc (sizeof(struct node));
    new-&gt;x = x;
    return new;
}

void print_list() {
    struct node *iter;

    iter = head;

    while (iter != NULL) {
        printf("num: %i\n", iter-&gt;x);
        iter = iter-&gt;next;
    }
}

//We're looking for the best way to right this.
//This is _my_ standard solution to the problem.
// (that is, to test the first element explicitly
// the use current-&gt;next != NULL to be one behind
// the search).
//I wondered what other people's is or if there
//is a convention?
void delete_item(int x) {

    struct node *iter;
    iter = head;

    if (iter == NULL) {
        printf("not found\n");
        return;
    }

    if (iter-&gt;x == x) {
        printf("found in first element: %i\n", x);
            head = head-&gt;next;
        return;
    }

    while (iter-&gt;next != NULL) {
        if (iter-&gt;next-&gt;x == x) {
            printf("deleting element: %i\n", x);
            iter-&gt;next = iter-&gt;next-&gt;next;
            return;
        }

        iter = iter-&gt;next;
    }

    printf("not found\n");
}


This is a complete example that can be compiled and tested. The output:

23:28: ~$ gcc -o ll linked_list.c
23:28: ~$ ./ll
num: 1
num: 2
num: 3
num: 4
num: 5
num: 6
num: 7
num: 8
num: 9
deleting element: 7
num: 1
num: 2
num: 3
num: 4
num: 5
num: 6
num: 8
num: 9
found in first element: 1
deleting element: 3
deleting element: 5
deleting element: 9
num: 2
num: 4
num: 6
num: 8
The neatest way to deal with this is to use what I was taught as the "2 pointer trick" (thank you Charles Lindsay all those years ago):

Instead of holding a pointer to the record you hold a pointer to the pointer that points to it - that is you use a double indirection. This enables you to both modify the pointer to the record and to modify the record without keeping track of the previous node.

One of the nice things about this approach is that you don't need to special case dealing with the first node.

An untested sketch using this idea for delete_item (in C++) looks like:

void delete_item(node** head, int i) {
  for (node** current = head; *current; current = &amp;(*current)-&gt;next) {
    if ((*current)-&gt;x == i) {
      node* next = (*current)-&gt;next;
      delete *current;
      *current = next;
      break;
    }
  }
}


This loop will break after the first entry it finds, but if you remove the "break" then it will remove all entries that match.