Meta Title (59 characters)

Linked List in C: Singly, Doubly & Circular List Guide

Meta Description (157 characters)

Learn Linked Lists in C with singly, doubly, and circular linked lists. Master insertion, deletion, reversal, searching, sorting, and interview problems.

Module 14: Linked List

Learning Objectives

By the end of this module, you will be able to:

• Understand what a linked list is.
• Learn how linked lists differ from arrays.
• Create and manipulate singly, doubly, and circular linked lists.
• Perform insertion, deletion, searching, reversing, and sorting operations.
• Analyze the time complexity of linked list operations.
• Solve common coding interview problems using linked lists.

Introduction

A Linked List is one of the most important linear data structures in Data Structures and Algorithms (DSA).

Unlike arrays, linked lists do not store elements in contiguous memory. Instead, each element (called a node) stores the data and the address of the next node.

Linked lists are widely used in:

• Operating Systems
• Memory Management
• Browser History
• Music Playlists
• Undo/Redo Operations
• Graph Algorithms
• Hash Tables
• Dynamic Memory Allocation

Array vs Linked List

What is a Linked List?

A linked list is a collection of nodes connected through pointers.

Each node contains:

• Data
• Address of the next node

Example

textCopy
1+------+-------+     +------+-------+     +------+------+
2| 10   |   •───|---->| 20   |   •───|---->| 30   | NULL |
3+------+-------+     +------+-------+     +------+------+

A pointer called head stores the address of the first node.

Node Structure

cCopy
1#include <stdio.h>
2#include <stdlib.h>
3
4struct Node
5{
6    int data;
7    struct Node *next;
8};

Creating a Node

cCopy
1struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
2
3newNode->data = 10;
4newNode->next = NULL;

Singly Linked List

A Singly Linked List (SLL) stores one pointer in each node that points to the next node.

Visualization:

genui{"computing_fundamentals_algorithms_learning_block":{"type_id":"SINGLY_LINKED_LIST_POINTERS"}}

Example

textCopy
1Head
2  │
3  ▼
410 → 20 → 30 → NULL

Advantages

• Less memory
• Easy to implement
• Efficient insertion/deletion

Disadvantages

• Cannot traverse backward
• Sequential access only

Traversing a Singly Linked List

cCopy
1#include <stdio.h>
2#include <stdlib.h>
3
4struct Node
5{
6    int data;
7    struct Node *next;
8};
9
10void display(struct Node *head)
11{
12    while(head != NULL)
13    {
14        printf("%d ", head->data);
15        head = head->next;
16    }
17}

Time Complexity

textCopy
1O(n)

Insertion Operations

Insertion can be performed:

• At the beginning
• At the end
• At a specific position

Insert at Beginning

cCopy
1void insertBeginning(struct Node **head, int value)
2{
3    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
4
5    newNode->data = value;
6    newNode->next = *head;
7
8    *head = newNode;
9}

Example

Before

textCopy
110 → 20 → 30

After inserting 5

textCopy
15 → 10 → 20 → 30

Time Complexity

textCopy
1O(1)

Insert at End

cCopy
1void insertEnd(struct Node **head, int value)
2{
3    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
4
5    newNode->data = value;
6    newNode->next = NULL;
7
8    if(*head == NULL)
9    {
10        *head = newNode;
11        return;
12    }
13
14    struct Node *temp = *head;
15
16    while(temp->next != NULL)
17        temp = temp->next;
18
19    temp->next = newNode;
20}

Time Complexity

textCopy
1O(n)

Deletion

Delete the first node.

cCopy
1void deleteBeginning(struct Node **head)
2{
3    if(*head == NULL)
4        return;
5
6    struct Node *temp = *head;
7
8    *head = (*head)->next;
9
10    free(temp);
11}

Time Complexity

textCopy
1O(1)

Deleting a node from the middle requires updating the previous node's next pointer.

Searching

Linear search is used because linked lists do not support random access.

cCopy
1int search(struct Node *head, int key)
2{
3    int position = 0;
4
5    while(head != NULL)
6    {
7        if(head->data == key)
8            return position;
9
10        position++;
11        head = head->next;
12    }
13
14    return -1;
15}

Time Complexity

textCopy
1O(n)

Reverse a Linked List

Reverse the direction of all links.

Before

textCopy
110 → 20 → 30 → NULL

After

textCopy
130 → 20 → 10 → NULL

Program

cCopy
1struct Node* reverse(struct Node *head)
2{
3    struct Node *prev = NULL;
4    struct Node *current = head;
5    struct Node *next = NULL;
6
7    while(current != NULL)
8    {
9        next = current->next;
10        current->next = prev;
11        prev = current;
12        current = next;
13    }
14
15    return prev;
16}

Time Complexity

textCopy
1O(n)

Sorting a Linked List

Bubble Sort can be used for linked lists.

Algorithm

