How To Write C Functions That Modify The Head Pointer Of A Linked List

Last Updated on December 13, 2022 by Prepbytes

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Some functions like print data in a list or changing data of nodes in the list do not require changing the head pointer of the linked list.

But, many functions require an update of the head pointer of the list like deleting the first node of the list, inserting a node at the beginning of the list, inserting a node at the end (head is updated only when the node that is being inserted is the first node of the list) and many more.

In this article, we are going to look at multiple ways of updating the head pointer of our linked list:

1) Making head pointer global

In this approach, we declare the head pointer globally and update it within any function where we want to update it.

Code Implementation

// head pointer declared globally
struct Node *head = NULL;
// this function will delete the first node of Linked list
void deleteFirst()
{
    if(head != NULL)
    {
    // old value of head is stored in temp     
    struct Node *temp = head;
        
    // update the head pointer as next node
    head = head->next;

    // free the memory space occupied by the previous head
    // as it has been deleted from the list
    free(temp);
    }
}

Time Complexity: O(1), since we have access to the head, we will only need constant time to update it to its next node.

Space Complexity: O(1), since we have access to the head, we will only need constant space to update it to its next node

However, there are certain demerits of this approach:

• This method is not useful if there is more than one linked list in our program
• Since the head is global, all functions can access and modify it, which can cause unpredictable results in projects.
• If there are multiple linked lists, we will require separated global head pointers for each linked list with a different name.

2) Returning the head pointer

In this approach, we return the modified head pointer from the function which changes the head and update the head with the returned value.

Code Implementation

// this function will delete the first node of the list
struct Node* deleteFirst(struct Node *head)
{
    if(head != NULL)
    {
    // old value of head is stored in temp
    struct Node *temp = head;

    // update the head pointer as next node
    head = head->next;

    // free the memory space occupied by the previous head
    // as it has been deleted from the list
    free(temp);
    }

    return head;
}
// inside main function, the call will look like:
head = deleteFirst(head);

Note: If instead of head = deleteFirst(head), we are using just deleteFirst(head) in the above code, so it will mean that we are not assigning the updated head node to a pointer, so it will lead to the wrong result.

Time Complexity: O(1), since we have access to the head, we will only need constant time to update it to its next node.

Space Complexity: O(1), since we have access to the head, we will only need constant space to update it to its next node

This approach is much better than the previous one, but there is only one problem: if the user forgets to assign the returned value, the compiler will also not raise any error. This will lead to wrong results.

3) Using double pointers

• In C language, we know that if we have to modify a variable of a function using some another function, we need to pass the pointer to that variable in the function.
• In the same way, If we want to update the head pointer, we need to pass a pointer to the head variable.
• This is called a double-pointer because the head is itself a pointer and we are passing a pointer to head pointer to the function where we want to update head.

Code Implementation

void deleteFirst(struct Node **head_ref)
{
    if(*head_ref != NULL)
    {
    // old value of head is stored in temp
    struct Node *temp = *head_ref;

    // update the head pointer as next node
    *head_ref = (*head_ref)->next;

    // free the memory space occupied by the previous head
    // as it has been deleted from the list
    free(temp);
    }
}

Time Complexity: O(1), since we have access to the head, we will only need constant time to update it to its next node.

Space Complexity: O(1), since we have access to the head, we will only need constant space to update it to its next node

This approach is the best among all the approaches, and it is recommended to use this when we want to update the head pointer.

So, in this blog, we have tried to explain various approaches to how you can write C functions to modify the head pointer of a linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.