Published on

Working with Linked Lists in C Intermediate C Concepts Part 2

Authors

Welcome to the second part of our Intermediate C Concepts series! In the previous post, we explored Dynamic Memory Allocation in C, mastering malloc, calloc, realloc, and free. Now, we'll put that knowledge to practical use by diving into one of the most fundamental and versatile dynamic data structures: the Linked List. Get ready to see how pointers and dynamic memory allocation unlock flexible ways to organize data!

Table of Contents

What is a Linked List? Why Not Just Use Arrays?

Arrays are great for storing collections of similar data types. However, they have a significant limitation: their size is fixed at compile time (or when dynamically allocated, fixed until reallocated). If you need a collection that can easily grow or shrink during program execution, or if you need to insert/delete elements frequently in the middle, arrays become inefficient.

This is where Linked Lists shine. A linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element (called a Node) contains two parts:

  1. Data: The actual value stored in the node.
  2. Pointer (or Link): An address pointing to the next node in the sequence.

The last node in the list points to NULL, indicating the end of the list. The entry point to the list is typically a pointer called head, which points to the first node. If head is NULL, the list is empty.

Advantages over Arrays:

  • Dynamic Size: Linked lists can grow and shrink easily at runtime by adding or removing nodes.
  • Efficient Insertion/Deletion: Inserting or deleting elements doesn't require shifting subsequent elements (unlike arrays). You just need to update the pointers of the adjacent nodes.

Disadvantages:

  • No Random Access: You cannot directly access the i-th element like array[i]. You must traverse the list from the head node.
  • Extra Memory: Each node requires extra memory to store the next pointer.

For this tutorial, we will focus on the most common type: the Singly Linked List, where each node points only to the next node.

The Building Block: The Node Structure

Everything in a linked list revolves around the Node. We define it in C using a struct. Since the struct needs to contain a pointer to itself (to point to the next node of the same type), this is a classic example of a self-referential structure.

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

// Define the structure for a node in the linked list
struct Node {
    int data;             // The data stored in the node (can be any type)
    struct Node *next;    // Pointer to the next node in the list
};

// Typedef for convenience (optional but common)
typedef struct Node Node;

// Global head pointer (or pass it to functions)
// Initialized to NULL, indicating an empty list
Node *head = NULL;

Here:

  • data holds the value (we're using int for simplicity).
  • next is a pointer of type struct Node*, which will hold the memory address of the subsequent node.
  • The typedef allows us to simply write Node instead of struct Node.
  • head is a pointer that will always point to the first node of the list. It's crucial!

Core Operations on Singly Linked Lists

Let's implement the essential operations for managing a linked list.

1. Creating a New Node

We need a way to create a new node when we want to add data. This involves dynamically allocating memory for the node structure and initializing its fields. A helper function is good practice.

// Function to create a new node with given data
Node* createNode(int data) {
    // Allocate memory for the new node
    Node* newNode = (Node*)malloc(sizeof(Node));

    // Check if malloc was successful
    if (newNode == NULL) {
        fprintf(stderr, "Error: Memory allocation failed for new node!\n");
        // exit(1); // Or handle error appropriately
        return NULL; // Indicate failure
    }

    // Initialize the node's data and next pointer
    newNode->data = data;
    newNode->next = NULL; // The new node initially points to nothing

    return newNode; // Return the pointer to the newly created node
}
  • We use malloc to get space for one Node structure.
  • Crucially, we check if malloc returned NULL.
  • We assign the passed data to the node's data field.
  • newNode->next is set to NULL because when first created, it's not linked to anything yet.

2. Insertion

Nodes can be inserted at various positions. Let's look at the most common ones:

a) Inserting at the Beginning (Prepend)

This is the simplest and most efficient insertion method (O(1) time complexity).

