Singly Linked List Program in C: A Comprehensive Guide

The real power of a singly linked list is its ability to effectively manage dynamic data. The main functions that singly linked lists support are insertion, deletion, and traversal. Let's go through each of those one at a time.

Insertion Operation in Singly Linked List Program in C

Insertion into the singly linked list is just the act of adding a new node at a specific location. There are three categories of insertions that we can talk about:

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

Insertion follows the same principle as before: we must first find the target position in the list and then update the pointers to include the new node in the linked 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 is removing a node from the list in such a way that the overall structure of the nodes that remain in the list is preserved. As with 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

The surrounding nodes' pointers are adjusted to skip the deleted node, and the pointer to the node is freed for use elsewhere.

#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 Program in C

Traversal is the act of going to each node in the list sequentially to accomplish some task, like displaying, processing data or searching for data. Traversal starts with the pointer to the head of the list and follows the chain of next pointers until it encounters the end of the list or 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

Summary

A singly linked list supports four basic operations: insertion, deletion, searching, and traversing.

• Insertion allows the user to insert a new node to the head of the list or to the end of the list, or to some particular location in the list.
• Deletion provides the user a fast way to delete a node stored in the list from any location in the list, since deleting the node being stored at the head of the list would be the most efficient in this regard.
• Searching for a node in the list involves finding its value.
• Traversal is simply going through each node in the list sequentially, beginning with the head of the list.

These operations are all that are necessary to make a singly linked list a flexible, efficient, dynamic structure to manage your data.

Analyzing the computational complexity of singly linked list operations helps you understand their efficiency and suitability for different tasks. Here’s a breakdown of the most common operations:

Time Complexity

• O(1): Operations like insertion or deletion at the head are constant time, regardless of list size.
• O(n): Operations involving traversal (insert at end, search, delete at end/position) require scanning up to n nodes.

Average Comparisons:

In a single linked list, locating a position or an element often requires (n+1)/2 comparisons, where n is the total amount of nodes.

Space Complexity

• O(n):

Each node stores the data and a pointer to the next node, so the space required grows linearly with the number of elements.

Each node stores:

• The data
• A pointer to the next node

Accordingly, memory increases linearly with the list size.

Note:

Anything that steps on or requires traversal beyond the head of a singly linked list is O(n) that speeds up for reading/adding at the head and for determining the number of nodes (counting: remembering the number of nodes) but does slow down for everything else.  An example of an exception would be obtaining the tail (end) in O(n) too, but it is listed in the next context below.

Every programming language has construct(s) for singly linked lists, simple expansions of arrays, or it can simply be a memory management approach that holds this kind of structure to keep track of either memory blocks of free and allocated or memory blocks of changes, which is often required in sorting or rapid-processing tasks.  Below are some situations where a singly linked list might be useful, in the instance of simply dynamic or free memory allocation:

1. Dynamic Memory Management

Again, singly linked lists best serve situations where the data length is not known beforehand and can potentially change. They can be very useful in memory allocations and systems model garbage collections, like linked lists that simply hold free and allocated memory references. 

2. Implementation of Stacks

Stacks, or the last-in-first-out (LIFO) approach to retrieving data, can be easily implemented using singly linked lists, as each push or pop can be performed instantly by allocating items to or accessing the head, for O(1) retrieval.  

3. Implementation of Queues

Queues, or first-in-first-out (FIFO), can also often use singly linked lists to hold their data, while enqueue adds nodes to the end, and dequeue removes a node from the front without moving other items. 

4. Graph Representations (Adjacency Lists)

In graph algorithms, singly linked lists are a data structure to hold the adjacency lists. Linking adjacent vertices into a list for each vertex is a memory-efficient and easy-to-update data structure. 

5. Undo Functionality in Applications

Many text editors or applications implement undo and redo functionality using singly linked lists. Each action or state is stored as a node, and the application traverses the list to return to that previous state.

Additional Examples:

• Hash Table Collision Handling:
  Singly linked lists are also used in hash tables to represent the list of links for buckets to handle collisions via chaining. Each bucket in a hash table structure has a linked list of elements that share an index.
• Polynomial and Sparse Matrix Representation:
  Singly linked lists can be used to efficiently represent polynomials and sparse matrices by holding only the non-zero terms or elements.
• Task Scheduling and Buffer Management:
  Singly linked lists are appropriate for managing task queues or buffers that can grow or shrink, alternating between read and write operations in operating systems, as well as applications making network requests.

Bottom Line: The above examples demonstrate how singly linked lists provide flexibility, efficiency and dynamic memory allocation and are valuable data structure options for many real-world programming or system design scenarios.

Singly linked lists are a basic data structure in C, and have some advantages and disadvantages with respect to arrays, doubly linked lists, and circular linked lists. You may choose the best data format for your application by being aware of these benefits and drawbacks.

Advantages

