13
\$\begingroup\$

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 *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 < 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;

    iter = head;

    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;
    iter = head;

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

    if (iter->x == x) {
        printf("found in first element: %i\n", x);
            head = head->next;
        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;
    }

    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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Forgetting for a moment it should invoke free() somewhere. \$\endgroup\$ Jan 31, 2011 at 23:47

6 Answers 6

5
\$\begingroup\$

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
        printf("not found\n");
        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.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ 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). \$\endgroup\$ Feb 3, 2011 at 23:34
  • \$\begingroup\$ @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. \$\endgroup\$
    – H2CO3
    Sep 23, 2015 at 19:39
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ May 20, 2016 at 20:55
  • \$\begingroup\$ They asked for elegant, not efficient. \$\endgroup\$ Sep 23, 2016 at 21:03
18
\$\begingroup\$

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.

\$\endgroup\$
0
5
\$\begingroup\$

General Comments:

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

Comments on Delete:

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))
    {
        printf("not found\n");
        return;
    }
    
    (*list) = delete_item_from_list(*list);
}

struct node* delete_item_from_list(struct node* head)
{
    struct node* iter = head;
    struct node* last = NULL;

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

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

    if (iter == NULL)
    {
        printf("not found\n");
    }
    else if (last == NULL)
    {
        printf("found in first element: %i\n", x);
        head = iter->next;
    }
    else
    {
        printf("deleting element: %i\n", x);
        last->next = iter->next;
    }
   
    free(iter);
    return head;
}
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 4, 2011 at 13:53
4
\$\begingroup\$

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) {
    printf("not found\n");
    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);
void print_list(node *head);
void delete_item(node *&head, int x);

int main(int argc, int argv) {
    struct node *head, *tail;

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

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

    // before
    print_list(head);

    // delete 7.
    delete_item(head, 7);

    // after
    print_list(head);

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

    print_list(head);
}

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) {
        printf("Linked list is empty.\n");
        return;
    }

    if (iter->x == x) {
            printf("Deleting Item. Index: %i, Value=%i\n", i, x);
            head = head->next;
            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.

\$\endgroup\$
3
  • 6
    \$\begingroup\$ This is C, not C++ :) \$\endgroup\$ Feb 1, 2011 at 1:42
  • \$\begingroup\$ 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. :) \$\endgroup\$
    – Michael
    Feb 1, 2011 at 2:14
  • \$\begingroup\$ The code is all C. Your text however says C++ :) If you want to test code easily there's always codepad.org. \$\endgroup\$ Feb 1, 2011 at 6:00
1
\$\begingroup\$

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

void remove_item(struct node **head, int x)
{
   struct node *n = *head,
               *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);

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

      n = next;
   }
}
\$\endgroup\$
-1
\$\begingroup\$

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.

Note that in a garbage-collected system, it's possible to add items to the start of the list, or perform the #2 style of deletion, in a lock-free thread-safe manner. Nodes which are deleted may get unlinked in one thread and accidentally relinked in another, but the delete flag will cause the node to be unlinked again on the next pass. In a multi-threaded system requiring explicit deallocation, such an unlink and relink sequence could be disastrous, since a node could be unlinked, deallocated, and relinked; locks would thus be necessary to avoid problems.

\$\endgroup\$
8
  • \$\begingroup\$ Not true. You have to scan the whole list in order to find the item you want to delete in any case, so there's no need to have to "search for the item before you want to delete" -- you just remember that as you're walking the list. And it's perfectly possible to put items at the front of the list in a non-garbage collected system. \$\endgroup\$ Feb 1, 2011 at 1:40
  • \$\begingroup\$ @Billy: Searching for an item immediately prior to deletion is a reasonably common scenario, and you're correct that in that case one will have the previous-item pointer. The scenario is not universal, however. The last time I used a linked list was for an "thread-safe lock-free arbitrary-order bag" with O(1) insertion and removal. The creator of each node kept a link to the node itself, but would not know if a node was added immediately before its node. So in that application the only time the list had to be traversed was to enumerate it. \$\endgroup\$
    – supercat
    Feb 1, 2011 at 15:35
  • \$\begingroup\$ @Billy: As for garbage collection, that's an issue if one is trying to write thread-safe lock-free code which can function correctly even if a thread is asynchronously aborted. In a non-GC lock-free system, it's almost impossible to know for certain whether anyone might hold a reference to a node, and thus whether the node can be safely deleted. \$\endgroup\$
    – supercat
    Feb 1, 2011 at 15:40
  • \$\begingroup\$ @supercat: But to remove the item from the list, you must first find the item to remove (the OP's interface specifies the value of the entry to remove, not a pointer to the node itself) which will already tell you the previous node. \$\endgroup\$ Feb 1, 2011 at 22:33
  • \$\begingroup\$ As for thread-safe/lock-free, first of all that's a completely difference scenario which has nothing to do with the OP's question, second if you're using a GC in that way the code is no longer lock-free (the GC is not lock free), third it's not even possible to handle that scenario with a GC in a thread-safe/lock-free way (i.e. if an element is removed from the list while someone is enumerating it). \$\endgroup\$ Feb 1, 2011 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.