C Program to Insert a Node at the Beginning of a Linked List

Introduction

A linked list is a dynamic data structure where each element, called a node, contains a data part and a pointer to the next node. To insert a node at the beginning of a linked list, you need to create a new node, set its next pointer to point to the current head of the list, and then update the head to this new node.

Example:

• Input: A linked list with nodes containing [20, 30, 40], and a new node with data 10.
• Output: The linked list after insertion will contain [10, 20, 30, 40].

Problem Statement

Create a C program that:

• Creates a singly linked list.
• Inserts a node at the beginning of the linked list.
• Displays the linked list after the insertion.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Function to Insert a Node at the Beginning: Write a function that creates a new node and inserts it at the beginning of the linked list.
4. Implement the Function to Display the Linked List: Write a function to traverse and display the elements of the linked list.
5. Create a Main Function: In the main() function, create the linked list, insert nodes at the beginning, and display the list.

C Program to Insert a Node at the Beginning of a Linked List

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

// Step 2: Define the Node Structure
struct Node {
    int data;
    struct Node* next;
};

// Function to insert a node at the beginning of the linked list
void insertAtBeginning(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;
}

// Function to display the linked list
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    // Insert elements at the beginning
    insertAtBeginning(&head, 40);
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);

    // Display the linked list
    printf("Linked List: ");
    displayList(head);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the list.

Function to Insert a Node at the Beginning

• The insertAtBeginning function takes a double pointer to the head of the linked list (head_ref) and the data to be inserted (new_data).
• A new node is allocated dynamically using malloc().
• The new node’s next pointer is set to point to the current head of the list.
• The head pointer is then updated to point to the new node, making it the new head of the list.

Function to Display the Linked List

• The displayList function traverses the linked list from the head and prints each node’s data, followed by an arrow (->), until it reaches the end (NULL).

Main Function

• The main function creates an empty linked list and inserts several nodes at the beginning using the insertAtBeginning function.
• After the nodes are inserted, the displayList function is called to display the linked list.

Output Example

Example Output:

Linked List: 10 -> 20 -> 30 -> 40 -> NULL

Conclusion

This C program demonstrates how to insert a node at the beginning of a linked list. It covers basic concepts such as dynamic memory allocation, pointer manipulation, and linked list traversal, making it a useful example for beginners learning data structures in C programming.