Linked Lists

3 min read

A Linked List is a linear data structure where elements are not stored at contiguous memory locations (like arrays). Instead, each element, called a node, is an independent structure that contains two parts:

Data: The actual information stored in the node.
Pointer (Link): A pointer to the next node in the sequence.

The first node in the list is always pointed to by a special pointer called the Head. The last node’s link pointer is set to NULL.

1. Defining the Node Structure

Every node in the linked list must be able to hold data and a pointer to the same type of node structure. This requires a self-referential structure.

// Define the structure for a node
typedef struct Node {
    int data;           // The data carried by this node
    struct Node *next;  // Pointer to the next node in the list
} Node; // The typedef alias is 'Node'

2. Creating a New Node

Creating a node requires dynamic memory allocation (malloc) because the list size is determined at runtime, and the nodes must persist beyond the function call stack.

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

// Function to allocate memory for a new node and initialize its values
Node* createNode(int value) {
    // 1. Allocate memory for one Node structure
    Node *newNode = (Node *)malloc(sizeof(Node));
    
    // 2. Check for allocation failure
    if (newNode == NULL) {
        perror("Error creating new node (malloc failed)");
        exit(EXIT_FAILURE); 
    }
    
    // 3. Initialize the data and set the next pointer to NULL
    newNode->data = value;
    newNode->next = NULL;
    
    return newNode;
}

3. Basic Operation: Insertion (At the Beginning)

Inserting a new node at the beginning is the simplest form of insertion, requiring only two steps to update the pointers.

Set the new node’s next pointer to point to the current Head.
Update the Head pointer to point to the new node.

Node *head = NULL; // Initially, the list is empty

// Function to insert a node at the beginning of the list
void insertAtBeginning(Node **head_ref, int value) {
    // 1. Create the new node
    Node *newNode = createNode(value);
    
    // 2. Point the new node's next to the current head
    newNode->next = *head_ref;
    
    // 3. Update the head to point to the new node
    *head_ref = newNode;
}

// Example call: Note we pass the ADDRESS of the head pointer (Node **)
// insertAtBeginning(&head, 50);

Note: We use Node **head_ref (a pointer to a pointer) because we need the function to modify the original head pointer in the calling function (achieving pass-by-reference for the pointer itself).

4. Basic Operation: Traversal (Printing the List)

To process all elements, you start at the Head and follow the next pointer until you reach the NULL terminator.

void traverseList(Node *head) {
    Node *current = head; // Start at the head
    
    printf("List: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next; // Move to the next node
    }
    printf("NULL\n");
}

5. Memory Cleanup (Deletion/Freeing)

Since linked list nodes are created on the heap, they must be manually freed to prevent memory leaks. The entire list can be freed by traversing it and freeing each node sequentially.

void freeList(Node *head) {
    Node *current = head;
    Node *next_node;

    while (current != NULL) {
        next_node = current->next; // Save the address of the next node
        free(current);             // Free the current node's memory
        current = next_node;       // Move to the saved next node
    }
}

What are your Feelings