Implementing a Simple Singly Linked List in C

Introduction

Data structures are essential for organizing and managing data efficiently. One of the fundamental data structures is the linked list, which provides a flexible way of storing elements in a linear order. In this blog post, we will explore the implementation of a simple singly linked list in the C programming language. We will walk through the code step by step and explain each function to understand how the linked list works.

Defining the Node Structure

A linked list is a collection of nodes, where each node holds data and a reference to the next node in the list. In our C implementation, we start by defining the structure for each node using a struct:

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

The Node structure has two members: data, which holds the value of the node, and next, a pointer to the next node in the list.

Creating a New Node

To create a new node, we write a function createNode that takes the data as input and returns a pointer to the newly allocated node. This function uses malloc to dynamically allocate memory for the node:

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

The function first allocates memory for a new node using malloc and then sets its data to the provided value. Since this node is not yet linked to any other node, we set the next pointer to NULL.

Inserting a Node

The next step is to insert nodes into the linked list. We provide two insertion functions: insertAtBeginning and insertAtEnd. The first function inserts a node at the beginning of the list, and the second function inserts a node at the end of the list.

void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

The insertAtBeginning function inserts a new node at the start of the list. It creates a new node using createNode and points its next to the current head. Then, it updates the head to point to the new node.

On the other hand, the insertAtEnd function inserts a new node at the end of the list. If the list is empty (head is NULL), it simply sets the head to the new node. Otherwise, it traverses the list until it reaches the last node, then appends the new node to the next of the last node.

Deleting a Node

We also need to be able to delete nodes from the list. The deleteNode function takes the head of the list and a key value to be deleted:

void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Key not found in the linked list.\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
}

The deleteNode function first checks if the head node matches the key. If it does, it updates the head to the next node and frees the memory occupied by the original head node.

If the head node does not match the key, the function traverses the list using temp and prev pointers to find the node to be deleted. Once the node with the given key is found, the function updates the next pointer of the previous node to bypass the node to be deleted and then frees the memory.

Printing and Freeing the Linked List

Finally, we provide two utility functions: printLinkedList to display the elements of the linked list and freeLinkedList to release the allocated memory:

void printLinkedList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void freeLinkedList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

The printLinkedList function traverses the list and prints the data of each node in sequence until it reaches the end (marked by NULL).

The freeLinkedList function is used to release the allocated memory for all nodes in the list. It iterates through the list, freeing each node one by one.

The Main Function

int main() {
    Node* head = NULL;

    insertAtFront(&head, 10);
    insertAtFront(&head, 20);
    insertAtFront(&head, 30);

    printf("Linked list elements: ");
    printList(head); // Output: Linked list elements: 30 20 10

    freeList(head);

    return 0;
}

In this main function, we create a simple linked list with three elements (30, 20, and 10) using the insertAtFront function. Then, we print the elements of the linked list using the printList function and free the memory allocated for the list using the freeList function to prevent memory leaks before the program terminates.

Conclusion

In this blog post, we explored the implementation of a simple singly linked list in C. We learned how to create a new node, insert nodes at the beginning and end of the list, delete nodes based on a given key, and print and free the linked list. Understanding linked lists and their basic operations is crucial for building more complex data structures and algorithms.

This is the first data structure implementation in the C Magic series. But if you wanna know more about linked lists check out my in-depth blog post Unleashing the Potential of Linked Lists from the Data Structures series.

Feel free to hit me up on Twitter as well.

Happy coding!