# 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->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 <stdio.h>
#include <stdlib.h>

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

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

for (i = 2; i < 10; i++) {
n->next = create_item(i);
n = n->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->x = x;
return new;
}

void print_list() {
struct node *iter;

while (iter != NULL) {
printf("num: %i\n", iter->x);
iter = iter->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->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;

if (iter == NULL) {
return;
}

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

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

iter = iter->next;
}

}


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

• Forgetting for a moment it should invoke free() somewhere. Jan 31, 2011 at 23:47

If you don't mind recursion (although C programmers generally DO mind), then you can do:

node* delete_item(node* curr, int x) {
node* next;
if (curr == NULL) { // Found the tail
return NULL;
} else if (curr->x == x) { // Found one to delete
next = curr->next;
free(curr);
return next;
} else { // Just keep going
curr->next = delete_item(curr->next, x);
return curr;
}
}


then, in main, you should do

head = delete_item(head, 7);


This uses the C stack to hold the "backwards look" in the list.

• As a C programmer, I love recursion as a technique (e.g. traversing trees, or printing evil numbers (bobhobbs.com/files/kr_lovecraft.html :-) )), but not when it's applied inappropriately (e.g. for something like this in the case where the lists can be large, or the machine has tiny stack). Feb 3, 2011 at 23:34
• @MattCurtis it's not applied inappropriately. If you have a linked list so big that traversing it recursively overflows the stack, then you are having much bigger problems. This deletion is much more elegant than one where one has to keep track of the previous item explicitly and treat the head of the list specially. Sep 23, 2015 at 19:39
• Am I missing something? How could this possibly be more efficient than simply traversing the list in a loop until you find the node just before the target? Also, this looks like it's re-writing the "next" pointer of every node in the list whether it needs it or not. May 20, 2016 at 20:55
• They asked for elegant, not efficient. Sep 23, 2016 at 21:03

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 = &(*current)->next) {
if ((*current)->x == i) {
node* next = (*current)->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.

Why do your list handling functions not take a list as a parameter?
As a result your application can only have one list.

You are leaking the list item when you delete it.

Since the create_item() is calling malloc() I would expect the delete_item() to call free().

I would split the delete_item() into two parts. The first part that deals with the head as a special case and the second part that deals with removing elements from the list (and free()ing them).

void delete_item(struct node** list, int x)
{
if ((list == NULL) || ((*list) == NULL))
{
return;
}

(*list) = delete_item_from_list(*list);
}

{
struct node* last = NULL;

while (iter != NULL)
{
if (iter->x == x)
{
break;
}

last = iter;
iter = iter->next;
}

if (iter == NULL)
{
}
else if (last == NULL)
{
printf("found in first element: %i\n", x);
}
else
{
printf("deleting element: %i\n", x);
last->next = iter->next;
}

free(iter);
}

• The reason I use a single global list was purely because it was a simplistic sample code block. This isn't to do with writing some generic linked list library or anything. Feb 4, 2011 at 13:53

It's been ages since I've done C++, but here are my observations:

First off, you're using global variables, which is ill-advised. I'm not sure if C supports member functions, but if not, you should be using parameter passing, e.g. delete_item(node* head, int x) and so on.

if (iter == NULL) {
return;
}


iter is set to the head of the linked list, and if the linked list doesn't yet exist, you reply that the item is "not found\n". I would change this to "Linked list is empty.\n"

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


This doesn't seem to work in the sense that it does not actually delete the element. If you want this item deleted -- which I'm assuming you do, given the name of the function -- then you should add this line: head = head->next; (You'll need to pass the head parameter "by reference" to make sure that this change will propagate outside the code of the delete_item function. Normally, if the parameter being passed wasn't a pointer, this would be done by passing the pointer. head is a node*, however, and I have forgotten how to pass a pointer by reference... I think it would either be node*& head or node** head ... sorry, but you'll have to figure that one out! :) ) Alternatively, you could have delete_item return a node *, and at the end of the function, you could return the first non-matching entry, and this would be called by head=delete_item(head, x). It's probably slightly frowned upon to do it that way, but it would be an easy way out.

At any rate, once you get that accomplished, it will delete the current head, and the new head will be the second element, if one exists... else it will be set to NULL.

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

iter = iter->next;
}


One problem I see is that you have to decide if you want to delete duplicate entries. For example, if 7 appears twice in the linked list, do you want to delete both 7s, or just one? If you want to delete both, you need to traverse the entire linked list by removing the return statements in the while loop and the initial check of the head node. This will create a problem as the program proceeds on to the final, "not found" statement, but that can be solved with an if statement:

if (!entryfound) printf("not found\n");


entryfound would have to be declared to be 0, and set to 1 if a match was found in the while loop. Alternatively, you could do entryfound++ in the event of a match and change this last line:

if (entryfound) { printf("%i matches found and deleted.\n", entryfound); }
else { printf("No matches found.\n"); }


After the changes, this is what your code should look like:

#include <stdio.h>
#include <stdlib.h>

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

struct node *create_item(int x);

int main(int argc, int argv) {

// initialise a linked list with a few items

for (int i = 2; i < 10; i++) {
tail->next = create_item(i);
tail = tail->next;
}

// before

// delete 7.

// after

// lets delete all odd numbers for effect.

}

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

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

void print_list(node *iter) {
int i=0;

if (iter==NULL} { printf("Linked list is empty.")); }
else {
while (iter != NULL) {
printf("Index: %i, Value=%i\n", i, iter->x);
iter = iter->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->next != NULL to be one behind
// the search).
//I wondered what other people's is or if there
//is a convention?

void delete_item(node *&head, int x) {
int i=0;
node* iter=head;  // Head might have to be dereferenced here... I forget!

if (iter==NULL) {
return;
}

if (iter->x == x) {
printf("Deleting Item. Index: %i, Value=%i\n", i, x);
entryfound++;
}

while (iter->next != NULL) {
i++;
if (iter->next->x == x) {
printf(Deleting Item. Index: %i, Value=%i\n", i, x);
iter->next = iter->next->next;
entryfound++;
}

iter = iter->next;
}

if (entryfound) { printf("%i matches found and deleted.\n", entryfound); }
else { printf("No matches found.\n"); }

}


As others have stated, you need to be deallocating the memory. Your program has what is known as a memory leak. The old "deleted" nodes are not actually deleted, they are simply removed from the chain of pointers. I'll leave it up to you to deallocate them in the event of a match.

Again, it's been a long time since I've done C++, but that's my take. Sorry for any debugging that you might have to do in that code.

• This is C, not C++ :) Feb 1, 2011 at 1:42
• Yep! I realize[d] that, but with that said, I don't know all of the differences between C and C++ (like I said, it's been a while... ~8 years.) The code that I posted probably won't work if you just copy & pasted it, but most of the changes should work, and anything left over should be easy to fix. The code is a big jump from where his code is now to "where it needs to be." It's not perfect, but it's the best I could do. :) Feb 1, 2011 at 2:14
• The code is all C. Your text however says C++ :) If you want to test code easily there's always codepad.org. Feb 1, 2011 at 6:00

My favorite technique would look something like this (copious amounts of comments added for illustrative purposes...):

void remove_item(struct node **head, int x)
{
*prev = NULL;

/* Loop through all the nodes... */
while (n)
{
/* Store the next pointer, since we might call free() on n. */
struct node *next = n->next;

/* Is this a node we're interested in? */
if (n->x == x)
{
/* Free the node... */
free(n);

if (prev)
{
/* Link the previous node to the next one. */
prev->next = next;
}
else
{
/* No previous node.  Update the head of the list. */
}
}
else
{
/* We didn't free this node; track that we visited it for the next iteration. */
prev = n;
}

n = next;
}
}


Deleting an item from a singly-linked list requires finding the previous item. There are two approaches one can use to deal with this:

1. When deleting an item, search through the list to find the previous item, then do the unlink.
2. Have a "deleted" flag for each item. When traversing the list for some other reason, check the "deleted" flag on each node. If a "deleted" node is encountered, unlink it from the previously-visited node.