C Linked Lists

An array stores elements in consecutive memory locations and requires you to decide its size upfront. A linked list is a different kind of data structure where each element (called a node) stores both data and a pointer to the next element. Nodes are scattered in memory — they do not need to be adjacent.

This makes linked lists ideal for situations where the number of elements changes frequently and you cannot predict the size in advance.

Linked List vs Array

Structure of a Linked List Node

Each node in a linked list has two parts:

1. Data — the value stored in the node
2. Next — a pointer to the next node in the list

struct Node {
    int data;
    struct Node *next;   // pointer to the next node
};

Visual Diagram

HEAD
 |
 v
+------+------+     +------+------+     +------+------+
| data | next | --> | data | next | --> | data | NULL |
|  10  |  *   |     |  20  |  *   |     |  30  |      |
+------+------+     +------+------+     +------+------+
  Node 1               Node 2               Node 3

- HEAD points to the first node
- Each node's 'next' points to the next node
- Last node's 'next' = NULL (end of list)

Types of Linked Lists

Creating a Singly Linked List

Step 1: Define the Node Structure

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

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

Step 2: Create a New Node

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

Insertion Operations

Insert at the Beginning

void insertAtBeginning(struct Node **head, int value)
{
    struct Node *newNode = createNode(value);
    newNode->next = *head;   // new node points to current head
    *head = newNode;          // head now points to new node
}

Insert at the End

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

    if (*head == NULL)   // list is empty
    {
        *head = newNode;
        return;
    }

    struct Node *current = *head;
    while (current->next != NULL)   // traverse to last node
        current = current->next;

    current->next = newNode;   // link last node to new node
}

Traversal — Printing All Nodes

void printList(struct Node *head)
{
    struct Node *current = head;

    printf("List: ");
    while (current != NULL)
    {
        printf("%d", current->data);
        if (current->next != NULL)
            printf(" -> ");
        current = current->next;
    }
    printf(" -> NULL\n");
}

Deletion Operation

Delete a Node by Value

void deleteNode(struct Node **head, int value)
{
    if (*head == NULL) return;

    // If the head node holds the value
    if ((*head)->data == value)
    {
        struct Node *temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }

    // Find the node before the one to delete
    struct Node *current = *head;
    while (current->next != NULL && current->next->data != value)
        current = current->next;

    if (current->next == NULL) return;   // value not found

    struct Node *temp = current->next;
    current->next = temp->next;   // bypass the deleted node
    free(temp);
}

Visual: Deleting a Node

Before deleting 20:
10 -> 20 -> 30 -> NULL

After deleting 20:
10 -> 30 -> NULL

Node holding 20 is freed from memory.
Node 10's 'next' now points directly to node 30.

Complete Linked List Program

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

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

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

void insertAtEnd(struct Node **head, int value) {
    struct Node *n = createNode(value);
    if (*head == NULL) { *head = n; return; }
    struct Node *cur = *head;
    while (cur->next) cur = cur->next;
    cur->next = n;
}

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

int main()
{
    struct Node *head = NULL;

    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);

    printList(head);   // Output: 10 -> 20 -> 30 -> 40 -> NULL

    return 0;
}

Counting Nodes

int countNodes(struct Node *head)
{
    int count = 0;
    while (head != NULL)
    {
        count++;
        head = head->next;
    }
    return count;
}

Freeing the Entire List

When the program ends, always free every node to avoid memory leaks.

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

Summary

A linked list is a dynamic data structure where each node holds data and a pointer to the next node. Unlike arrays, linked lists do not require a fixed size — they grow and shrink at runtime using dynamic memory allocation. The three core operations are insertion (at the beginning or end), traversal (visiting all nodes), and deletion (removing a specific node by updating pointers and freeing memory). A singly linked list is the most basic form, where each node points only to the next. Every dynamically allocated node must be freed when no longer needed to prevent memory leaks. Linked lists are the foundation for building more advanced data structures like stacks, queues, and trees.