Linked Lists

Lesson 33

Linked Lists in C are dynamic data structures where each node contains data and a pointer to the next node. Unlike arrays, they do not require contiguous memory, making them ideal for efficient insertion and deletion. Memory is managed dynamically using malloc() and free().

C Track

Save progress as you learn.

44 lessons

Lesson content

Linked Lists in C Programming: A Complete Beginner to Advanced Guide

What are Linked Lists in C Programming?

Linked Lists in C programming are dynamic data structures that store elements as individual nodes, where each node contains data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory locations, making them flexible for inserting and deleting elements.

Imagine a treasure hunt where each clue tells you where to find the next clue. You start with the first clue, follow its instructions to the next one, and continue until you reach the end. A linked list works the same way — each node points to the next node in the sequence.

Why Do Linked Lists Exist?

Arrays are efficient when you know the number of elements in advance. However, inserting or deleting elements in the middle of an array often requires shifting many elements. Linked lists solve this problem by allowing nodes to be inserted or removed without moving other elements.

Real-World Use Cases

Linked lists are widely used in:

Music playlists
Browser navigation (Back and Forward)
Undo and Redo functionality
Dynamic memory management
Hash tables
Graph representations
Polynomial manipulation
Operating system process management

Prerequisites

Before learning Linked Lists in C, you should understand:

Variables
Data types
Functions
Structures
Pointers
Dynamic memory allocation with malloc() and free()

Core Concepts

What is a Linked List?

A linked list is a linear data structure consisting of nodes connected using pointers. Each node contains data (the value to store) and a next pointer (the address of the next node). The first node is called the head, and the last node points to NULL.

Node Structure

A node is usually defined using a structure.

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

Creating a Node

Memory for a node is allocated dynamically using malloc(). Always check whether malloc() returns NULL before using the allocated memory.

struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));

Types of Linked Lists

Type	Description
Singly Linked List	Each node points to the next node only
Doubly Linked List	Each node has pointers to both the previous and next nodes
Circular Linked List	The last node points back to the first node
Circular Doubly Linked List	Nodes point both forward and backward in a circular manner

For beginners, the singly linked list is the best starting point.

Basic Operations

Common linked list operations include:

Create
Traverse
Insert
Delete
Search
Update

Code Examples

Example 1: Beginner – Create and Display a Linked List

#include <stdio.h>                      // Include standard input/output library
#include <stdlib.h>                     // Include memory allocation functions

struct Node                             // Define the node structure
{
    int data;                           // Store the node's value
    struct Node *next;                  // Pointer to the next node
};

int main()
{
    struct Node *head;                  // Pointer to the first node
    struct Node *second;                // Pointer to the second node

    head = (struct Node *)malloc(sizeof(struct Node));     // Allocate memory for first node
    second = (struct Node *)malloc(sizeof(struct Node));   // Allocate memory for second node

    if (head == NULL || second == NULL)                    // Check allocation success
    {
        printf("Memory allocation failed.\n");             // Display error
        return 1;                                          // Exit program
    }

    head->data = 10;                  // Store value in first node
    head->next = second;              // Link first node to second node

    second->data = 20;                // Store value in second node
    second->next = NULL;              // Mark the end of the list

    struct Node *temp = head;         // Temporary pointer for traversal

    while (temp != NULL)              // Traverse the list
    {
        printf("%d ", temp->data);    // Print node data
        temp = temp->next;            // Move to the next node
    }

    free(head);                       // Free first node
    free(second);                     // Free second node

    return 0;                         // End program
}

Output: 10 20

Example 2: Beginner – Insert at the Beginning

#include <stdio.h>                     // Include standard input/output library
#include <stdlib.h>                    // Include memory allocation functions

struct Node                            // Define node structure
{
    int data;                          // Node data
    struct Node *next;                 // Pointer to next node
};

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

    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); // Allocate memory

    if (newNode == NULL)               // Check allocation success
    {
        printf("Memory allocation failed.\n"); // Display error
        return 1;                      // Exit program
    }

    newNode->data = 50;                // Store value
    newNode->next = head;              // Point to current head
    head = newNode;                    // Update head pointer

    printf("%d\n", head->data);        // Print first node

    free(head);                        // Free allocated memory

    return 0;                          // End program
}

Output: 50

Example 3: Intermediate – Insert at the End

#include <stdio.h>                      // Include standard input/output library
#include <stdlib.h>                     // Include memory allocation functions

struct Node
{
    int data;                           // Store node value
    struct Node *next;                  // Pointer to next node
};

int main()
{
    struct Node *head = (struct Node *)malloc(sizeof(struct Node)); // Create first node
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); // Create new node

    if (head == NULL || newNode == NULL) // Check allocation success
    {
        printf("Memory allocation failed.\n"); // Display error
        return 1;                        // Exit program
    }

    head->data = 10;                     // Initialize first node
    head->next = NULL;                   // End of list

    newNode->data = 30;                  // Initialize new node
    newNode->next = NULL;                // New last node

    head->next = newNode;                // Link new node at the end

    struct Node *temp = head;            // Traverse pointer

    while(temp != NULL)                  // Traverse list
    {
        printf("%d ", temp->data);       // Print node
        temp = temp->next;               // Move forward
    }

    free(head);                          // Free first node
    free(newNode);                       // Free second node

    return 0;                            // End program
}

