Singly Linked List Data Structure in C: Full Implementation

Singly Linked List Data Structure in C: Full Implementation

This document provides a comprehensive implementation of a singly linked list in C, demonstrating fundamental operations such as appending nodes, inserting nodes at specific positions, deleting nodes, calculating list length, and displaying list contents. Understanding linked lists is crucial for mastering dynamic data structures in C programming.

Understanding the Node Structure

A singly linked list is composed of individual elements called nodes. Each node contains two primary parts: the data it holds and a link (or pointer) to the next node in the sequence. The root pointer always points to the first node of the list, or is NULL if the list is empty.

#include <stdio.h>
#include <stdlib.h> // Required for malloc and free
// #include <conio.h> // Non-standard header, often used for getch()

struct node
{
    int data;
    struct node* link;
};

struct node* root = NULL; // Global pointer to the first node of the list
int len; // Global variable to store list length (though length() calculates it)

// Function prototypes
void append(void);
void addatbegin(void); // Declared but not implemented in this example
void addatafter(void);
int length(void);
void display(void);
void delete_node(void); // Renamed to avoid conflict with C++ keyword
    

Main Program Execution and Menu

The main function serves as the entry point, presenting a menu-driven interface for users to interact with the linked list. It continuously prompts for user input until the exit option is chosen.

int main() // Changed to int main() for standard C
{
    int ch;
    while(1)
    {
        printf("--- Singly Linked List Operations ---\n");
        printf("1. Append a Node\n");
        printf("2. Add Node After a Specific Position\n");
        printf("3. Get List Length\n");
        printf("4. Display List Elements\n");
        printf("5. Delete a Node\n");
        printf("6. Exit Program\n");
        printf("Enter your choice: ");
        scanf("%d", &ch);

        switch(ch)
        {
            case 1: append();
                    break;
            case 2: addatafter();
                    break;
            case 3: len = length();
                    printf("Current list length: %d\n\n", len);
                    break;
            case 4: display();
                    break;
            case 5: delete_node(); // Call the renamed function
                    break;
            case 6: exit(0); // Use exit(0) for successful termination
            default: printf("Invalid choice. Please enter a number between 1 and 6.\n\n");
        }
    }
    return 0; // Standard practice for int main()
}
    

Core Linked List Operations

Appending a Node (append())

The append function adds a new node to the end of the singly linked list. It handles both cases: when the list is empty (the new node becomes the root) and when the list already contains nodes (it traverses to the last node and links the new node).

void append()
{
    struct node* temp;
    temp = (struct node*)malloc(sizeof(struct node)); // Allocate memory for the new node

    if (temp == NULL) { // Check for successful memory allocation
        printf("Memory allocation failed!\n");
        return;
    }

    printf("Enter node data: ");
    scanf("%d", &temp->data);
    temp->link = NULL; // New node's link should point to NULL as it's the last node

    if(root == NULL) // If the list is empty
    {
        root = temp;
    }
    else // If the list is not empty
    {
        struct node* p = root;
        while(p->link != NULL) // Traverse to the last node
        {
            p = p->link;
        }
        p->link = temp; // Link the new node to the end
    }
    printf("Node appended successfully.\n\n");
}
    

Calculating List Length (length())

The length function iterates through the entire linked list, counting each node to determine the total number of elements. This provides the current size of the list.

int length()
{
    int count = 0;
    struct node* temp = root; // Start from the root

    while(temp != NULL) // Traverse until the end of the list
    {
        count++;
        temp = temp->link;
    }
    return count;
}
    

Displaying List Elements (display())

The display function prints the data contained within each node of the linked list, starting from the root. It informs the user if the list is currently empty.

void display()
{
    struct node* temp = root;

    if(temp == NULL)
    {
        printf("List is empty.\n\n");
    }
    else
    {
        printf("List elements: ");
        while(temp != NULL)
        {
            printf("%d -> ", temp->data);
            temp = temp->link;
        }
        printf("NULL\n\n"); // Indicate the end of the list
    }
}
    

Adding a Node After a Specific Position (addatafter())

The addatafter function inserts a new node at a specified position within the list. It first validates the provided location against the current list length. If valid, it traverses to the node at the desired insertion point and then re-links the pointers to include the new node.

Note: The original code had a bug where temp was used before memory allocation. This has been corrected.

void addatafter(void)
{
    struct node* temp;
    int loc, current_len, i = 1;

    printf("Enter the location after which to add the node: ");
    scanf("%d", &loc);

    current_len = length();

    if(loc > current_len || loc <= 0) // Location must be within bounds and positive
    {
        printf("Invalid location. Currently the list has %d nodes.\n", current_len);
        printf("Please enter a location between 1 and %d.\n\n", current_len);
        return;
    }

    temp = (struct node*)malloc(sizeof(struct node)); // Allocate memory for the new node
    if (temp == NULL) { // Check for successful memory allocation
        printf("Memory allocation failed!\n");
        return;
    }

    printf("Enter node data: ");
    scanf("%d", &temp->data);
    temp->link = NULL; // Initialize link

    struct node* p = root;
    // Traverse to the node *at* 'loc' position
    while(i < loc) // Traverse to the node *at* the specified location
    {
        p = p->link;
        i++;
    }

    // Now 'p' points to the node *after* which we want to insert 'temp'
    temp->link = p->link; // New node points to what 'p' was pointing to
    p->link = temp;       // 'p' now points to the new node
    printf("Node added successfully after location %d.\n\n", loc);
}
    

Deleting a Node (delete_node())

The delete_node function removes a node from the list at a specified position. It handles three main scenarios: deleting the first node, deleting a node in the middle, and invalid location input. Memory occupied by the deleted node is freed using free() to prevent memory leaks.

Note: The original code had an infinite loop bug in the traversal for deletion. This has been corrected.

void delete_node(void) // Renamed to avoid conflict
{
    struct node* temp;
    int loc;

    printf("Enter location of the node to delete: ");
    scanf("%d", &loc);

    int current_len = length();

    if(loc > current_len || loc <= 0) // Location must be valid and positive
    {
        printf("Invalid location. Currently the list has %d nodes.\n\n", current_len);
        return;
    }
    else if(loc == 1) // Deleting the first node
    {
        temp = root;
        root = temp->link; // Root now points to the second node
        temp->link = NULL; // Disconnect the old root
        free(temp);        // Free memory of the old root
        printf("Node at location 1 deleted successfully.\n\n");
    }
    else // Deleting a node from the middle or end
    {
        struct node* p = root; // Pointer to the node *before* the one to be deleted
        struct node* q;        // Pointer to the node to be deleted
        int i = 1;

        while(i < loc - 1) // Traverse to the node *before* the target location
        {
            p = p->link;
            i++; // Increment i to move to the next node
        }
        q = p->link;        // 'q' is the node to be deleted
        p->link = q->link;  // 'p' bypasses 'q' and links to 'q's next node
        q->link = NULL;     // Disconnect 'q' from the list
        free(q);            // Free memory of 'q'
        printf("Node at location %d deleted successfully.\n\n", loc);
    }
}
    

Further Enhancements (Not Implemented in Original)

• Add at Beginning: Implement the addatbegin() function to insert a node at the start of the list.
• Search Node: Add a function to search for a specific data value within the list.
• Reverse List: Implement a function to reverse the order of nodes in the list.
• Error Handling: More robust error handling for malloc failures.
• User Experience: Clearer prompts and output messages.