Working with Linked Lists in C

In the vast landscape of data structures, linked lists stand out as a fundamental and versatile tool for organizing data. Unlike arrays, which have a fixed size and contiguous memory allocation, linked lists offer dynamic memory management and efficient insertion/deletion operations. This makes them incredibly useful for scenarios where the number of elements is unknown or frequently changes.

This entry in our C-Language Series will dive deep into understanding, implementing, and manipulating linked lists in C, focusing primarily on the singly linked list due to its foundational importance.

What is a Linked List?

At its core, a linked list is a linear collection of data elements, called nodes, where each node points to the next node in the sequence. It's a chain-like structure rather than a continuous block of memory.

• Node: The basic building block of a linked list. Each node typically contains:
  • Data: The actual information or value stored in the node.
  • Pointer (or Link): A reference (memory address) to the next node in the sequence. The last node's pointer usually points to NULL, signifying the end of the list.
• Head: A pointer to the very first node in the linked list. If the list is empty, the head pointer will be NULL.

Types of Linked Lists

While the concept of nodes and pointers remains central, linked lists come in various forms:

• Singly Linked List: Each node points only to the next node in the sequence. Traversal is unidirectional.
• Doubly Linked List: Each node has two pointers: one to the next node and one to the previous node. This allows for bidirectional traversal.
• Circular Linked List: The last node's pointer points back to the first node, forming a circle. This can be singly or doubly linked.

For the remainder of this post, we will concentrate on the singly linked list to build a strong foundation.

Implementing a Singly Linked List in C

1. Defining the Node Structure

In C, we use a struct to define the node. It will contain our data (let's use an int for simplicity) and a pointer to another node of the same type.

#include <stdio.h>
#include <stdlib.h> // For malloc and free

// Define the structure for a node
struct Node {
    int data;          // Data part of the node
    struct Node* next; // Pointer to the next node
};
    

2. Creating a New Node

A function to allocate memory for a new node, initialize its data, and set its next pointer to NULL is very useful.

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

3. Traversing and Printing the List

To see the contents of our linked list, we need to traverse it from the head to the end, printing each node's data.

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

4. Insertion Operations

4.1. Insert at the Beginning (Prepending)

This is a common operation where a new node is added as the first element of the list. The new node's next pointer points to the old head, and then the head pointer is updated to the new node.

// Function to insert a new node at the beginning of the list
struct Node* insertAtBeginning(struct Node* head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = head; // New node points to the old head
    return newNode;        // New node becomes the new head
}
    

4.2. Insert at the End (Appending)

To add a node at the end, we first traverse the list to find the last node (the one whose next pointer is NULL), and then make it point to the new node.

// Function to insert a new node at the end of the list
struct Node* insertAtEnd(struct Node* head, int data) {
    struct Node* newNode = createNode(data);
    if (head == NULL) {
        return newNode; // If list is empty, new node is the head
    }
    struct Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode; // Last node points to the new node
    return head;
}
    

4.3. Insert After a Specific Node

This operation involves finding a node with a specific value and then inserting the new node immediately after it.

// Function to insert a new node after a specific node (by value)
struct Node* insertAfter(struct Node* head, int prevData, int newData) {
    struct Node* current = head;
    while (current != NULL && current->data != prevData) {
        current = current->next;
    }

    if (current == NULL) {
        printf("Node with data %d not found.\n", prevData);
        return head; // Node not found, return original head
    }

    // Found the previous node, insert newNode after it
    struct Node* newNode = createNode(newData);
    newNode->next = current->next;
    current->next = newNode;
    return head;
}
    

5. Deletion Operations

5.1. Delete from the Beginning

Removing the head node is straightforward: update the head to point to the second node, and then free the memory of the original head.

// Function to delete the first node
struct Node* deleteFromBeginning(struct Node* head) {
    if (head == NULL) {
        printf("List is empty, nothing to delete.\n");
        return NULL;
    }
    struct Node* temp = head; // Store old head
    head = head->next;        // New head is the next node
    free(temp);               // Free memory of old head
    return head;
}
    

5.2. Delete a Specific Node by Value

This requires finding the node to be deleted and its preceding node. Once found, the preceding node's next pointer is updated to bypass the deleted node, and the deleted node's memory is freed.

// Function to delete a node by its data value
struct Node* deleteNode(struct Node* head, int key) {
    struct Node *current = head, *prev = NULL;

    // Case 1: Head node itself holds the key
    if (current != NULL && current->data == key) {
        head = current->next; // Change head
        free(current);        // Free old head
        return head;
    }

    // Case 2: Search for the key to be deleted, keep track of the previous node
    while (current != NULL && current->data != key) {
        prev = current;
        current = current->next;
    }

    // If key was not present in linked list
    if (current == NULL) {
        printf("Node with data %d not found for deletion.\n", key);
        return head;
    }

    // Unlink the node from the linked list
    prev->next = current->next;
    free(current); // Free memory
    return head;
}
    

6. Searching for an Element

To find if a particular value exists in the list, we traverse from the head until we find the value or reach the end of the list.

// Function to search for an element in the linked list
int searchList(struct Node* head, int key) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return 1; // Found
        }
        current = current->next;
    }
    return 0; // Not found
}
    

