Singly Linked List Program in C: A Comprehensive Guide

A singly linked list in C is a list of nodes connected together sequentially, where each node stores:

• A piece of data (integer, character, etc.).
• Each one gives a pointer to the next node.

The singly linked list starts from the first node, known as the head pointer. If the list is empty, the head is assigned NULL.

Singly linked lists offer flexibility and dynamic memory utilisation. Unlike arrays, their size is not fixed, and nodes can be added or removed without requiring memory reallocation or data shifting.

The working mechanism of a singly linked list revolves around creating nodes, linking them, and managing their connections dynamically. Here’s how it typically works:

1. Node Creation: Each node is created dynamically using memory allocation functions.
2. Sequential Linking: Nodes are linked together by assigning the next pointer of one node to the address of the next node.
3. Head Management: The head pointer maintains a reference to the first node, ensuring accessibility to the list.
4. Termination: The last node's pointer (next) is set to null, signaling that this is the end of the list.

Traversing a singly linked list thus first starts from the head pointer and follows the chain of the next pointers until the very end is reached.

The core strength of a singly linked list lies in its ability to handle dynamic data efficiently. The primary operations it supports are insertion, deletion, and traversal. Let’s discuss each in detail.

Insertion Operation in Singly Linked List

Insertion in the singly linked list is simply adding a new node in specific positions. There are three major types of insertions:

1. At the beginning
2. At the end
3. At a specific position

1. Insertion at the Beginning

This operation involves putting a new node in front of the current head. Then the new node thus becomes the first node, and the head pointer changes to point to it. This is a very efficient operation, as it requires a constant amount of time no matter what the length of the list might be.

Code Example:

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

// Define the Node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to insert a node at the beginning of the list
void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory for the new node
    newNode->data = newData;  // Assign data to the new node
    newNode->next = *head;    // Make the new node point to the current head
    *head = newNode;          // Update the head to the new node
}

// Function to print the linked list
void printList(struct Node* head) {
    while (head != NULL) {  // Traverse the list until the end
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");  // Indicate the end of the list
}
int main() {
    struct Node* head = NULL;  // Initialize the head pointer to NULL

    // Insert elements at the beginning of the list
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);

    // Print the linked list
    printList(head);

    return 0;

Output:

30 -> 20 -> 10 -> NULL
Process returned 0(0X0)  execution time : 2.749 s
press any key to continue

2. Insertion at the End

To add the node at the end, we can traverse the list until we reach the last node. The new node is attached to the last node's pointer with the address of the new node.

Code Example:

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

// Define the structure for a linked list node
struct node {
    int data;
    struct node* next;
};

// Function to add a node at the end of the linked list
void addLast(struct node** head, int val) {
    // Create a new node
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = val;
    newNode->next = NULL;

    // If the linked list is empty, the new node becomes the head
    if (*head == NULL) {
        *head = newNode;
    } else {
        // Otherwise, traverse to the last node
        struct node* lastNode = *head;
        while (lastNode->next != NULL) {
            lastNode = lastNode->next;
        }
        // Add the new node at the end
        lastNode->next = newNode;
    }
}
// Function to print the linked list
void printList(struct node* head) {
    struct node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);  // Print the data in the current node
        temp = temp->next;            // Move to the next node
    }
    printf("NULL\n");                  // Indicate the end of the list
}

int main() {
    struct node* head = NULL;  // Initialize the linked list as empty

    // Add elements to the linked list
    addLast(&head, 10);
    addLast(&head, 20);
    addLast(&head, 30);

    // Print the linked list
    printList(head);

    return 0;
}

Output

10 -> 20 -> 30 -> NULL
Process returned 0 (0X0)  execution time : 0.848 s
press any key to continue

3. Insertion at a Specific Position

This operation involves navigating to the desired position in the list and adjusting the pointers of the surrounding nodes to include the new node in the sequence.

Code Example:

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

// Node structure
struct Node {
    int data;
    struct Node* next;
};
// Function to create a new node
struct Node* createNode(int x) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

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

// Function to insert a node at a specific position
struct Node* insertPos(struct Node* head, int pos, int data) {
    if (pos < 1) {
        printf("Invalid position.\n");
        return head;
    }

    // If inserting at the head
    if (pos == 1) {
        struct Node* newNode = createNode(data);
        newNode->next = head;
        return newNode;
    }

