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

Answer 1

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.

Answer 2

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

Answer 3

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;