Circlular Linked List

Question

My code for a circular linked list works fine for adding, searching, counting, viewing but once I delete an entry from the list, it messes up with all other data in the list. I know the bug is in the DeleteNode function but can't figure it out. Please help me with this - Thank you.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct Node{
    int data;
    struct Node *next;
}*head,*temp,*curr,*prev,*p;
/*   Prototypes   */
void AddNode(int value);
int CountNode();
void SearchNode(int value);
void ViewAll();
void DeleteNode(int value);
/* Main */
int main(){
    int choice,value;
    printf("\n\n\n\t\t\tCircular Linked List\n\n\t\t\tSyed Danish Ali\n\n\t\t\tUBIT\n\n\n\t\t\t\tHit ENTER to continue...");
    while(getche() != '\r'){
    }
    do{
        system("cls");
        printf("\n\nMENU\n=====\n\n[1] ADD\n[2] COUNT\n[3] SEARCH\n[4] VIEW ALL [5] DELETE\n[6] EXIT\n\nCHOICE:\t");
        scanf("%d",&choice);
        if(choice == 1){
        printf("Enter data:\t"); scanf("%d",&value);
        AddNode(value);
        getch();
        } else if(choice == 2){
        printf("\n\n%d Node(s).",CountNode());
        getch();
        }else if(choice == 3){
        printf("Enter the data to search:\t");
        scanf("%d",&value);
        SearchNode(value);
        getch();
        } else if(choice == 4){
        ViewAll();
        getch();
        } else if(choice == 5){
        printf("Enter the data to search:\t");
        scanf("%d",&value);
        DeleteNode(value);
        getch();
        } else if(choice == 6){
            return 0;
        }

    }while(1);
}

void AddNode(int value){
    temp = (struct Node *) malloc (sizeof(struct Node));
    temp->data = value;

    if(head == NULL){
    head = temp;
    temp->next = head;
    } else {
    curr = head;
    while(curr->next != head){
        curr = curr->next;
    }
    p = curr;
    curr->next = temp;
    temp->next = head;
    }
    printf("\n\nNode added.");
}
int CountNode(){
    int k = 0;
    if(head == NULL){
    return 0;
    } else {
    curr = head;
    while(curr->next != head){
        k++;
        curr = curr->next;
    }
    return k;
    }
}
void SearchNode(int value){
    int flag = 0,k = 0;
    if (head == NULL){
    printf("\n\nList is empty.");
    } else {
    curr = head;
    while(curr->next != head){
        if (curr->data == value){
        flag = 1;
        printf("\n\n%d found at index # %d.",value,k);
        curr = curr->next;
        } else {
        curr = curr->next;
        k++;
        }
    }
    }
    if(flag == 0)
    printf("\n\nValue %d not found.",value);
}
void ViewAll(){
    int counter = 0;
    if(head == NULL)
    printf("\n\nList is empty.");
    else{
    curr = head;
    printf("LIST GENERATED:\n===============\n");
    while(curr->next != head){
        printf("\nElement # %d:\nData:\t%d",counter+1,curr->data);
        curr = curr->next;
        counter++;
    }
    }
}
void DeleteNode(int value){
    int flag = 0;
    if(head == NULL){
    printf("\n\nList is empty.");
    } else {
    curr = head;
    while(curr->next != head){
        if(curr->data == value){
        printf("\n\nValue found.");
        flag = 1;
        if(curr == head){
            curr->next = head;
            free(curr);

        } else {
            prev->next = curr->next;
            free(curr);
        }
        } else {
        prev = curr;
        curr = curr->next;
        }
    }
    printf("Node deleted.");
    }
    if(flag == 0)
    printf("\n\nValue not found.");
}

Answer 1

You have a circular list. This means that whenever you are deleting a node, be it head or not, there will be previous node.

This code can be shortened and will also resolve your issue.

    if(curr == head){
        curr->next = head;
        free(curr);

    } else {
        prev->next = curr->next;
        free(curr);
    }

To

    prev->next = curr->next;
    if(curr == head)
         head = curr->next;
    free(curr);

Your original code sets curr->next to head instead of the other way around thus ending up in curr->next pointing to curr (which is equal to head).

EDIT:

However, you should also check if curr->next is equal to itself which means you are deleting the last node in the circular link list.

Answer 2

} else {
        prev->next = curr->next;  //here prev doesn't point to any memory address so
                                    we can't assign value to prev->next
        free(curr);
    }

Answer 3

Your Code is good, i took complete look to it and found the error. You just need to add break after freeing node. thats it. :) After freeing node it is again ittrating and current is null.. so it break.

void DeleteNode(int value){
    int flag = 0;
    if(head == NULL){
    printf("\n\nList is empty.");
    } else {
    curr = head;
    while(curr->next != head){
        if(curr->data == value){
        printf("\n\nValue found.");
        flag = 1;
        if(curr == head){
            curr->next = head;
            free(curr);
            break;  // this is where it break

        } else {
            prev->next = curr->next;
            free(curr);
            break;  // this is where it break
        }
        } else {
        prev = curr;
        curr = curr->next;
        }
    }
    printf("Node deleted.");
    }
    if(flag == 0)
    printf("\n\nValue not found.");
}