// Function to insert a node at the beginning of the list
void insertAtBeginning(int data) {
    // Create the new node
    Node* newNode = createNode(data);
    if (newNode == NULL) {
        return; // Node creation failed
    }

    // Link the new node to the current head
    newNode->next = head;

    // Update the head to point to the new node
    head = newNode;

    printf("Inserted %d at the beginning.\n", data);
}
  • Create the node.
  • Point the next of the new node to the current head of the list.
  • Update the head pointer to point to the newNode, making it the new first node.

b) Inserting at the End (Append)

This requires traversing the list to find the last node (O(n) time complexity).

// Function to insert a node at the end of the list
void insertAtEnd(int data) {
    // Create the new node
    Node* newNode = createNode(data);
     if (newNode == NULL) {
        return; // Node creation failed
    }

    // If the list is empty, the new node becomes the head
    if (head == NULL) {
        head = newNode;
        printf("Inserted %d as the first node (at the end).\n", data);
        return;
    }

    // Traverse to the last node
    Node* current = head;
    while (current->next != NULL) {
        current = current->next; // Move to the next node
    }

    // Link the last node's next pointer to the new node
    current->next = newNode;
    printf("Inserted %d at the end.\n", data);
}
  • Create the node.
  • Handle the special case: If the list is empty (head == NULL), the new node is the head.
  • Otherwise, start from the head and iterate (while (current->next != NULL)) until you find the node whose next pointer is NULL. This is the last node.
  • Set the next pointer of that last node to point to the newNode.

3. Traversal (Printing the List)

To see the contents of the list, we need to traverse it from beginning to end.

// Function to print all elements in the linked list
void printList() {
    // Start from the head
    Node* current = head;

    if (current == NULL) {
        printf("List is empty.\n");
        return;
    }

    printf("List: ");
    // Traverse until the end of the list (current becomes NULL)
    while (current != NULL) {
        printf("%d -> ", current->data); // Print the data
        current = current->next;       // Move to the next node
    }
    printf("NULL\n"); // Indicate the end of the list
}
  • Use a temporary pointer (current) initialized to head.
  • Loop as long as current is not NULL.
  • Inside the loop, process the current->data (here, we print it).
  • Crucially, update current = current->next to move to the next node for the next iteration.

4. Searching for a Node

Find if a node with specific data exists in the list.

// Function to search for a node with specific data
Node* searchNode(int data) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == data) {
            printf("Found node with data %d at address %p.\n", data, (void*)current);
            return current; // Return pointer to the found node
        }
        current = current->next;
    }
    printf("Node with data %d not found.\n", data);
    return NULL; // Data not found
}
  • Traverse the list similar to printing.
  • In each iteration, check if current->data matches the target data.
  • If found, return the pointer to that node (current).
  • If the loop finishes without finding the data, return NULL.

5. Deletion

Removing nodes also requires careful pointer manipulation and memory management (free).

a) Deleting the First Node

Relatively simple (O(1)).

// Function to delete the first node in the list
void deleteFirstNode() {
    if (head == NULL) {
        printf("Cannot delete from an empty list.\n");
        return;
    }

    // Store the current head in a temporary pointer
    Node* temp = head;

    // Update head to point to the second node
    head = head->next;

    // Free the memory of the original first node
    printf("Deleting first node with data %d.\n", temp->data);
    free(temp);
    temp = NULL; // Good practice
}
  • Check if the list is empty.
  • Create a temporary pointer (temp) to hold the current head.
  • Move the head pointer to the next node (head = head->next).
  • free() the memory pointed to by temp.

b) Deleting a Node with Specific Data

This is more complex as you need to find the node before the one you want to delete (O(n)).

