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
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.