CODEWITHSUNDEEP
clistdata-structures
Mistu4u
Mistu4u

Reputation: 5416

What more does the code need to delete a node from a linked list successfully?

I want to delete a given node from a linked list by the node's index number (serial number). So what I tried to do in my function is that, first I have taken the user input of the index number. Then I used two node type pointers temp and current. I started traversing the list with current and when the index number of the node matches with the user input, I tried to delete the node. So far it is correct. I am facing problem with the deletion logic. Here is the code I tried:

void delete_node(struct node **start,int index_no)
{    
    int counter=0;
    struct node *temp, *current;

    temp=(struct node *)malloc(sizeof(struct node));
    current=(struct node *)malloc(sizeof(struct node));
    current=*start;

    while(current->next!=NULL)
    {
        counter++;
        if(counter==index_no)
        {
            temp= current->next;
            free(current);
            /*I guess some code is missing here. Help me finding the logic.*/
        }
        else
        {
            printf("\n The index number is invalid!!");
        }
    }
}

The commented portion lacks the deletion logic. Also, I have a feeling that this code is not space and time-efficient. If it is so, please suggest to a way to make it more compact.

Upvotes: 1

Views: 121

Answers (2)

wildplasser
wildplasser

Reputation: 44250

Deleting from a linked list is actually:

  • find the pointer that points to us
  • (if found) make it point to our .next pointer instead
  • delete our node.

In order to change the pointer that points to us, we need a pointer to it: a pointer to pointer. Luckily the first argument already is a pointer to pointer, it presumably points to the head pointer that points to the first list item.

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

void delete(struct node **pp, int num) {
    struct node *del;
    int counter;

    for (counter=0; *pp; pp= &(*pp)->next) {
        if(counter++ == num) break;
        }

    if (!*pp) { printf("Couldn't find the node(%d)\n", num); return; }

    /* if we get here, *pp points to the pointer that points to our current node */

    del = *pp;
    *pp = del->next;
    free(del);
  }

Upvotes: 1

T Percival
T Percival

Reputation: 8674

Why are you allocating two nodes in the delete function, then leaking their memory? It seems they should be initialized to start or one of its successors.

You also need to update the next pointer in the previous element and potentially also the start (head) of the list if the removed element was the first (ie. index_no == 1).

You also have an off-by-one error where the final node can never be deleted, because only a node with a ->next pointer will be considered for deletion.

Suggested reading: A Tutorial on Pointers and Arrays in C.

Upvotes: 1

Related Questions