1. Dynamic Sizing
   Singly linked lists can grow or shrink in memory at runtime, which is a great advantage when working with a number of elements that is not known beforehand or is not fixed.
2. Efficient Insertion and Deletion Operations
   Adding or removing a node from the front (head) of the list is "fast" (O(1)), because only a few pointers need to be updated in memory. A linked list does not need to shift everything, whereas an array does.
3. Better Memory Efficiency for Dynamic Data
   Since nodes are allocated only as needed, there’s no memory wastage due to unused elements or the need for contiguous memory locations, which arrays require.
4. No Need for Contiguous Memory Locations
   Each node can be stored in memory wherever space is available, therefore, singly linked lists are less prone to memory allocation problems that can come with large arrays.
5. Simple Implementation in C
   Since the structure can be expressed using (struct), singly linked lists are very easy to implement and extend, which is why they are a common example to illustrate computer science problems and due to their simplicity, a common use for data structures to use when implementing stacks, queues, adjacency lists in graphs, etc.

Disadvantages

1. No Random Access
   If you want to access a node at some position in the list, you must iterate through the list starting from the head, which is an O(n) to find the item. An array will allow you to access any element in O(1).
2. Extra Memory Overhead
   Every node needs extra space for the next pointer, which can be significant if the node data is small.
3. Forward Traversal Only
   In contrast to doubly linked lists or circular linked lists, singly linked lists can only be traversed from head to tail, thus limiting some operations.
4. More Complex Insertion/Deletion at Arbitrary Positions
   Compared to similar operations in arrays, inserting or deleting a node at a specified location requires traversing the list to that point, which is less efficient.
5. Pointer Management Complexity
   A pointer not updated correctly can leave you with a memory leak or a broken list. Managing your pointer is very important, especially when deleting or inserting a node.

In summary:
A singly linked list in C gives you dynamic memory management and a flexible approach to performing insertions/deletions more efficiently than in arrays. For applications with unpredictable data sizes, given the flexibility of applying deletion/insertion will be more advantageous. It becomes a less desirable data structure in applications where speed of random access operations is desired, or even traversing the linked list in both directions. Knowing the tradeoffs between a singly linked list and any other data structure will help you better meet your programming needs.

1. Always Initialize Pointers
   Before using your data structure, be sure to set all the pointers (head especially) to NULL before use to avoid any undefined behavior.
2. Check for NULL Before Operations
   In the case of insertion, deletion, or traversal, before performing any of those actions, ensure that the pointers are equal NULL to prevent any segmentation fault.
3. Free Memory After Deletion
   To avoid memory leaks, always use the free method to release the memory allotted to the destroyed node or nodes.
4. Handle Edge Cases
   Be cautious when managing special cases, such as empty lists, lists with one node, or invalid positions, to maintain program functionality.
5. Update Pointers Properly
   After each insertion or deletion, ensure that pointers to the head and/or next are updated appropriately to preserve the integrity of the list.
6. Use Helper Functions
   While maintaining a small size and code readability, write separate, reusable functions for vital logic such as create, insert, delete, and print functionality.
7. Avoid Unnecessary Traversal
   Whenever possible, when traversing is not required, minimize traversing the linked list by maintaining additional pointers (like tail) if the list requires frequent access to the end of the list.
8. Document Your Code
   Add comments detailing your logic, especially when navigating pointers since that will be the key component to maintain.
9. Test with Different Scenarios
   Test your implementation with the empty list, one-node list, and handle boundary case testing (typically the last element) to identify bugs if they exist.
10. Consistent Naming Conventions
    Use clear and meaningful names for structures, functions, and variables for greater clarity and product maintainability.

Having a working singly linked list program in C is paramount for any novice programmer in data structures, as it will enhance the understanding of pointers, dynamic memory, and how nodes are connected together. These concepts and logic will be the backbone of any advanced academic programming concepts.

Key Points to Remember

• A singly-linked list allows for dynamic memory allocation. As such, it gives flexibility for data of any size to be stored in a list.
• Insertions and deletions can be done very efficiently at the head of the list (O(1)), but elements at positions in the list will not be accessed until traversed (O(n)).
• Also, be careful navigating pointers when deleting nodes, so memory leaks and dangling references are avoided.
• Singly linked lists are ideal for cases requiring insertion and deletion; not ideal when random access to nodes is needed in real time.
• It is important to free memory correctly in order to be able to write a good and efficient C program as this can cause memory leaks, or an unstable program.

Practical Advice for Learners 

• Practice developing your own singly linked list program from the ground up in C
• Focus on implementing insertion, deletion, traversal, and search operations.
• Try converting it into a menu-driven linked list program to deepen understanding.

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

A singly linked list data structure that is dynamic; each node consists 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?

Dynamic memory allocations are performed with linked lists; insertion/deletion time is constant, whereas arrays are static.

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

Linked lists are used for handling various dynamic data, such as stacks or queues, where certain graph structures, such as adjacency lists, are represented.