// Function to delete a node with specific data
void deleteNodeByData(int data) {
    if (head == NULL) {
        printf("List is empty, cannot delete.\n");
        return;
    }

    Node* current = head;
    Node* previous = NULL; // Keep track of the previous node

    // Special case: Deleting the head node
    if (current != NULL && current->data == data) {
        head = current->next; // Move head
        printf("Deleting head node with data %d.\n", data);
        free(current);       // Free old head
        current = NULL;
        return;
    }

    // Traverse to find the node to delete, keeping track of the previous one
    while (current != NULL && current->data != data) {
        previous = current;
        current = current->next;
    }

    // If the node was not found
    if (current == NULL) {
        printf("Node with data %d not found for deletion.\n", data);
        return;
    }

    // Node found, bypass it in the list
    // Link the previous node's next to the current node's next
    previous->next = current->next;

    // Free the memory of the node to be deleted
    printf("Deleting node with data %d.\n", data);
    free(current);
    current = NULL;
}
  • Handle the empty list case.
  • Handle the special case where the head node itself needs to be deleted (similar to deleteFirstNode).
  • Use two pointers: current starts at head, and previous starts at NULL.
  • Iterate through the list. In each step, update previous = current before updating current = current->next.
  • Stop when current points to the node to be deleted (or when current becomes NULL if not found).
  • If found, link the previous node directly to the node after current (previous->next = current->next). This effectively removes current from the chain.
  • free(current).

6. Freeing the Entire List

Crucial for preventing memory leaks when the list is no longer needed.

// Function to free all nodes in the linked list
void freeList() {
    Node* current = head;
    Node* nextNode = NULL;

    printf("Freeing the entire list...\n");
    while (current != NULL) {
        nextNode = current->next; // Store pointer to the next node
        printf("Freeing node with data %d at %p\n", current->data, (void*)current);
        free(current);           // Free the current node
        current = nextNode;      // Move to the next node
    }

    // Reset head to NULL as the list is now empty
    head = NULL;
    printf("List freed successfully.\n");
}
  • Use two pointers: current and nextNode.
  • Iterate while current is not NULL.
  • Inside the loop: First, save the address of the next node (nextNode = current->next). Then, free(current). Finally, update current = nextNode to move to the next node you saved earlier. (If you freed current first, you'd lose the link to the rest of the list!)
  • Set head = NULL at the end.

Example Usage (main function)

Let's put some of these functions together:

// (Include struct definition and all function definitions from above here)

int main() {
    printList(); // List is empty.

    insertAtBeginning(10);
    insertAtBeginning(5);
    insertAtEnd(20);
    insertAtEnd(30);
    insertAtBeginning(1);

    printList(); // List: 1 -> 5 -> 10 -> 20 -> 30 -> NULL

    searchNode(10); // Found node with data 10...
    searchNode(99); // Node with data 99 not found.

    deleteNodeByData(10); // Deleting node with data 10.
    printList(); // List: 1 -> 5 -> 20 -> 30 -> NULL

    deleteFirstNode(); // Deleting first node with data 1.
    printList(); // List: 5 -> 20 -> 30 -> NULL

    deleteNodeByData(30); // Deleting node with data 30.
    printList(); // List: 5 -> 20 -> NULL

    deleteNodeByData(5);
    deleteNodeByData(20);
    printList(); // List is empty.

    // Test inserting into an empty list after deletion
    insertAtEnd(55);
    printList(); // List: 55 -> NULL

    // CRITICAL: Always free the list when done!
    freeList();
    printList(); // List is empty.

    return 0;
}

Variations (Briefly)

  • Doubly Linked List: Each node has pointers to both the next and the previous node. Allows traversal in both directions but uses more memory.
  • Circular Linked List: The next pointer of the last node points back to the head node instead of NULL, forming a circle.

Conclusion

Linked lists are a cornerstone data structure, offering dynamic resizing and efficient insertions/deletions at the cost of direct access. Understanding how to manipulate nodes using pointers and managing their memory lifecycle with malloc and free is a vital skill for any C programmer. You've now learned how to implement the fundamental operations for a singly linked list.

In our next C intermediate tutorial, we'll build upon these concepts to implement Stacks and Queues, which can often be efficiently realized using linked lists!

Further Reading & Related Posts

Discuss on Twitter • View on GitHub