Insert node at beginning of linked list in c

Insert a node at the beginning of a linked list involves creating a new node, setting its next pointer to the current head of the list, and then updating the head pointer to the new node. This operation is simple and efficient with a time complexity of O(1).

The main code for insertion the node at the beginning of linked list is given below, Let insert the node with data 90 in list 10 ->20->30 ->40. 

Step 01: Node Structure in Linked List

A linked list is a collection of nodes, each consisting of two components data and pointer address.

struct Node {
int data; // Data held by the node
struct Node* next; // Pointer to the next node in the list
};

Here, we define a structure "Node" representing a node in the Linked List.

  • data: This integer will store the actual data for each node.
  • next: This pointer will point to the next node in the list, linking all nodes together.

The structure of a node in the linked list is described below.

Node Structure in Linked List

 Step 02: Consider a Singly-linked List 

Each node points to the next one in the list, and the last node points to NULL, indicating the end of the list.Consider a singly linked list consisting of four nodes, each containing specific values and addresses:

  • – The first node contains the value 10 and is located at address 350.
  • – The second node contains the value 20 and is located at address 380.
  • – The third node contains the value 30 and is located at address 700.
  • – The fourth node contains the value 40 and is located at address 900.

Each node points to the next node in the list, and the last node points to NULL, indicating the end of the list.

Example A Singly Linked List with four Nodes

Step 03: Create New Node for insertion (“ptr2”)

To insert a new node (suppose data=90 and address =1200) at the beginning of a singly linked list, first, create the new node and assign its data and address.

Create new Node in Linked list

 

Note: In this position, we need to take an additional pointer, “ptr2,” which will point to the new node.

Step 04: Insertion at beginning (ptr2 -> next = Head;)

  • ptr2 is the new node being inserted at the beginning of the list.
  • Head is the current starting node of the linked list.
  • ptr2->next = Head; links the new node (ptr2) to the current head node of the list.
  • After this, ptr2 becomes the new head of the linked list. Now, the Head pointer points to the second node of the list.

Insert Node at the beginning of Linked List

Step 05:Insertion at beginning (Head = ptr2;)

As after step 04: The Head pointer currently points to the second node of the list. To make Head point to the first node (the newly inserted node), we update Head to ptr2, as ptr2 already points to the new first node.

Insert Node at the beginning of Linked List - part 2

 


Code Example: Insert a Node at the Beginning of a Linked List

#include <stdio.h>
#include <stdlib.h>// Define the structure of a node
struct Node {
int data;
struct Node* next;
};// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) {
printf(“Memory allocation failed\n”);
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to insert a node at the beginning of the linked list
struct Node* insertAtBeginning(struct Node* head, int data) {
struct Node* newNode = createNode(data);

// Point the new node to the current head
newNode->next = head;

// The new node becomes the new head
return newNode;
}

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

// Main function
int main() {
// Manually creating the linked list
struct Node* head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
head->next->next->next = createNode(40);

printf(“Initial linked list: “);
displayList(head);

// Insert a new node with value 5 at the beginning
int newData = 90;

printf(“\nInserting %d at the beginning…\n”, newData);
head = insertAtBeginning(head, newData);

printf(“Linked list after insertion: “);
displayList(head);

return 0;
}

Output:

Initial linked list: 10 -> 20 -> 30 -> 40 -> NULL
Inserting 90 at the beginning...
Linked list after insertion: 90 -> 10 -> 20 -> 30 -> 40 -> NULL

Main Function Explanation

  • The linked list is created with the values 10 -> 20 -> 30 -> 40. First, the head node is created with the value 10 using createNode(10). head->next->next->next, method link the each node.
  • Print the original linked list using printList(head). This will print theriginal Linked List: 10 20  30 40
  • The program prompts the user to enter a value to insert at the beginning of the list, The user inputs a value (let’s say 90).
  • The insertion at the beginning operation is performed by calling insertAtBeginning(head, data) where data is the value entered by the user.
  • Finally, the program prints the updated linked list after the insertion