Putting It All Together: A Complete Example

Let's integrate these functions into a main function to demonstrate their usage.

int main() {
    struct Node* head = NULL; // Initialize an empty linked list

    printf("--- Insertion Operations ---\n");
    head = insertAtBeginning(head, 10); // List: 10 -> NULL
    head = insertAtBeginning(head, 20); // List: 20 -> 10 -> NULL
    head = insertAtEnd(head, 30);       // List: 20 -> 10 -> 30 -> NULL
    head = insertAtEnd(head, 40);       // List: 20 -> 10 -> 30 -> 40 -> NULL
    printList(head); // Expected: Linked List: 20 -> 10 -> 30 -> 40 -> NULL

    head = insertAfter(head, 10, 25); // List: 20 -> 10 -> 25 -> 30 -> 40 -> NULL
    printList(head); // Expected: Linked List: 20 -> 10 -> 25 -> 30 -> 40 -> NULL

    printf("\n--- Search Operation ---\n");
    if (searchList(head, 25)) {
        printf("25 found in the list.\n");
    } else {
        printf("25 not found in the list.\n");
    }
    if (searchList(head, 99)) {
        printf("99 found in the list.\n");
    } else {
        printf("99 not found in the list.\n");
    }

    printf("\n--- Deletion Operations ---\n");
    head = deleteFromBeginning(head); // List: 10 -> 25 -> 30 -> 40 -> NULL
    printList(head); // Expected: Linked List: 10 -> 25 -> 30 -> 40 -> NULL

    head = deleteNode(head, 30); // List: 10 -> 25 -> 40 -> NULL
    printList(head); // Expected: Linked List: 10 -> 25 -> 40 -> NULL

    head = deleteNode(head, 10); // List: 25 -> 40 -> NULL
    printList(head); // Expected: Linked List: 25 -> 40 -> NULL

    head = deleteNode(head, 40); // List: 25 -> NULL
    printList(head); // Expected: Linked List: 25 -> NULL

    head = deleteNode(head, 25); // List: NULL
    printList(head); // Expected: Linked List: NULL

    head = deleteFromBeginning(head); // Should print "List is empty..."
    printList(head); // Expected: Linked List: NULL

    // For comprehensive memory management, ensure all allocated nodes are freed.
    // A function to free the entire list would typically be used at the end:
    // void freeList(struct Node* head) {
    //     struct Node* current = head;
    //     struct Node* next;
    //     while (current != NULL) {
    //         next = current->next;
    //         free(current);
    //         current = next;
    //     }
    // }
    // freeList(head); // If head still points to nodes

    return 0;
}
    

Advantages of Linked Lists

• Dynamic Size: Linked lists can grow or shrink during runtime, as memory is allocated or deallocated as needed.
• Ease of Insertion/Deletion: Adding or removing elements is efficient (O(1) if the position is known, O(n) otherwise), as it only involves changing a few pointers, unlike arrays where shifting elements can be costly.
• Efficient Memory Utilization: Memory is allocated only for the elements actually in the list.

Disadvantages of Linked Lists

• No Random Access: To access an element at a specific index, you must traverse the list from the beginning (sequential access), which can be slow (O(n)). Arrays offer O(1) random access.
• Extra Memory Overhead: Each node requires additional memory to store the pointer(s) to the next (and previous) node(s).

When to Use Linked Lists?

Linked lists are ideal for scenarios where:

• The number of elements is unknown beforehand or changes frequently.
• Frequent insertions and deletions are required, especially at the beginning or end of the list.
• Memory usage needs to be flexible and dynamic.
• Sequential access is acceptable, and random access is not a primary requirement.

Common applications include implementing other data structures like stacks, queues, hash tables, and for managing dynamic memory.

Conclusion

Linked lists are a cornerstone of computer science education and practical programming. Understanding their mechanics, from node creation to complex insertion and deletion logic, is crucial for any C programmer. They empower you to build flexible and efficient data management solutions, laying the groundwork for more advanced data structures and algorithms. Keep practicing these concepts, as hands-on experience solidifies your understanding.