clinked-listvalgrindgcc7

Linked list does not remove the second (2) record in list but works fine for all others


I really do not understand what happens with my Program because it seems that it works fine when I try to remove any record found in linked List.

The problem comes when I try to remove the record 2 it does not remove it and prints instead 0.

Here is the working program which can be verified:

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

struct node{
    int data;
    struct node *next;
};

void printList( struct node  *head );
void freeList ( struct node **head );
void createList ( struct node **head, const int val );
int searchInList( struct node **head);
int deleteInList( struct node **head, const int val );

int main ( void ){
    struct node *head = NULL;

    int listLen = 5;
    int remove = 3;

    createList ( &head , listLen );
    printf("\t\tBefore:\n");
    printList( head );

    if ( deleteInList( &head, remove ) == -1 ){
        printf("No result found!\n\t\tNothing here to be deleted\n");
    }else{
        printf("\t\tAfter:\n");
        printList( head );
    }

    freeList( &head );
}

void printList( struct node *head ){
    struct node *current = head;

    while ( current != NULL ){
        printf("Data = %d\n",  current->data );
        current = current->next;
    }
    printf("\n\n");
}

void freeList ( struct node **head ){
    struct node *current = *head;
    while ( current != NULL ){
        struct node *tmp = current->next;
        free( current );
        current = tmp;
    }
}

void createList ( struct node **head, const int val ){
    struct node *current;
    for( int i = val ; i > 0 ; i-- ) {
        current = malloc( sizeof( struct node ) );
        current->data = i;
        current->next  = *head;
        *head = current;
    }
}

int searchInList( struct node ** head) {
    int retval = -1;
    struct node *next = NULL;

    if (*head == NULL) {
        return -1;
    }

    next = (*head)->next;
    retval = (*head)->data;
    free(*head);
    *head = next;

    return retval;
}

int deleteInList( struct node ** head, const int val ) {
    struct node *previous, *current;

    if (*head == NULL) {
        return -1;
    }

    if ( ( *head )->data == val ) {
        return searchInList( head );
    }

    current = ( *head )->next;
    previous = current;

    while ( current ) {
        if ( current->data == val ) {
            previous->next = current->next;
            free( current );
            return val;
        }

        previous = current;
        current  = current->next;
    }
    return -1;
}

Output:

        Before:
Data = 1
Data = 2
Data = 3
Data = 4
Data = 5


        After:
Data = 1
Data = 2
Data = 4
Data = 5

And the program looks fine, but if I replace int remove = 3; with int remove = 2; it does not work because i get:

Data = 1
Data = 2
Data = 3
Data = 4
Data = 5


        After:
Data = 1
Data = 0
Data = 3
Data = 4
Data = 5

When the expected Output should be:

        After:
Data = 1
Data = 3
Data = 4
Data = 5

And looking at Valgrind I noticed that I have one free more:

==9107== HEAP SUMMARY:
==9107==     in use at exit: 0 bytes in 0 blocks
==9107==   total heap usage: 6 allocs, 7 frees, 1,104 bytes allocate

And I cannot figure out whats happening.

Here is the whole Valgrind report:

==9107== Memcheck, a memory error detector
==9107== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==9107== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==9107== Command: ./program
==9107== 
        Before:
Data = 1
Data = 2
Data = 3
Data = 4
Data = 5


        After:
Data = 1
==9107== Invalid read of size 4
==9107==    at 0x400714: printList (program.c:39)
==9107==    by 0x4006D2: main (program.c:29)
==9107==  Address 0x5204130 is 0 bytes inside a block of size 16 free'd
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x4008C7: deleteInList (program.c:97)
==9107==    by 0x4006AB: main (program.c:25)
==9107==  Block was alloc'd at
==9107==    at 0x4C2DB8F: malloc (vg_replace_malloc.c:299)
==9107==    by 0x4007AA: createList (program.c:57)
==9107==    by 0x400684: main (program.c:21)
==9107== 
Data = 2
==9107== Invalid read of size 8
==9107==    at 0x40072B: printList (program.c:40)
==9107==    by 0x4006D2: main (program.c:29)
==9107==  Address 0x5204138 is 8 bytes inside a block of size 16 free'd
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x4008C7: deleteInList (program.c:97)
==9107==    by 0x4006AB: main (program.c:25)
==9107==  Block was alloc'd at
==9107==    at 0x4C2DB8F: malloc (vg_replace_malloc.c:299)
==9107==    by 0x4007AA: createList (program.c:57)
==9107==    by 0x400684: main (program.c:21)
==9107== 
Data = 3
Data = 4
Data = 5


==9107== Invalid read of size 8
==9107==    at 0x400764: freeList (program.c:48)
==9107==    by 0x4006DE: main (program.c:32)
==9107==  Address 0x5204138 is 8 bytes inside a block of size 16 free'd
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x4008C7: deleteInList (program.c:97)
==9107==    by 0x4006AB: main (program.c:25)
==9107==  Block was alloc'd at
==9107==    at 0x4C2DB8F: malloc (vg_replace_malloc.c:299)
==9107==    by 0x4007AA: createList (program.c:57)
==9107==    by 0x400684: main (program.c:21)
==9107== 
==9107== Invalid free() / delete / delete[] / realloc()
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x400777: freeList (program.c:49)
==9107==    by 0x4006DE: main (program.c:32)
==9107==  Address 0x5204130 is 0 bytes inside a block of size 16 free'd
==9107==    at 0x4C2EDEB: free (vg_replace_malloc.c:530)
==9107==    by 0x4008C7: deleteInList (program.c:97)
==9107==    by 0x4006AB: main (program.c:25)
==9107==  Block was alloc'd at
==9107==    at 0x4C2DB8F: malloc (vg_replace_malloc.c:299)
==9107==    by 0x4007AA: createList (program.c:57)
==9107==    by 0x400684: main (program.c:21)
==9107== 
==9107== 
==9107== HEAP SUMMARY:
==9107==     in use at exit: 0 bytes in 0 blocks
==9107==   total heap usage: 6 allocs, 7 frees, 1,104 bytes allocated
==9107== 
==9107== All heap blocks were freed -- no leaks are possible
==9107== 
==9107== For counts of detected and suppressed errors, rerun with: -v
==9107== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)

I am on Linux mint 18.3 with GCC-7


Solution

  • In deleteInList:

      ...
      if ((*head)->data == val) {
        return searchInList(head);
      }
    
      current = (*head)->next;
      //  previous = current;   << this is wrong
      previous = *head;         // this is correct
    
      while (current) {
        if (current->data == val) {
      ...
    

    In your original code previous is the same as current during the first iteration.

    BTW: the searchInList function does not what it's name suggests.