1. Compare adjacent nodes.
2. Swap data if necessary.
3. Repeat until sorted.

Time Complexity

textCopy
1O(n²)

For large linked lists, Merge Sort is preferred because it runs in O(n log n).

Doubly Linked List

A Doubly Linked List (DLL) contains two pointers.

• Previous pointer
• Next pointer

Node Structure

cCopy
1struct Node
2{
3    int data;
4    struct Node *prev;
5    struct Node *next;
6};

Visualization

textCopy
1NULL ← 10 ⇄ 20 ⇄ 30 → NULL

Advantages

• Traverse forward
• Traverse backward
• Easier deletion

Disadvantages

• More memory
• Slightly more complex

Circular Linked List

In a Circular Linked List, the last node points back to the first node.

textCopy
110 → 20 → 30
2↑           │
3└───────────┘

Advantages

• Continuous traversal
• Useful for circular queues
• Round-robin scheduling
• Multiplayer games

Time Complexity of Linked List Operations

Practice Project 1: Reverse Linked List

cCopy
1struct Node* reverse(struct Node *head)
2{
3    struct Node *prev = NULL;
4
5    while(head != NULL)
6    {
7        struct Node *next = head->next;
8        head->next = prev;
9        prev = head;
10        head = next;
11    }
12
13    return prev;
14}

Time Complexity

textCopy
1O(n)

Practice Project 2: Detect Loop (Floyd's Cycle Detection)

Also called the Tortoise and Hare Algorithm.

Algorithm

• Slow pointer moves one node.
• Fast pointer moves two nodes.
• If they meet, a loop exists.

Program

cCopy
1int detectLoop(struct Node *head)
2{
3    struct Node *slow = head;
4    struct Node *fast = head;
5
6    while(fast && fast->next)
7    {
8        slow = slow->next;
9        fast = fast->next->next;
10
11        if(slow == fast)
12            return 1;
13    }
14
15    return 0;
16}

Time Complexity

textCopy
1O(n)

Space Complexity

textCopy
1O(1)

Practice Project 3: Merge Two Sorted Lists

Algorithm

1. Compare the first nodes.
2. Choose the smaller node.
3. Continue recursively or iteratively.
4. Return the merged list.

Simplified Recursive Implementation

cCopy
1struct Node* merge(struct Node *a, struct Node *b)
2{
3    if(a == NULL)
4        return b;
5
6    if(b == NULL)
7        return a;
8
9    if(a->data < b->data)
10    {
11        a->next = merge(a->next, b);
12        return a;
13    }
14
15    b->next = merge(a, b->next);
16
17    return b;
18}

Time Complexity

textCopy
1O(n + m)

Practice Project 4: Find Middle Node

Use the slow and fast pointer technique.

cCopy
1struct Node* middleNode(struct Node *head)
2{
3    struct Node *slow = head;
4    struct Node *fast = head;
5
6    while(fast && fast->next)
7    {
8        slow = slow->next;
9        fast = fast->next->next;
10    }
11
12    return slow;
13}

Example

textCopy
110 → 20 → 30 → 40 → 50

Output

textCopy
130

Time Complexity

textCopy
1O(n)

Common Interview Questions

1. Reverse a Linked List
2. Detect a Loop
3. Find the Middle Node
4. Merge Two Sorted Lists
5. Remove Duplicates
6. Delete Nth Node from End
7. Find Intersection Point
8. Check if Linked List is Palindrome
9. Rotate Linked List
10. Clone a Linked List with Random Pointer

Common Mistakes to Avoid

• Forgetting to allocate memory using malloc().
• Losing node references before updating pointers.
• Forgetting to free memory after deletion, causing memory leaks.
• Accessing NULL pointers.
• Not updating the head pointer after inserting or deleting the first node.
• Confusing singly linked lists with doubly linked lists when updating pointers.

Best Practices

• Always check whether a pointer is NULL before dereferencing it.
• Free dynamically allocated memory using free() to avoid memory leaks.
• Keep insertion and deletion functions modular and reusable.
• Use descriptive variable names such as head, current, previous, and next.
• Prefer the slow/fast pointer technique for problems such as finding the middle node and detecting loops.
• Use Merge Sort instead of Bubble Sort for sorting large linked lists because it offers better performance.

Module Summary

In this module, you learned:

• What a linked list is and how it differs from an array.
• The structure and implementation of singly, doubly, and circular linked lists.
• Core operations such as traversal, insertion, deletion, searching, reversing, and sorting.
• How to solve common interview problems including reversing a linked list, detecting loops, merging sorted lists, and finding the middle node.
• The time complexity of various linked list operations and when to use each type of linked list.

After completing this module, you'll be ready to learn Stacks, where you'll explore stack operations, array and linked-list implementations, recursion, expression evaluation, balanced parentheses, postfix and infix conversion, and other classic stack-based algorithms.