oldDoctor oldDoctor - 4 months ago 16
C Question

Deleting a node at a given position in Linked List

Given a singly linked list and a position, i am trying to delete a linked list node at a specific position.
CODE:

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

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

void printList(struct node* head_ref)
{
//struct node* head_ref = (struct node*)malloc(sizeof(struct node));

if(head_ref == NULL)
printf("The list is empty");

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

void insert_beg(struct node **head_ref,int new_data)
{
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}

void delete(struct node **head_ref,int position)
{
int i=1;
if(*head_ref == NULL)
return;

struct node *tails,*temp = *head_ref;
if(position == 0)
{

*head_ref = temp->next;
free(temp);
return;
}

while(temp->next!=NULL)
{
tails = temp->next;
temp = temp->next;

if(i == position)
{
tails->next = temp->next;
free(temp);
return;
}

i++;
}

}

int main()
{
struct node *head = NULL;
insert_beg(&head,36);
insert_beg(&head,35);
insert_beg(&head,34);
insert_beg(&head,33);

printList(head);
int position;
printf("Enter the position of the node u wanna delete\n");
scanf("%d",&position);

delete(&head,position);
printf("\n");
printList(head);
}


Whenever I am trying to delete a node above position 0, I am getting 0 in that specific position instead of nothing. Could I know where I am going wrong?
For eg my list is : 33 34 35 36
My Output: 33 0 35 36 (while attempting to delete node 1)
Valid Output: 33 35 36

Answer

The problem occurs due to this wrong statement

while(temp->next!=NULL)
{ 
    tails = temp->next;
    ^^^^^^^^^^^^^^^^^^^
    temp = temp->next;

In this case tails and temp are the same nodes. And if temp is deleted then you set the data member next of the deleted node to temp->next

    if(i == position)
    {
        tails->next = temp->next;
        ^^^^^^^^^^^^^^^^^^^^^^^^^

Here tails is node that will be deleted.

You should change the data member next of the node before the deleted node. So the wrong statement should be updated like

while(temp->next!=NULL)
{ 
    tails = temp;
    ^^^^^^^^^^^^^
    temp = temp->next;

As for me then I would write the function the following way

int delete( struct node **head, size_t position )
{
    struct node *prev = NULL;

    size_t i = 0;

    while ( i != position && *head != NULL ) 
    {
        prev = *head;
        head = &( *head )->next;
        ++i;
    }

    int success = *head != NULL;

    if ( success )
    {
        struct node *tmp = *head;

        if ( prev == NULL )
        {
            *head = ( *head )->next;
        }
        else
        {
            prev->next = ( *head )->next;
        }

        free( tmp );
    }

    return success;
}