Search code examples
cdoubly-linked-list

Removing node from doubly linked list gives segmentation fault - C


I have written a program that can can add char characters to the start of a doubly linked list. Now once I have this list, the aim of my program is to remove certain char character(s) from the list entirely. For example (using curly brackets only for representative purposes): if list consists of { a, b, b, a, c }, then my program can remove all "b" from the list to make it { a, a, c}. Moreover, if my list is {b, a, c, a} or {a, c, a, b} and if I want to remove "b" then the program works fine for both cases and gives me {a, c, a}.

But there's a number of issues (for all cases assume I want to remove "b"):

  1. if my list is {b, a, b, a, c} ("b" at front and somewhere in middle), I get segmentation fault (I think it has to do with using cursor in the while loop, but I don't know why exactly and how to fix it)
  2. if my list is {a, b, b, a, c, b} ("b" in middle and at last) then output gives me weird symbols (I'm assuming its a memory fault, don't know why)

Here is the code I am using:

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

struct list
{
   int data;
   struct list* next;
   struct list* prev;
};

struct list* head; // global variable - pointer to head node of list.
struct list* last; // global variable - pointer to last node of list

//Creates a new list and returns pointer to it.
struct list* GetNewNode(char x)
{
   struct list* newNode
       = malloc(sizeof(struct list));
   newNode->data = x;
   newNode->prev = NULL;
   newNode->next = NULL;
   return newNode;
}

//Inserts a list at head of doubly linked list
void InsertAtHead(char x)
{
   struct list* newNode = GetNewNode(x);
   if(head == NULL)
   {
       head = newNode;
       return;
   }

   head->prev = newNode;
   newNode->next = head;
   head = newNode;
   struct list* temp = head;

   while (temp->next != NULL) temp = temp->next;
   last = temp;
}

void remove_element (char character)
{
   struct list * cursor, *previous, *store_el;
   //int boolean = 0;

   if (head == NULL) return;
   else
   {
       cursor = head;
       while(cursor != NULL)
       {
           if (cursor->data == character)
           {
               if (cursor->prev == NULL)
               {
                  // printf("deleting from front\n");
                   previous = head;
                   head = head->next;
                   head->prev = NULL;
                   //boolean = 1;
                   //free(previous);
               }
               if (cursor->next == NULL)
               {
                   //printf("deleting from back\n");
                   previous = last;
                   last = last->prev;
                   last->next = NULL;
                   //boolean = 1;
                   //free(previous);
               }
               else
               {
                  // printf("deleting from middle\n");
                   previous = cursor;
                   cursor = cursor->next;
                   cursor->prev = previous->prev;
                   store_el = previous->prev;
                   store_el->next = cursor;
                   cursor = head;

               }
               free(previous);
               //printf("head data = %c\n", cursor->data);
           }
           cursor = cursor->next;
       }
   }
}

//Prints all the elements in linked list in forward traversal order
void Print()
{
   struct list* temp = head;
   printf("Forward: ");
   while(temp != NULL)
   {
       printf("%c ",temp->data);
       temp = temp->next;
   }
   printf("\n");
}

int main()
{

   char character;
   /*Driver code to test the implementation*/
   head = NULL; // empty list. set head as NULL.

   // Calling an Insert and printing list before and after deletion of character
   InsertAtHead('c');
   InsertAtHead('a');
   InsertAtHead('b');
   InsertAtHead('b');
   InsertAtHead('a');
   Print();
   printf("After deletion:\n");
   remove_element ('b');
   Print();
}

Solution

  • /* 
    *I changed the name of your variable 'last' to 'tail'
    *I removed the code at the end of your InsertAtHead function
    *I added "tail = newNode;"
    *I changed the name of your variable 'previous' to 'garbage'
    *I removed your variable 'store_el' completely.
    *I could have changed the whole code in your remove element function because the 3 cases are unnecessary but anyway.
    */
    //Inserts a list at head of doubly linked list
    void InsertAtHead(char x){
        struct list* newNode = GetNewNode(x);
    
        if (head == NULL){
            head = newNode;
            tail = newNode;
            return;
        }
    
        head->prev = newNode;
        newNode->next = head;
        head = newNode;
    }
    
    void remove_element (char character){
        struct list * cursor,  *garbage;
    
        cursor = head;
        while(cursor != NULL){
            if (cursor->data == character){
                    garbage = cursor;
    
                    if (cursor->prev == NULL){
                        head = head->next;
                        If (head!=NULL) head->prev = NULL;
                        cursor=head;
                    }else if (cursor->next == NULL){
                        tail = tail->prev;
                        tail->next = NULL;
                        cursor=NULL;
                    }else{
                        garbage->prev->next = garbage->next;
                        garbage->next->prev = garbage->prev;
                        cursor=cursor->next;
                    }
    
                    free(garbage);
            } else cursor=cursor->next;
        }
    }
    

    Try it now.

    The problem with your code was that you were using the memory you freed.

    /*
    *cursor and previous point to the same memory address
    *you free the memory that the variable previous points so the cursor points to that freed memory 
    *when you save the next address to the cursor using that freed memory you create an undefined behaviour (your code may work or may not)
    */
    cursor = head;
            while(cursor != NULL)
            {
                if (cursor->data == character)
                {
                    if (cursor->prev == NULL)
                    {
                        previous = head;
                        head = head->next;
                        head->prev = NULL;
                        free(previous);
    ...
    cursor=cursor->next;
    

    The Improved Code:

    #include<stdio.h>
    #include<stdlib.h>
    
    //The type of your variable data was wrong. I changed it to char
    struct list{
        char data;
        struct list *prev, *next
    };
    
    void remove_element (char character){
        struct list * cursor,  *garbage;
    
        cursor = head;
        while(cursor != NULL){
            if (cursor->data == character){
                    garbage = cursor;
    
                    if (garbage->prev!=NULL ) garbage->prev->next = garbage->next;
                    if (garbage->next!=NULL ) garbage->next->prev = garbage->prev;
                    cursor=cursor->next;
    
                    if (head==garbage) head=cursor;
                    //Basically the tail variable has no use for your current program.
                    //if (tail==garbage) tail=garbage->prev;
    
                    free(garbage);
            } else cursor=cursor->next;
        }
    }