How to delete a certain element in linked list in C

Question

I'm trying to delete a certain element in my linked list.

When I print all elements on the screen, they have a certain order (see case 2). When in case 7, I can choose an element to delete based on that order.

The code in case 7 doesn't work. Here is my code:

#include "stdio.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "string.h"
#define SIZE 100
double dummy = sin(0.0);

struct sputnik {
  char nazvanie[30];
  char nazvanie_main[30];

  int year;
  float d;
  int period;
  struct sputnik *next;
};

int main(void) {
  char choice;
  int punkt;
  int i, count = 0;
  struct sputnik *head = NULL;
  struct sputnik *prev, *current;
  int res, kolvo, j, number;
  struct sputnik a[SIZE];
  system("clear");

  while (1) {
    printf("Menu: ");
    printf("1- Create table with sputniks  \n 2-All sputniks \n 3-Write      4-Read \n 5-Add \n 6-Change \n 7-Delete \n 8-Exit \n");
    scanf("%d", &punkt);

    while (getchar()!='\n') 
      continue;

    switch(punkt) {
      case 1:
        while (1) {
          printf("Create new table? (N-new; O-old)");
          choice = toupper(getchar());
          if (choice == 'N') {
            count = 0;
            prev = head;
            while (prev != NULL) {
              current = prev->next;
              free(prev);
              prev = current;
            }
            head = NULL;
          }
          if (choice != 'N' && choice != 'O') {
            while (getchar() != '\n')
              continue;
            continue;
          }
          while (getchar()!='\n')
            continue;
          break;
        }
        for ( ; ; count++) {
          current = (struct sputnik *)malloc(sizeof(struct sputnik));
          if (head == NULL) {
            head = current;
          } else {
            prev->next = current;
          }
          current->next = NULL;
          printf("Name %d sputnika:", count + 1);
          gets(current->nazvanie);
          printf("Name planet:");
          gets(current->nazvanie_main);
          printf("Open year:");
          scanf("%d", &current->year);
          while (getchar() != '\n')
            continue;
          printf("Diameter:");
          scanf("%f", &current->d);
          while (getchar() != '\n')
            continue;
          printf("Period:");
          scanf("%d", &current->period);
          while (getchar() != '\n')
            continue;
          prev = current;
          printf("Finish vvod?: y/n: \n");
          if (toupper(getchar()) == 'Y') {
            count++;
            break;
          } else {
            while (getchar() != '\n')
              continue;
            continue;
          };
        }
        break;
      case 2:
        if (head == NULL) {
          printf ("No data \n");
        } else {
          printf(" Sputniks: \n");
        }
        current = head;
        i = 0;
        while (current != NULL) {
          printf("%d sputnik - %s planet %s god %d diametr %4.3f period %d\n", ++i, current->nazvanie, current->nazvanie_main, current->year, current->d, current->period);
          current = current->next;
        }
        break;
      case 3:
        break;
      case 4:
        break;
      case 5:
        break;
      case 6:
        break;
      case 7:
        int nummer;
        printf("Number for sputnik to delete:\n");
        scanf("%d", &nummer);
        while (getchar() != '\n')
          continue;
        current = head;
        i = 0;
        while (current != NULL) {
          if (i == nummer - 1) {
            prev = current;
            free(current);
            current = prev->next;
          } else {
            current = current->next;
            i = i + 1;
          }
        }
        break;
      case 8:
        prev = head;
        while (prev != NULL) {
          current = prev->next;
          free(prev);
          prev = current;
        }
        printf("Finish \n");
        return 0;
        break;
      default:
        printf ("Dont right choose!\n");
        break;
    }
  } 
  return 0; 
}

You need to set prev=current in your else block (before updating current), rather than your if block. In the if, you'll set prev->next=current->next then free(current). — adamdc78
– adamdc78, Commented Dec 30, 2014 at 7:39
You do understand the warning: ‘gets’ is deprecated message the compiler is (or should be) giving you? While not relevant to your logic issue here, it isn't a good idea to use gets (unless that is the only thing available on your system - which almost never applies) It creates substantial security vulnerabilities for buffer overrun. — David C. Rankin
– David C. Rankin, Commented Dec 30, 2014 at 8:29

WhozCraig · Accepted Answer · 2014-12-30 09:33:14Z

Your current algorithm is completely broken.

You never link the node prior to the deleted node with the one following.
Your algorithm does not account for deletion the head node at all.
You needlessly march through the rest of the list even after deleting your target.

In short, this needs to be done over.

There a a number of ways to do this, many using at least one pair of pointers (a prev and a current) and marching them down the list, which appears to be what you tried and what several answers are trying to fix. Being different, I'll show you how you can do this with a single pointer-to-pointer. This has the added benefit of eliminating the need to special-case head-pointer checking.

Including basic error checking it is done something like this:

int nummer;
printf("Number for sputnik to delete:\n");
if (scanf("%d", &nummer) == 1 && nummer > 0)
{
    struct sputnik** pp = &head;
    while (--nummer && *pp)
        pp = &(*pp)->next;;
    if (*pp)
    {
        struct sputnik *p = *pp;
        *pp = p->next;
        free(p);
    }
}
while (getchar() != '\n')
    continue;

This walks the actual pointers in the linked list; not just their values. As a result when we arrive at the pointer referring to the node we intend to delete, we do so using the pointer in the list that got us there (including the head pointer if the request was for node(1)). This allows us to update that pointer to its successors address, then delete the node and finish up.

When it comes to single-linked-list manipulation, pointer-to-pointer algorithms often offer surprisingly elegant solutions and generally concise code. Stare at it awhile and perhaps compare it to different two/three pointer methods.

Best of luck.

Short, sweet, to-the-point and bulletproof. Always good to snatch a few more pebbles from a learned hand.

Ziumin · Accepted Answer · 2014-12-30 07:46:05Z

You should properly relink your list when deleting its item. And also don't try to read from deleted element (prev=current;current=prev->next; free(prev);)

So your case 7 may look like this code:

        int nummer;
        printf(" Number for sputnik to delete:\n");
        scanf ("%d",&nummer);
        while(getchar()!='\n') continue;
        current=head; prev=NULL;
        i=0;
        while(current!=NULL) {
          if (i==nummer-1){
              if (prev==NULL) {
                // move head pointer if first element should be removed
                head=current->next;
              } else {
                prev->next = current->next; // relink list items
              }
              free(current); // free allocated memory
              break;
          }
          else 
          {
            prev=current; current=current->next; i=i+1; // go to next item
          }
        }
        break;

fenceop · Accepted Answer · 2014-12-30 08:17:23Z

0

Your deletion logic is not right;

struct sputnik *prev = NULL, *current = NULL;
current = head;

if (number == 1) {
  head = head->next;
  free(current);
  current = NULL;
  return;
}

while (i < (number - 1)) {
  current = current->next;
  i++;
} 

prev = current;
current = current->next;

if (current->next == NULL) {
  free(current);
  current = NULL;
  prev->next = NULL;
  return;
} else {
  prev->next = current->next;
  free(current);
  current = NULL;
  return;
}

edited Dec 30, 2014 at 8:17

fenceop

1,5273 gold badges19 silver badges30 bronze badges

answered Dec 30, 2014 at 7:44

Gopi

19.9k4 gold badges28 silver badges37 bronze badges

2 Comments

Ziumin Over a year ago

What about head if head element should be deleted?

Gopi Over a year ago

@Ziumin Deleting at some position the edited code should be fine

Collectives™ on Stack Overflow

How to delete a certain element in linked list in C

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related