How to implement a linked list in C?

Mastering Linked Lists in C: A Comprehensive Guide

Explore the fundamentals of linked lists in C, including their structure, common operations, and practical implementation examples. This guide covers singly linked lists, from creation to deletion.

Linked lists are fundamental data structures in computer science, offering a dynamic alternative to arrays for storing collections of data. Unlike arrays, which store elements in contiguous memory locations, linked lists store elements (nodes) at arbitrary locations, connecting them through pointers. This flexibility makes them highly efficient for operations like insertion and deletion, especially when the size of the collection changes frequently. This article will guide you through the process of implementing a singly linked list in C, covering its basic structure and essential operations.

Understanding the Linked List Structure

At its core, a linked list is composed of individual units called nodes. Each node typically contains two main parts: the data it holds and a pointer (or reference) to the next node in the sequence. The last node in the list points to NULL, signifying the end of the list. The entire list is accessed via a 'head' pointer, which points to the first node. If the head pointer is NULL, the list is empty.

graph TD
    A[Head] --> B(Node 1)
    B --> C(Node 2)
    C --> D(Node 3)
    D --> E[NULL]

    subgraph Node Structure
        B_data[Data] --> B_next[Next Pointer]
    end

    style A fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#ccc,stroke:#333,stroke-width:2px
    style B_data fill:#add8e6,stroke:#333,stroke-width:1px
    style B_next fill:#add8e6,stroke:#333,stroke-width:1px

Conceptual diagram of a singly linked list and its node structure.

typedef struct Node {
    int data;          // Data stored in the node
    struct Node *next; // Pointer to the next node
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        perror("Failed to allocate memory for new node");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Essential Linked List Operations

Implementing a linked list involves defining functions for common operations. These operations allow you to manipulate the list, such as adding new elements, removing existing ones, and traversing the list to access its contents. We'll focus on the most common operations for a singly linked list.

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

// Node structure (as defined previously)
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// Function to create a new node (as defined previously)
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        perror("Failed to allocate memory for new node");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 1. Insertion at the beginning
Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = createNode(data);
    newNode->next = head;
    return newNode; // New node becomes the new head
}

// 2. Insertion at the end
Node* insertAtEnd(Node* head, int data) {
    Node* newNode = createNode(data);
    if (head == NULL) {
        return newNode; // If list is empty, new node is the head
    }
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

// 3. Deletion of a node by value
Node* deleteNode(Node* head, int key) {
    Node *current = head, *prev = NULL;

    // If head node itself holds the key to be deleted
    if (current != NULL && current->data == key) {
        head = current->next; // Changed head
        free(current);       // Free old head
        return head;
    }

    // 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("\nNode with data %d not found.\n", key);
        return head;
    }

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

// 4. Traversal and printing
void printList(Node* head) {
    Node* current = head;
    printf("Linked List: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 5. Freeing the entire list
void freeList(Node* head) {
    Node* current = head;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    printf("List freed successfully.\n");
}

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

    head = insertAtBeginning(head, 10);
    head = insertAtBeginning(head, 20);
    head = insertAtEnd(head, 30);
    head = insertAtEnd(head, 40);
    printList(head); // Expected: 20 -> 10 -> 30 -> 40 -> NULL

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

    head = deleteNode(head, 20);
    printList(head); // Expected: 30 -> 40 -> NULL

    head = deleteNode(head, 50); // Node not found
    printList(head); // Expected: 30 -> 40 -> NULL

    freeList(head);
    head = NULL; // Important: Set head to NULL after freeing

    return 0;
}

Advantages and Disadvantages of Linked Lists

Linked lists offer distinct advantages over arrays, particularly in scenarios requiring frequent insertions or deletions. However, they also come with their own set of drawbacks.

Advantages:

• Dynamic Size: Linked lists can grow or shrink in size during runtime, as memory is allocated dynamically.
• Efficient Insertions/Deletions: Adding or removing elements is efficient (O(1) if the position is known, O(n) otherwise), as it only requires updating a few pointers, unlike arrays which may require shifting many elements.

Disadvantages:

• No Random Access: Accessing an element at a specific index (e.g., the 5th element) requires traversing the list from the beginning, resulting in O(n) time complexity. Arrays, in contrast, offer O(1) random access.
• More Memory Overhead: Each node requires extra memory to store the pointer to the next node, which can be significant for lists with many small data elements.
• Cache Performance: Due to non-contiguous memory allocation, linked lists can exhibit poorer cache performance compared to arrays.

1. Define the Node Structure

Start by defining a struct for your node, including the data field and a pointer to the next node. Use typedef for convenience.

2. Implement Node Creation

Write a function to dynamically allocate memory for a new node, initialize its data, and set its next pointer to NULL.

3. Develop Insertion Functions

Create functions for inserting nodes at the beginning and end of the list. Consider edge cases like an empty list.

4. Develop Deletion Functions

Implement functions to delete nodes, typically by value. Remember to handle cases where the head node is deleted or the node is not found.

5. Add Traversal and Utility Functions

Include a function to print the list's contents and, crucially, a function to free all allocated memory to prevent leaks.

6. Test Your Implementation

Write a main function to test all your linked list operations thoroughly, ensuring they work as expected for various scenarios.