C Program to Implement Singly Linked List

What is a Singly Linked List in C?

Singly linked lists are one of the fundamental data structures in computer programming. Understanding how to implement a singly linked list in C is essential for beginners and intermediate learners alike. In this article, we will explore the concept of linked lists, their advantages, common operations, practical code examples, and real-world use cases.

A singly linked list is a linear data structure where each element, called a node, contains data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory locations, which makes them more flexible for dynamic data management.

Structure of a Node

Each node in a singly linked list contains two parts:

• Data: The actual value or information stored.
• Pointer: A reference to the next node in the list.

Node Representation in C

📄

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

Advantages of Using Singly Linked List

• Dynamic memory allocation – size can grow or shrink at runtime.
• Efficient insertion and deletion – no need to shift elements as in arrays.
• Flexible memory utilization – no wastage of memory.

 Operations on Singly Linked List in C

Here are the basic operations performed on a linked list in C programming:

• Creating a linked list
• Inserting a node (at beginning, end, or specific position)
• Deleting a node (by value or position)
• Traversing or displaying the list
• Searching for a node

1. Creating and Traversing a Singly Linked List

📄

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

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

void display(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;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // Allocate nodes
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    // Assign data
    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = NULL;

    // Display list
    display(head);

    return 0;
}

Explanation: We created a linked list with three nodes and displayed it using a traversal function. Each node points to the next node, and the last node points to

2. Inserting a Node in a Singly Linked List

📄

// Insert at beginning
struct Node* insertAtBeginning(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = head;
    head = newNode;
    return head;
}

// Insert at end
struct Node* insertAtEnd(struct Node* head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        return newNode;
    }

    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    return head;
}

3. Deleting a Node from a Singly Linked List

📄

struct Node* 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 head;
    }

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

    if (temp == NULL) return head;

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

 Singly Linked List

Singly linked lists are widely used in scenarios where dynamic memory allocation and flexible data insertion/deletion are required:

• Implementing stacks and queues
• Managing playlists in music or video applications
• Undo functionality in text editors
• Navigation systems with dynamic route adjustments
• Graph adjacency lists for memory-efficient graph representation

Comparison Table: Array vs Singly Linked List

C Program to Create a Singly Linked List

This example demonstrates how to create a simple singly linked list in C. We will create three nodes and link them together. This is a fundamental step for understanding more advanced linked list operations like insertion, deletion, and traversal.

Structure of a Node

Each node contains two parts: data and a pointer to the next node.

📄

struct Node {
    int data;          // Store data
    struct Node* next; // Pointer to the next node
};

Complete C Program to Create a Linked List

📄

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

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

int main() {
    // Create nodes
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // Allocate memory
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    // Assign data and link nodes
    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = NULL;

    // Display linked list
    struct Node* temp = head;
    printf("Linked list: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    return 0;
}

Explanation

• We first define a struct Node with data and a pointer.
• We dynamically allocate memory for three nodes using malloc.
• We assign values to the data part of each node.
• We link each node using the next pointer, forming the linked list.
• The last node points to NULL indicating the end of the list.

Output

When you run this program, the output will be:

📄

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

Key Points

• Linked lists are dynamic; you can add or remove nodes at runtime.
• Each node contains a pointer to the next node.
• The last node always points to NULL.
• This simple example can be extended to include insertion, deletion, and searching operations.

Implementing a singly linked list in C is a fundamental skill for programmers. Linked lists provide dynamic memory management, efficient insertion/deletion, and are versatile in real-world applications. By understanding nodes, traversal, insertion, and deletion operations, beginners and intermediate learners can build a strong foundation for advanced data structures.

FAQs 

1. What is the difference between singly and doubly linked list?

A singly linked list has nodes pointing only to the next node, while a doubly linked list has nodes pointing to both previous and next nodes, making traversal in both directions possible.

2. Can we implement a singly linked list without using pointers in C?

No. Pointers are essential in C for linking nodes dynamically, as they provide the ability to point to memory locations of subsequent nodes.

3. How do we traverse a linked list?

Traversal involves starting at the head node and iterating through each node using the next pointer until NULL is reached, processing each node’s data along the way.

4. What are the advantages of a linked list over an array?

Linked lists are dynamic in size, allow efficient insertion/deletion without shifting elements, and utilize memory more flexibly compared to arrays.

5. Can a singly linked list contain duplicate values?

Yes. Singly linked lists can store duplicate values since each node is independent, and there is no restriction on data uniqueness.