I am a begginer and trying to learn data structres. I wrote a code that erases an element from the linked list. If the element alreay exists in the list, no problem happens during compiling and running. But, when I try to erase an element which does not exist in the list, a segmentation fault happens even I've already coded that case. Can you please give it a look and help me?
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int x;
struct node *next;
}node;
void addElement(node *r, int x)
{
for(; r->next!=NULL; r=r->next);
r->next=(node*)malloc(sizeof(node));
r->next->x=x;
r->next->next=NULL;
}
node* add_Element_inorder(node *r, int x)
{
if(r==NULL)
{
r=(node*)malloc(sizeof(node));
r->next=NULL;
r->x=x;
return r;
}
if(r->x>x)
{
node*tmp=(node*)malloc(sizeof(node));
tmp -> x = x;
tmp->next=r;
return tmp;
}
node *iter=r;
while(iter->next!=NULL && iter->next->x < x)
{
iter=iter->next;
}
node*tmp=(node*)malloc(sizeof(node));
tmp->next = iter->next;
iter->next=tmp;
tmp->x=x;
return r;
}
void print_Linked_L(node *r)
{
node* iter = r;
printf("%d ", iter->x);
iter=iter->next;
while(iter != NULL)
{
printf("%d ", iter->x);
iter=iter->next;
}
}
node* erase_Element(node *r, int x)
{
node*iter=r;
if(iter->x == x)
{
r=r->next;
free(iter);
return r;
}
while(iter->next->x != x && iter->next!=NULL)
{
iter=iter->next;
}
if(iter->next==NULL)
{
printf("Number does not exist.");
return r;
}
node *temp=iter->next;
iter->next=iter->next->next;
free(temp);
return r;
}
int main()
{
node *root = (node*)malloc(sizeof(node));
root=NULL;
root= add_Element_inorder(root, 400);
root= add_Element_inorder(root, 40);
root= add_Element_inorder(root, 4);
root= add_Element_inorder(root, 450);
root= add_Element_inorder(root, 50);
node *iter=root;
print_Linked_L(root);
root =erase_Element(root,45);
printf("\n");
print_Linked_L(root);
return 0;
}
In fact all functions are incorrect.
For example in this function
void addElement(node *r, int x)
{
for(; r->next!=NULL; r=r->next);
r->next=(node*)malloc(sizeof(node));
r->next->x=x;
r->next->next=NULL;
}
there is no check whether t is equal to NULL. The function should be defined at least like
node * addElement( node *head, int x )
{
node *new_node = malloc( sizeof( node ) );
new_node->x = x;
if ( head == NULL )
{
new_node->next = head;
head = new_node;
}
else
{
node *current = head;
while ( current->next != NULL ) current = current->next;
new_node->next = NULL;
current->next = new_node;
}
return head;
}
In the function add_Element_inorder there are two many duplicated code. The function can be defined simpler.
node * add_Element_inorder( node *head, int x)
{
node *new_node = malloc( sizeof( node ) );
new_node->x = x;
if ( head == NULL || x < head->x )
{
new_node->next = head;
head = new_node;
}
else
{
node *current = head;
while ( current->next != NULL && !( x < current->next->x ) )
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
return head;
}
The function print_Linked_L can invoke undefined behavior for an empty list when the pointer to the head node is equal to NULL.
void print_Linked_L(node *r)
{
node* iter = r;
printf("%d ", iter->x);
//...
The function can be define like
void print_Linked_L( const node *head )
{
for ( ; head != NULL; head = head->next )
{
printf( "%d -> ", head->x );
}
puts( "null" );
}
The function erase_Element again can invoke undefined behavior when there is no node with the target value due to incorrect order of condition in the while statement
while(iter->next->x != x && iter->next!=NULL)
That is at first you need to check whether iter->next != NULL and only after that check whether its value is unequal to x.
The function can be defined the following way
node * erase_Element( node *head, int x )
{
if ( head != NULL )
{
if ( head->x == x )
{
node *tmp = head;
head = head->next;
free( tmp );
}
else
{
node *current = head;
while ( current->next != NULL && current->next->x != x )
{
current = current->next;
}
if ( current->next != NULL )
{
node *tmp = current->next;
current->next = current->next->next;
free( tmp );
}
else
{
printf( "Number %d does not exist in the list.\n", x );
}
}
}
return head;
}
The function main starts with memory leak
int main()
{
node *root = (node*)malloc(sizeof(node));
root=NULL;
At first memory was allocated and then at once the returned address was lost due to overwriting the pointer root.
Here is a demonstrative program that shows the updated function definitions.
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int x;
struct node *next;
} node;
node * addElement( node *head, int x)
{
node *new_node = malloc( sizeof( node ) );
new_node->x = x;
if ( head == NULL )
{
new_node->next = head;
head = new_node;
}
else
{
node *current = head;
while ( current->next != NULL ) current = current->next;
new_node->next = NULL;
current->next = new_node;
}
return head;
}
node * add_Element_inorder( node *head, int x)
{
node *new_node = malloc( sizeof( node ) );
new_node->x = x;
if ( head == NULL || x < head->x )
{
new_node->next = head;
head = new_node;
}
else
{
node *current = head;
while ( current->next != NULL && !( x < current->next->x ) )
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
return head;
}
void print_Linked_L( const node *head )
{
for ( ; head != NULL; head = head->next )
{
printf( "%d -> ", head->x );
}
puts( "null" );
}
node * erase_Element( node *head, int x )
{
if ( head != NULL )
{
if ( head->x == x )
{
node *tmp = head;
head = head->next;
free( tmp );
}
else
{
node *current = head;
while ( current->next != NULL && current->next->x != x )
{
current = current->next;
}
if ( current->next != NULL )
{
node *tmp = current->next;
current->next = current->next->next;
free( tmp );
}
else
{
printf( "Number %d does not exist in the list.\n", x );
}
}
}
return head;
}
int main(void)
{
node *root = NULL;
root = add_Element_inorder( root, 400 );
root = add_Element_inorder( root, 40 );
root = add_Element_inorder( root, 4 );
root = add_Element_inorder( root, 450 );
root = add_Element_inorder( root, 50 );
print_Linked_L( root );
root = erase_Element( root, 45 );
print_Linked_L(root);
root = erase_Element( root, 400 );
print_Linked_L(root);
root = erase_Element( root, 40 );
print_Linked_L(root);
root = erase_Element( root, 4 );
print_Linked_L(root);
root = erase_Element( root, 450 );
print_Linked_L(root);
root = erase_Element( root, 50 );
print_Linked_L(root);
return 0;
}
The program output is
4 -> 40 -> 50 -> 400 -> 450 -> null
Number 45 does not exist in the list.
4 -> 40 -> 50 -> 400 -> 450 -> null
4 -> 40 -> 50 -> 450 -> null
4 -> 50 -> 450 -> null
50 -> 450 -> null
50 -> null
null