Output: 10 30

Example 4: Intermediate – Search for a Value

#include <stdio.h>                      // Include standard input/output library
#include <stdlib.h>                     // Include memory allocation functions

struct Node
{
    int data;                           // Node value
    struct Node *next;                  // Pointer to next node
};

int main()
{
    struct Node first = {10, NULL};     // First node
    struct Node second = {20, NULL};    // Second node

    first.next = &second;               // Link nodes

    int key = 20;                       // Value to search

    struct Node *temp = &first;         // Start traversal

    while(temp != NULL)                 // Traverse list
    {
        if(temp->data == key)           // Check value
        {
            printf("Found\n");          // Value found
            return 0;                   // Exit program
        }

        temp = temp->next;              // Move to next node
    }

    printf("Not Found\n");              // Value absent

    return 0;                           // End program
}

Output: Found

Example 5: Advanced – Delete the First Node

#include <stdio.h>                      // Include standard input/output library
#include <stdlib.h>                     // Include memory allocation functions

struct Node
{
    int data;                           // Node value
    struct Node *next;                  // Pointer to next node
};

int main()
{
    struct Node *head = (struct Node *)malloc(sizeof(struct Node)); // First node
    struct Node *second = (struct Node *)malloc(sizeof(struct Node)); // Second node

    if (head == NULL || second == NULL) // Check allocation success
    {
        printf("Memory allocation failed.\n"); // Display error
        return 1;                        // Exit program
    }

    head->data = 100;                    // Initialize first node
    head->next = second;                 // Link first to second

    second->data = 200;                  // Initialize second node
    second->next = NULL;                 // End of list

    struct Node *temp = head;            // Store first node

    head = head->next;                   // Move head to second node

    free(temp);                          // Free old first node

    printf("%d\n", head->data);          // Print new head

    free(head);                          // Free remaining node

    return 0;                            // End program
}

Output: 200

Common Mistakes and Pitfalls

Wrong	Correct
Dereferencing a NULL pointer	Check for NULL before accessing a node
Forgetting to free memory	Call free() for dynamically allocated nodes
Losing the head pointer during insertion	Store or update the head pointer carefully
Using an uninitialized pointer	Initialize pointers before use
Accessing temp->next when temp is NULL	Verify temp != NULL first

Wrong:

struct Node *ptr;

ptr->data = 10;

Correct:

struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));

if(ptr != NULL)
{
    ptr->data = 10;
    free(ptr);
}

Best Practices

Always check the return value of malloc().
Free every dynamically allocated node exactly once.
Initialize pointers to NULL when appropriate.
Use helper functions such as insertNode(), deleteNode(), and displayList() to keep code modular.
Update links carefully before deleting nodes.
Avoid memory leaks by freeing unused nodes.
Use meaningful variable names like head, tail, current, and newNode.

When NOT to Use This

Avoid linked lists when:

Fast random access by index is required.
The number of elements rarely changes.
Memory usage should be minimized, as each node stores an additional pointer.
Better cache performance is important; arrays are typically more cache-friendly.
Frequent searching is required, since linked lists require linear traversal.

Summary / Key Takeaways

Linked Lists in C programming store data as nodes connected through pointers.
Each node contains data and a pointer to the next node.
Linked lists support efficient insertion and deletion operations.
Memory is allocated dynamically using malloc() and released using free().
Common operations include insertion, deletion, traversal, searching, and updating.
Always check for NULL pointers and free allocated memory to avoid errors and leaks.
Linked lists are ideal for dynamic collections where the size changes frequently.
Arrays remain a better choice when fast indexed access is required.

FAQ About Linked Lists in C

1. What is a linked list in C programming?

A linked list is a dynamic data structure made up of nodes. Each node stores data and a pointer to the next node, allowing flexible insertion and deletion.

2. What is the difference between an array and a linked list?

Array	Linked List
Stored in contiguous memory	Nodes can be stored anywhere in memory
Fixed size (traditional arrays)	Can grow or shrink dynamically
Fast random access	Sequential access only
Slower insertion and deletion	Faster insertion and deletion when the node position is known

3. Why is malloc() used in linked lists?

malloc() dynamically allocates memory for new nodes at runtime, allowing the linked list to grow as needed.

4. Why should I call free() after deleting a node?

Calling free() releases dynamically allocated memory back to the system, preventing memory leaks.

5. Where are linked lists used in real-world software?

Linked lists are commonly used in browser history, music playlists, undo/redo systems, hash table collision handling, graph representations, memory management, process scheduling, and file system implementations.

Prev: Multi-dimensional Arrays Back to hub