To continue ittrating and deleting all nodes with same value you can use this in your else statement..

else {
            prev->next = curr->next;
            free(curr);
            curr=prev; // this what you need
            break;  
        }

Answer 4

Nice implementation. I have found the following bugs:

1. When traversing the list, the head was ignored. Below, the while-loops have been replaced by a do-while for the search, view and delete functions.

2. As pointed out already, prev was not assigned a valid value in the delete function.

3. When deleting the head, prev->next was not changed. prev was not set anyway in this case. In the code below, a tail variable has been added. This way, prev can be set already at the beginning of the delete function. Otherwise, the list Also it has been made sure, that global variables like curr and prev always have a valid value.

I hope this may be of use. Cheers, Michael

Modified code:

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

struct Node
{
  int data;
  struct Node *next;
}*head,*temp,*curr,*prev,*tail;

/*   Prototypes   */
void AddNode(int value);
int  CountNode();
void SearchNode(int value);
void ViewAll();
void DeleteNode(int value);

/* Main */
int main()
{
  int choice,value;
  printf("\n\n\n\t\t\tCircular Linked List\n\n\t\t\tSyed Danish Ali\n\n\t\t\tUBIT\n\n\n\t\t\t\tHit ENTER to continue...");
  while(getche() != '\r')
  {
  }
  do
  {
    system("cls");
    printf("\n\nMENU\n=====\n\n[1] ADD\n[2] COUNT\n[3] SEARCH\n[4] VIEW ALL\n[5] DELETE\n[6] EXIT\n\nCHOICE:\t");
    scanf("%d",&choice);
    if(choice == 1){
      printf("Enter data:\t"); scanf("%d",&value);
      AddNode(value);
      getch();
    } else if(choice == 2){
      printf("\n\n%d Node(s).",CountNode());
      getch();
    }else if(choice == 3){
      printf("Enter the data to search:\t");
      scanf("%d",&value);
      SearchNode(value);
      getch();
    } else if(choice == 4){
      ViewAll();
      getch();
    } else if(choice == 5){
      printf("Enter the data to search:\t");
      scanf("%d",&value);
      DeleteNode(value);
      getch();
    } else if(choice == 6){
      return 0;
    }
  } while(1);
}

void AddNode(int value)
{
  temp = (struct Node *) malloc (sizeof(struct Node));
  temp->data = value;

  if(head == NULL)
  {
    head = temp;
    tail = temp;
    curr = temp;
    temp->next = head;
  } else {
    // remember prev if needed
    prev       = tail;
    prev->next = temp;
    tail       = temp;
    curr       = temp;
    temp->next = head;
  }
  // remember tail
  printf("\n\nNode added.");
  }
  int CountNode(){
  int k = 0;
  if(head == NULL){
    return 0;
  } else {
    temp = head;
    // count head, too
    do
    {
      k++;
      temp = temp->next;
    } while(temp != head);
    return k;
  }
}

void SearchNode(int value){
  int flag = 0,k = 0;
  if (head == NULL){
     printf("\n\nList is empty.");
  } else {
    curr = head;
    // search head, too
    do
    {
      if (curr->data == value){
        flag = 1;
        printf("\n\n%d found at index # %d.",value,k);
        curr = curr->next;
      } else {
        curr = curr->next;
        k++;
      }
    } while(curr != head);
  }
  if(flag == 0)
  {
    printf("\n\nValue %d not found.",value);
  }
}

void ViewAll(){
  int counter = 0;
  if(head == NULL)
  {
    printf("\n\nList is empty.");
  } else {
    curr = head;
    printf("LIST GENERATED:\n===============\n");
    // show head, too
    do
    {
      printf("\nElement # %d:\nData:\t%d",counter+1,curr->data);
      curr = curr->next;
      counter++;
    } while(curr != head);
  }
}

void DeleteNode(int value){
  int flag = 0;
  if(head == NULL)
  {
    printf("\n\nList is empty.");
  } else {
    curr = head;
    prev = tail;
    // delete head, too, if it contains the searched value
    do{
      if(curr->data == value)
      {
        printf("\n\nValue found.");
        flag = 1;
        if(curr == head)
        {
          if(tail == head)
          {
            // list contains only one element
            free(head);
            temp = NULL;
            head = NULL;
            prev = NULL;
            curr = NULL;
            tail = NULL;
          } else {
            // list contains more than one element
            temp = curr;
            free(temp);
            temp = tail; // ensure, temp is valid
            curr = head->next;
            head = curr;
            tail->next = curr;
            // prev = tail;
          }

        } else {
          // curr != head
          prev->next = curr->next;
          if(curr == tail){
            tail = prev; // tail may be head as well, now
          } else {
            // nothing to do ;O)
          }
          free(curr);
          curr = prev->next;
          temp = prev; // ensure, temp is valid
        }
      } else {
        // don't delete, just advance
        prev = curr;
        curr = curr->next;
      }
    } while(curr != head);
    printf("Node deleted.");
  }
  if(flag == 0)
  {
    printf("\n\nValue not found.");
  }
}