Inserting into the Singly Linked List: A C Program Exploration

Singly linked lists offer dynamic data structures, allowing you to add new elements at any point. This program demonstrates how to declare and insert elements into a singly linked list in C, making it a valuable tool for managing and manipulating data.

Imagine a train with carriages representing nodes in a linked list. You want to add a new passenger (data) to the train, but you need to decide where to insert them—at the beginning, end, or somewhere in the middle. This program explores different insertion scenarios within a C implementation of a singly linked list.

C Program for Declaring and Inserting into a Singly Linked List:

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

// Structure to represent a node in the linked list
typedef struct node {
  int data;
  struct node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}

// Function to declare (initialize) an empty linked list
Node* declareList() {
  return NULL; // An empty list is represented by a NULL head pointer
}

// Function to insert a node at the beginning of the linked list
Node* insertAtBeginning(Node* head, int data) {
  Node* newNode = createNode(data);
  newNode->next = head; // New node points to the old head
  return newNode; // New node becomes the new head
}

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

  if (head == NULL) { // Empty list, new node becomes the head
    return newNode;
  }

  Node* current = head;
  while (current->next != NULL) { // Traverse to the last node
    current = current->next;
  }
  current->next = newNode; // Last node points to the new node
  return head; // Head remains unchanged
}

// Function to insert a node after a specific node in the linked list
Node* insertAfter(Node* head, int target, int data) {
  if (head == NULL) { // Empty list, cannot insert
    return NULL;
  }

  Node* current = head;
  while (current != NULL && current->data != target) { // Find the target node
    current = current->next;
  }

  if (current == NULL) { // Target not found, cannot insert
    return head;
  }

  Node* newNode = createNode(data);
  newNode->next = current->next; // New node points to what was after the target
  current->next = newNode; // Target node points to the new node
  return head; // Head remains unchanged
}

int main() {
  // Declare an empty list
  Node* head = declareList();

  // Insert some nodes
  head = insertAtEnd(head, 10);
  head = insertAtBeginning(head, 20);
  head = insertAfter(head, 10, 30);

  printf("List after insertions:\n");
  Node* current = head;
  while (current != NULL) {
    printf("%d ", current->data);
    current = current->next;
  }
  printf("\n");

  return 0;
}

Explanation:

1. Node structure: Defines the basic building block of the list, containing data and a pointer to the next node.

2. createNode function: Allocates memory for a new node, initializes it with data and a NULL next pointer, and returns the new node.

3. declareList function: Initializes the head pointer of the list to NULL, signifying an empty list.

4. insertAtBeginning, insertAtEnd, and insertAfter functions:

• Take the head pointer and additional arguments (data for new node, target node for insertion after) as input.

• Create a new node with the given data.

• Depending on the function:

• insertAtBeginning: Makes the new node point to the current head and updates the head pointer to the new node.

• insertAtEnd: Traverses to the last node and makes it point to the new node.

• insertAfter: Finds the target node and makes the new node point to