C Program to Implement Singly Linked List

A Singly Linked List is a fundamental data structure in computer science, commonly used in C programming. It is a linear data structure in which each element, called a node, contains a data field and a pointer to the next node in the sequence. This article provides an overview of singly linked lists, their implementation in C, and their applications.

What is a Singly Linked List?

A Singly Linked List is a dynamic data structure consisting of nodes that are connected sequentially. Each node comprises two parts:

• Data: Stores the information.
• Pointer: Points to the next node in the list.

The last node in a singly linked list has a pointer set to

Key Operations on Singly Linked List

The main operations performed on a singly linked list include:

• Insertion: Adding a new node to the beginning, end, or a specific position in the list.
• Deletion: Removing a node from the list.
• Traversal: Visiting each node to access or process its data.

Structure of a Singly Linked List in C

In C programming, a singly linked list is implemented using structures. Here's how a node is defined:

struct Node {
    int data;
    struct Node* next;
};

Implementation of Singly Linked List in C

1. Creating a Node

The first step in implementing a singly linked list is to define a function that creates 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;
}

2. Insertion Operations

a) Inserting at the Beginning

void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

b) Inserting at the End

void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

3. Deletion Operations

a) Deleting a Node by Value

void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

4. Traversing the Linked List

Traversal is used to access each node of the linked list.

void traverseList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Example Program

Below is an example program demonstrating the implementation of a singly linked list in C:

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

void traverseList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);

    printf("Singly Linked List:\n");
    traverseList(head);
    return 0;
}

Advantages of Singly Linked List

• Dynamic memory allocation allows efficient use of memory.
• Efficient insertion and deletion operations compared to arrays.

FAQs

What is a singly linked list in C?

A singly linked list in C is a data structure where each node contains data and a pointer to the next node, forming a sequence.

What are the applications of singly linked lists?

Singly linked lists are used in dynamic memory allocation, implementation of stacks and queues, and handling hierarchical data structures like trees.

What are the advantages of a singly linked list?

The advantages include dynamic memory allocation, efficient insertion and deletion, and flexibility compared to arrays.

Can a singly linked list be circular?

Yes, a singly linked list can be circular, where the last node points back to the first node, forming a loop.

Conclusion

A singly linked list is an essential concept in data structures, providing a dynamic and efficient way to manage data in C programming. Understanding its implementation and operations is crucial for mastering advanced programming and problem-solving techniques.