C Program to Implement Singly Linked List

1. Introduction

A singly linked list is a data structure that consists of nodes. Each node contains data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion and removal of elements from any position in the list.

2. Program Overview

In this program, we will:

1. Define the basic structure of a node in a singly linked list.

2. Implement functions to:

- Create a new node.

- Insert an element at the end of the list.

- Display the linked list.

- Delete a node from the linked list.

3. Code Program

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

// Define the node structure
struct Node {
    int data;           // Data part of the node
    struct Node* next;  // Pointer to the next node
};

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

// Function to insert an element at the end of the linked list
void insertEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {  // If the list is empty
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

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

// Function to delete a node from the linked list
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head, *prev;
    if (temp != NULL && temp->data == key) {  // If head node itself holds the key
        *head = temp->next;
        free(temp);
        return;
    }
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;  // Key was not found
    prev->next = temp->next;
    free(temp);
}

int main() {
    struct Node* head = NULL;
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    insertEnd(&head, 40);
    printf("Linked list:\n");
    displayList(head);
    printf("\nDeleting node 20:\n");
    deleteNode(&head, 20);
    displayList(head);
    return 0;
}

Output:

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

Deleting node 20:
10 -> 30 -> 40 -> NULL

4. Step By Step Explanation

1. We start by defining the structure of a node using the struct keyword. The Node has an integer data and a pointer to the next node.

2. The createNode function helps in creating a new node with the given data.

3. The insertEnd function is used to insert an element at the end of the linked list.

4. To display the linked list, we use the displayList function which iterates over each node and prints its data.

5. The deleteNode function is designed to delete a node from the list based on a given key.

6. In the main function, we perform various operations on the linked list to demonstrate its functionalities.