deleting node from a singly linked list

Question

I have a simple function that searches for a node with a given key from a single linked list and deletes it. The function works when the node with that holds the given key is everywhere except if that node is the head of the list. Why does this happen?

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


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

void printlist(struct Node* node){
    while(node!=NULL){
        printf("%d", node->data);
        node = node->next;
    }
    printf("\n");
}

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
void deleteNode(struct Node* head, int key){
    if(head->data==key){
        head = head->next;
    }
    else {
        while(head->next->data!=key){
            head = head->next;
        }
        head->next = head->next->next;
    }
}

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    deleteNode(first, 2);  
    printlist(first); // prints 13

    deleteNode(first, 1);
    printlist(first); // still prints 13
}

Answer 1

The function deals with a copy of the original head. So changing of the copy does not influence on the original node. You should either pass the head node by reference through pointer or return from the function the changed head node. Also you have to check in the beginning of the function whether the head node is equal to NULL. Otherwise the function can invoke undefined behavior.

For example

void deleteNode( struct Node **head, int key )
{
    while( *head != NULL && ( *head )->data != key ) head = &( *head )->next;

    if ( *head != NULL ) *head = ( *head )->next;
}

And call it like

deleteNode( &first, 1 );

Here is a demonstrative program

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

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

void printlist(struct Node* node){
    while(node!=NULL){
        printf("%d", node->data);
        node = node->next;
    }
    printf("\n");
}

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
void deleteNode( struct Node **head, int key )
{
    while( *head != NULL && ( *head )->data != key ) head = &( *head )->next;

    if ( *head != NULL ) *head = ( *head )->next;
}

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    deleteNode(&first, 2);  
    printlist(first); // prints 13

    deleteNode(&first, 1);
    printlist(first); // still prints 13
}

Its output is

123
13
3

Or

struct Node * deleteNode( struct Node *head, int key )
{
    if ( head != NULL )
    {
        if ( head->data == key )
        {
            head = head->next;
        }
        else 
        {
            struct Node *current = head;
            while( current->next != NULL && current->next->data != key )
            {
                current = current->next;
            }
            if ( current->next != NULL ) current->next = current->next->next;
        }
    }

    return head;
}

and call it like

first = deleteNode( first, 1 );

Here is another demonstrative program

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

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

void printlist(struct Node* node){
    while(node!=NULL){
        printf("%d", node->data);
        node = node->next;
    }
    printf("\n");
}

/* Given a reference (pointer to pointer) to the head of a list 
   and a key, deletes the first occurrence of key in linked list */
    struct Node * deleteNode( struct Node *head, int key )
    {
        if ( head != NULL )
        {
            if ( head->data == key )
            {
                head = head->next;
            }
            else 
            {
                struct Node *current = head;
                while( current->next != NULL && current->next->data != key )
                {
                    current = current->next;
                }
                if ( current->next != NULL ) current->next = current->next->next;
            }
        }

        return head;
    }

int main(){

    struct Node* first = (struct Node*)malloc(sizeof(struct Node));
    struct Node* second = (struct Node*)malloc(sizeof(struct Node));
    struct Node* third = (struct Node*)malloc(sizeof(struct Node));
    first->data = 1;
    second->data = 2;
    third->data = 3;
    first->next = second;
    second->next = third;
    third->next = NULL;

    printlist(first); // prints 123

    first = deleteNode(first, 2);  
    printlist(first); // prints 13

    first = deleteNode(first, 1);
    printlist(first); // still prints 13
}

Again its output is

123
13
3

In general nodes of lists are allocated dynamically. So the function that deletes nodes should also free the deleted node or return it from the function.

Answer 2

When you call this function: void deleteNode(struct Node* head, int key) with a first argument that is a pointer to a Node struct (as you do twice in your main), then what the function receives as its first argument is a copy of the pointer you gave!

You probably know that a function: void Increment(int n) can do whatever it likes to the n it's passed, without changing the variable in the calling module. So, if you want the function to actually change the value in the calling block, you give it a pointer:

void Increment(int* n) {
    ++(*n);
}

Likewise, if you want a function to change a pointer, then you have to pass it a pointer to that pointer. Try this:

void deleteNode(struct Node** head, int key){
    Node* temp = *head;
    if(temp->data==key){
        *head = temp->next; // Only need to change *head if its the first one ...
    }
    else {
        while(temp->next->data!=key){
            temp = temp->next;
        }
        temp->next = temp->next->next; // ... else we have already changed the actual "links"
    }
}

And, in main, use:

deleteNode(&first, 2);

and:

deleteNode(&first, 1);

Let us know what happens.

Note: Incidentally, this is not "best possible code" - by removing a link without actually deleting the object pointed to, you are creating a memory leak.

Note 2: Also, if the key is not found, your code will "fall off" the end of the list, when it finds a NULL next pointer!