Home > database >  Int linked list in c throwing segmentation fault
Int linked list in c throwing segmentation fault

Time:04-19

Inserting into my linked list is causing a segmentation fault and I'm not sure why. It's an int linked list. It works sometimes and then other times not. I can't see where it would be going wrong? Maybe it has something to do with when I create the new linked list. As the linked list insert last method is working during file reading but not when I create a new list.

LinkedList* createLinkedList()
{
    LinkedList* list;

    list = (LinkedList*)malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    list->length = 0;

    #ifdef DEBUG
    printf("Linked list. Creation of list complete. Checking list length. %d \n", list->length);
    #endif

    return list;
}

void insertLast(LinkedList* list, int entry)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = entry;

    /*If list is empty*/
    if(list->length == 0)
    {
        list->head = newNode;
        list->tail = newNode;
    }
    else
    {
        newNode->prev = list->tail;
        /*if this is the second item in the list*/
        if(list->length == 1)
        {
            list->head->next = newNode;
        }
        else
        {
            list->tail->next = newNode;
        }
    }
    
    list -> tail = newNode;
    list->length  ;
    #ifdef DEBUG
    printf("Linked List. Insert last complete. Checking list length. %d\n", list->length);
    #endif
}

This works

int main (void)
{
    LinkedList* list = createLinkedList();
    insertLast(list, 1);
}

but this doesn't

int shortestSeekTimeFirst(LinkedList* list)
{
    LinkedList* usedDisks = createLinkedList();

    int data = list->head->data;
    insertLast(usedDisks, data);
    insertLast(usedDisks, list->head->next->data);
}

CodePudding user response:

You never want to blindly dereference a pointer that could be NULL.

In shortestSeekTimeFirst() you directly access list->head->next->data without checking if any of the pointers are valid, so if any of list, list->head, or even list->head->next is NULL your program will segfault.

CodePudding user response:

This function insertLast is incorrect.

void insertLast(LinkedList* list, int entry)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = entry;

    /*If list is empty*/
    if(list->length == 0)
    {
        list->head = newNode;
        list->tail = newNode;
    }
    else
    {
        newNode->prev = list->tail;
        /*if this is the second item in the list*/
        if(list->length == 1)
        {
            list->head->next = newNode;
        }
        else
        {
            list->tail->next = newNode;
        }
    }
    
    list -> tail = newNode;
    list->length  ;
    #ifdef DEBUG
    printf("Linked List. Insert last complete. Checking list length. %d\n", list->length);
    #endif
}

In this if statement

    if(list->length == 0)
    {
        list->head = newNode;
        list->tail = newNode;
    }

neither the data member prev nor the data member next of the new node is set to NULL. They are uninitialized and have indeterminate values.

The same problem exists when the list is not empty that is neither the data member prev nor the data member next of the new node is set.

The function can be written simpler

 int insertLast( LinkedList *list, int entry )
 {
     Node* newNode = malloc( sizeof( Node ) );
     int success = newNode != NULL;

     if ( success )
     {
         newNode->data = entry;
         newNode->next = NULL;
         newNode->prev = list->tail;

         if ( list->tail == NULL )
         {
             list->head = newNode;
         }
         else
         {
             list->tail->next = newNode;
         }  

         list->tail = newNode; 
         list->length  ;
     }

     return success;
 }

As for this code snippet

int shortestSeekTimeFirst(LinkedList* list)
{
    LinkedList* usedDisks = createLinkedList();

    int data = list->head->data;
    insertLast(usedDisks, data);
    insertLast(usedDisks, list->head->next->data);
}

then after this declaration

    LinkedList* usedDisks = createLinkedList();

the data members head and tail of the list are equal to NULL. So at least this statement

    int data = list->head->data;

invokes undefined behavior.

  • Related