    struct Node* curr = head;
    // Traverse to the node just before the desired position
    for (int i = 1; i < pos - 1 && curr != NULL; i++) {
        curr = curr->next;
    }

    // If position is greater than the number of nodes
    if (curr == NULL) {
        printf("Position is out of bounds.\n");
        return head;
    }

    struct Node* newNode = createNode(data);
    newNode->next = curr->next;
    curr->next = newNode;

    return head;
}
// Main function
int main() {
    // Creating the list
    struct Node* head = createNode(3);
    head->next = createNode(5);
    head->next->next = createNode(8);
    head->next->next->next = createNode(10);

    // Print original list
    printf("Original list:\n");
    printList(head);

    // Insert new node at position
    int data = 12, pos = 3;
    head = insertPos(head, pos, data);

    // Print list after insertion
    printf("\nList after insertion:\n");
    printList(head);

    // Cleanup remaining nodes
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Output

original list:
3 -> 5 -> 8 -> 10 -> NULL

List after insertion:
3 -> 5 -> 12 -> 8 -> 10 -> NULL

Deletion Operation in Singly Linked List

Deletion removes a node from the list while maintaining the structural integrity of the remaining nodes. Similar to insertion, deletion can occur:

1. At the beginning
2. At the end
3. At a specific position

Code Example for Deleting at the Beginning Operation:

To delete the first node, the head pointer must be updated so that it points to the second node. The memory allocated for the first node is then deallocated.

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

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

// Function to create a new node
struct Node* createNode(int new_data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->data = new_data;
    newNode->next = NULL;
    return newNode;
}

// Function to delete the head node and return the new head
struct Node* deleteHead(struct Node* head) {
    // Check if the list is empty
    if (head == NULL) {
        printf("The list is already empty.\n");
        return NULL;
    }

    // Store the current head in a temporary variable
    struct Node* temp = head;

    // Move the head pointer to the next node
    head = head->next;

    // Free the memory of the old head node
    free(temp);

    return head;
}

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

// Main function
int main() {
    // Create a hard-coded linked list
    struct Node* head = createNode(3);
    head->next = createNode(12);
    head->next->next = createNode(15);
    head->next->next->next = createNode(18);

    // Print the original list
    printf("Original list:\n");
    printList(head);

    // Delete the head node
    head = deleteHead(head);

    // Print the list after deleting the head
    printf("\nList after deleting the head:\n");
    printList(head);

    // Cleanup remaining nodes
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Output:

Original list:
3 -> 12 -> 15 -> 18 -> NULL

List after deleting the head:
12 -> 15 -> 18 -> NULL

Code Example for Deleting at End:

This entails traversing to the second-latest node and terminating at the last one connected by accessing the next pointer via NULL.

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

// Node structure for the linked list
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 remove the last node of the linked list
struct Node* removeLastNode(struct Node* head) {
    // If the list is empty, return NULL
    if (head == NULL) {
        printf("The list is empty.\n");
        return NULL;
    }

    // If the list has only one node, delete it and return NULL
    if (head->next == NULL) {
        free(head);
        return NULL;
    }

    // Find the second last node
    struct Node* secondLast = head;
    while (secondLast->next->next != NULL) {
        secondLast = secondLast->next;
    }

    // Delete the last node
    free(secondLast->next);

    // Change next of second last to NULL
    secondLast->next = NULL;

    return head;
}

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

// Driver code
int main() {
    // Creating a static linked list
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    // Print the original list
    printf("Original list:\n");
    printList(head);

    // Removing the last node
    head = removeLastNode(head);

    // Print the list after removing the last node
    printf("\nList after removing the last node:\n");
    printList(head);

    // Free remaining nodes to avoid memory leaks
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Output:

original list : 1 -> 2 -> 3 -> 4 -> 5 -> NULL
list after removing last node :  1 -> 2 -> 3 -> 4 -> NULL

process returned 0(0X0)  exxecution time : 9.561 s
press any key to continue

Deleting a Node at a Specific Position

Here, the pointers of the surrounding nodes are adjusted to bypass the node to be deleted. The memory allocated for the node is subsequently freed.

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

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

// Function to delete a node at a given position
struct Node* deleteNode(struct Node* head, int position) {
    if (head == NULL) {
        printf("The list is empty.\n");
        return head;
    }

    struct Node* temp = head;

    // Case 1: If the head is to be deleted
    if (position == 1) {
        head = head->next;
        free(temp);
        return head;
    }

    // Traverse to the node just before the one to delete
    struct Node* prev = NULL;
    for (int i = 1; i < position && temp != NULL; i++) {
        prev = temp;
        temp = temp->next;
    }

    // If position is out of bounds
    if (temp == NULL) {
        printf("Position %d is out of bounds.\n", position);
        return head;
    }

    // Unlink the node to delete and free it
    prev->next = temp->next;
    free(temp);

    return head;
}

// Function to print the linked list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}
int main() {
    // Create a linked list: 2 -> 3 -> 4 -> 5 -> NULL
    struct Node* head = newNode(2);
    head->next = newNode(3);
    head->next->next = newNode(4);
    head->next->next->next = newNode(5);

    printf("Original list: ");
    printList(head);

    // Delete the node at position 2
    int position = 2;
    head = deleteNode(head, position);

    printf("List after deletion: ");
    printList(head);

    // Cleanup remaining nodes
    while (head != NULL) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Output:

original list : 2 -> 3 -> 4 -> 5 -> NULL
list after deletion : 2 -> 4 -> 5 -> NULL

Traversal Operation in Singly Linked List

Traversal refers to visiting each node in the list sequentially to perform operations like displaying, processing, or searching for data. Starting from the head pointer, the traversal follows the chain of the next pointers until it reaches the end (NULL).

Traversal is particularly useful for debugging and understanding the current structure of the list.

Code Example:

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

// Define the structure for a linked list node
struct Node {
    int data;
    struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
    // Allocate memory for a new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;  // Set the data
    newNode->next = NULL;  // Initialize the next pointer to NULL
    return newNode;
}

// Function to traverse and print the linked list
void traverseList(struct Node* head) {
    // Loop through the list until head becomes NULL
    while (head != NULL) {
        printf("%d -> ", head->data);  // Print the data of the current node
        head = head->next;            // Move to the next node
    }
    printf("NULL\n");                  // Indicate the end of the list
}

int main() {
    // Create a hard-coded linked list with values 10, 20, 30, 40
    struct Node* head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);
    head->next->next->next = createNode(40);

    // Traverse and print the linked list
    traverseList(head);
    // Free the allocated memory for nodes (optional but recommended)
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Output:

10 20 30 40
 process returned 0(0X0)  execution time : 0.390 s
 Press any key to continue

Singly linked lists have numerous applications in real-world programming and system design due to their dynamic nature and efficient handling of data. Some common applications include:

1. Dynamic Memory Management: Singly linked lists are ideal for scenarios where memory requirements are unpredictable. Their ability to dynamically allocate and deallocate memory helps in optimising system performance.
2. Implementation of Stacks and Queues: Stacks and Queues, as the most fundamental data structures, are usually implemented as singly linked lists. For stacks, nodes are added or deleted from one end, while for queues, the processes are in FIFO order.
3. Graph Representation: In graph theory, singly linked lists are the representations of adjacency lists, an important part also to search algorithms like BFS and DFS.
4. Polynomial Representation: Polynomial expressions, where each term has a coefficient and an exponent, are efficiently stored and manipulated using linked lists.
5. Sparse Matrix Representation: Singly linked lists store non-zero elements of a sparse matrix, saving memory by avoiding the storage of unnecessary zero values.‍
6. Database Management Systems: In databases, singly linked lists are used to manage dynamic collections of data, such as tables or records, which can grow or shrink as needed.

Mastering the singly linked list program in C provides a strong foundation in data structures and algorithms. Dynamic memory management is one of the plus points that he/she can derive from the application of singly linked lists. Matrix operations, including insertion, deletion, and traversal, as well as even more advanced therapeutic concepts like recursion and graph, can be successfully carried out by ANY programmer with the aid of singly linked lists.

1. What is a singly linked list in data structure?

A singly linked list is a dynamic data structure of nodes, each consisting of data and a pointer to the next node.

2. How do you implement a strongly linked in C?

By using structures to define nodes, dynamically allocating memory for new nodes, and connecting them using pointers.

3. What are the key operations in a singly linked list?

The key operations include insertion, deletion, and traversal of nodes in the list.

4. Why use linked lists over arrays?

Linked lists provide dynamic memory allocation; insertion/deletion time is constant, while arrays are static in nature.

5. Where is the real-world usage of linked lists?

Linked lists are used in dynamic data handling, implementing stacks and queues, and representing graph structures like adjacency lists.