CODEBHAVYA • DATA STRUCTURES

🔗 Linked List

Learn how nodes are connected using pointers, visualize pointer changes step by step, and understand how linked-list operations are implemented in C.

LINKED LIST

📖 Introduction to Linked List

A linked list is a linear data structure made of separate memory blocks called nodes. Unlike an array, the nodes do not need to be stored in consecutive memory locations.

Each node stores the actual data and a pointer that tells us where the next node is located. The first node is reached using a pointer called head.

💡 Key Idea

In an array, elements are connected by index positions. In a linked list, nodes are connected by addresses stored in pointers.

🧠 Simple Example

If the list stores 10, 20, 30, the logical connection is: head → 10 → 20 → 30 → NULL. The final NULL tells us that the list has ended.

Why do we use Linked Lists?

Nodes can be created dynamically when needed.
Insertion and deletion do not require shifting all later elements.
The structure can grow or shrink during program execution.
Linked lists are used to build stacks, queues, graph adjacency lists and many other structures.

Important: A linked list gives flexible memory usage, but direct random access such as a[5] is not available. To reach a node, we usually move from the head one link at a time.

01 • FOUNDATION

🧩 Node Structure in C

Every singly linked-list node contains data and a pointer to the next node.

A single node

data 10

next address

→

next node

C Structure

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

Understanding each line

struct Node defines the format of one node.
int data; stores the actual value.
struct Node *next; stores the address of another node of the same type.

Remember: next does not store the next value. It stores the address of the next node.

02 • LINKED LIST TYPE

➡️ Singly Linked List

Each node has one link: a pointer to the next node.

data10

next•

→

data20

next•

→

data30

nextNULL

💡 Direction of movement

A singly linked list can naturally be traversed only in the forward direction: head → first node → second node → ... → NULL.

03 • BASIC OPERATION

🚶 Create and Traverse a Singly Linked List

Create nodes dynamically, connect them, and visit every node from head to NULL.

💡 Traversal Idea

Use a temporary pointer, usually called temp. Start it at head. Read the current node, then move using temp = temp->next. Stop when temp == NULL.

Algorithm

1. Set temp = head
2. While temp != NULL
      a. Process temp->data
      b. Move temp = temp->next
3. Stop when temp becomes NULL

CodeBhavya

Singly Linked List Visualizer

Create & Traverse

Node values (comma separated)

Speed

Load the list, then press Next to begin traversal.

Current—

Visited0

Nodes0

💻 C Program — Create and Traverse

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

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

int main()
{
    int n, value;
    struct Node *head = NULL;
    struct Node *tail = NULL;
    struct Node *newNode;
    struct Node *temp;

    scanf("%d", &n);

    for(int i = 0; i < n; i++)
    {
        scanf("%d", &value);

        newNode = (struct Node *)malloc(sizeof(struct Node));
        newNode->data = value;
        newNode->next = NULL;

        if(head == NULL)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail->next = newNode;
            tail = newNode;
        }
    }

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Sample Input

4
10 20 30 40

Sample Output

10 20 30 40

⚡ Complexity

Traversal: O(n)Every node is visited once.

Extra Space: O(1)Only a temporary pointer is used during traversal.

Direct Access: O(n)Reaching the kth node may require moving through earlier nodes.

Interview note: Traversal is the foundation for most linked-list operations. Searching, counting, printing and reaching a position all depend on moving pointer-by-pointer.

04 • INSERTION

➕ Insert a Node at the Beginning

Create a new node, point it to the current head, then make it the new head.

🧠 Example

Before insertion: head → 10 → 20 → 30 → NULL
Insert 5 at the beginning.
After insertion: head → 5 → 10 → 20 → 30 → NULL

Algorithm

1. Create newNode
2. Store the new value in newNode->data
3. Set newNode->next = head
4. Set head = newNode

CodeBhavya

Singly Linked List Visualizer

Insert at Beginning

Existing list

New value

Load the list, then press Next to see each pointer update.

Head10

Step0

Nodes3

💻 C Program — Insert at Beginning

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

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

struct Node *insertBeginning(struct Node *head, int value)
{
    struct Node *newNode;

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

    newNode->data = value;
    newNode->next = head;

    head = newNode;

    return head;
}

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *head;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;

    first->next = second;
    second->next = third;
    third->next = NULL;

    head = first;

    head = insertBeginning(head, 5);

    while(head != NULL)
    {
        printf("%d ", head->data);
        head = head->next;
    }

    return 0;
}

Initial List

10 20 30

Output After Inserting 5

5 10 20 30

⚡ Complexity

Time: O(1)No traversal is required.

Extra Space: O(1)One new node is allocated.

Pointer Changes: 2Update newNode->next and head.

Interview note: Inserting at the beginning of a singly linked list is a constant-time operation because we already have direct access to the head pointer.

05 • INSERTION

➕ Insert a Node at the End

Move to the last node, connect the new node after it, and keep the new node pointing to NULL.

🧠 Example

Before insertion: head → 10 → 20 → 30 → NULL
Insert 40 at the end.
After insertion: head → 10 → 20 → 30 → 40 → NULL

💡 Key Idea

If the list is not empty, use a temporary pointer and move until temp->next == NULL. At that moment, temp points to the last node. Then connect temp->next = newNode.

Algorithm

1. Create newNode
2. Store value in newNode->data
3. Set newNode->next = NULL
4. If head == NULL
      head = newNode
      stop
5. Set temp = head
6. While temp->next != NULL
      temp = temp->next
7. Set temp->next = newNode

CodeBhavya

Singly Linked List Visualizer

Insert at End

Existing list

New value

Load the list, then press Next to trace the pointer movement to the last node.

temp—

Step0

Nodes3

💻 C Program — Insert at End

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

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

struct Node *insertEnd(struct Node *head, int value)
{
    struct Node *newNode;
    struct Node *temp;

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

    newNode->data = value;
    newNode->next = NULL;

    if(head == NULL)
        return newNode;

    temp = head;

    while(temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;

    return head;
}

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *head;
    struct Node *temp;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;

    first->next = second;
    second->next = third;
    third->next = NULL;

    head = first;

    head = insertEnd(head, 40);

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Initial List

10 20 30

Output After Inserting 40

10 20 30 40

⚡ Complexity

Time: O(n)Without a tail pointer, we traverse to the last node.

Extra Space: O(1)Only one new node and a temporary pointer are required.

With Tail: O(1)If a tail pointer is maintained, insertion at end becomes constant time.

Interview note: If a singly linked list frequently performs insertions at the end, maintaining a tail pointer can reduce insertion time from O(n) to O(1).

06 • INSERTION

📍 Insert a Node at a Given Position

Move to the node before the required position, then reconnect two links in the correct order.

🧠 Example

Before insertion: head → 10 → 20 → 30 → 40 → NULL
Insert 25 at position 3.
After insertion: head → 10 → 20 → 25 → 30 → 40 → NULL

💡 Why pointer-update order matters

First save the remaining list using newNode->next = temp->next. Only after that should we execute temp->next = newNode. If the order is wrong, we may lose access to the rest of the list.

Algorithm

1. Create newNode
2. Store the new value
3. If position == 1
      newNode->next = head
      head = newNode
      stop
4. Set temp = head
5. Move temp to the node at position - 1
6. If temp == NULL
      position is invalid
7. Set newNode->next = temp->next
8. Set temp->next = newNode

CodeBhavya

Singly Linked List Visualizer

Insert at Position

Existing list

New value

Position (1-based)

Load the list and press Next to see how the two links are changed.

temp—

Position3

Nodes4

💻 C Program — Insert at Position

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

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

struct Node *insertAtPosition(struct Node *head, int value, int position)
{
    struct Node *newNode;
    struct Node *temp;

    if(position < 1)
        return head;

    newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->data = value;

    if(position == 1)
    {
        newNode->next = head;
        return newNode;
    }

    temp = head;

    for(int i = 1; i < position - 1 && temp != NULL; i++)
        temp = temp->next;

    if(temp == NULL)
    {
        free(newNode);
        return head;
    }

    newNode->next = temp->next;
    temp->next = newNode;

    return head;
}

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
    struct Node *head;
    struct Node *temp;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;
    fourth->data = 40;

    first->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = NULL;

    head = first;

    head = insertAtPosition(head, 25, 3);

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Initial List

10 20 30 40

Output After Inserting 25 at Position 3

10 20 25 30 40

⚡ Complexity

Best Case: O(1)Position 1 inserts directly at the head.

General Case: O(n)We may need to traverse to position - 1.

Extra Space: O(1)One new node plus a few pointer variables are used.

Interview note: For a 1-based position p, stop at node p - 1. Then perform newNode->next = temp->next before temp->next = newNode.

07 • DELETION

🗑️ Delete a Node at the Beginning

Move head to the second node, then free the old first node.

🧠 Example

Before deletion: head → 10 → 20 → 30 → NULL
Delete the first node.
After deletion: head → 20 → 30 → NULL

💡 Key Idea

Save the current head in a temporary pointer. Move head to head->next, then release the old first node using free(temp).

Algorithm

1. If head == NULL
      stop
2. Set temp = head
3. Set head = head->next
4. free(temp)
5. Return head

CodeBhavya

Singly Linked List Visualizer

Delete at Beginning

Existing list

Speed

Load the list, then press Next to delete the first node safely.

head10

Step0

Nodes3

💻 C Program — Delete at Beginning

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

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

struct Node *deleteBeginning(struct Node *head)
{
    struct Node *temp;

    if(head == NULL)
        return NULL;

    temp = head;
    head = head->next;

    free(temp);

    return head;
}

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *head;
    struct Node *temp;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;

    first->next = second;
    second->next = third;
    third->next = NULL;

    head = first;

    head = deleteBeginning(head);

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Initial List

10 20 30

Output

20 30

⚡ Complexity

Time: O(1)No traversal is required.

Extra Space: O(1)Only one temporary pointer is used.

MemoryThe removed node must be released using free().

Interview note: Never call free(head) before saving the next node. After memory is freed, reading head->next is invalid.

08 • DELETION

🗑️ Delete a Node at the End

Move to the last node while keeping track of the previous node, then disconnect and free the last node.

🧠 Example

Before deletion: head → 10 → 20 → 30 → 40 → NULL
Delete the last node.
After deletion: head → 10 → 20 → 30 → NULL

💡 Key Idea

A singly linked list cannot move backward. Therefore, while moving toward the last node, keep another pointer called prev one node behind temp.

Algorithm

1. If head == NULL
      stop
2. If head->next == NULL
      free(head)
      head = NULL
      stop
3. Set prev = NULL
4. Set temp = head
5. While temp->next != NULL
      prev = temp
      temp = temp->next
6. Set prev->next = NULL
7. free(temp)
8. Return head

CodeBhavya

Singly Linked List Visualizer

Delete at End

Existing list

Speed

Load the list, then press Next to move temp and prev toward the last node.

temp10

prevNULL

Nodes4

💻 C Program — Delete at End

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

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

struct Node *deleteEnd(struct Node *head)
{
    struct Node *temp;
    struct Node *prev;

    if(head == NULL)
        return NULL;

    if(head->next == NULL)
    {
        free(head);
        return NULL;
    }

    prev = NULL;
    temp = head;

    while(temp->next != NULL)
    {
        prev = temp;
        temp = temp->next;
    }

    prev->next = NULL;
    free(temp);

    return head;
}

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
    struct Node *head;
    struct Node *temp;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;
    fourth->data = 40;

    first->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = NULL;

    head = first;

    head = deleteEnd(head);

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Initial List

10 20 30 40

Output

10 20 30

⚡ Complexity

Time: O(n)We must reach the last node.

Extra Space: O(1)Only temp and prev are used.

Single NodeHandle the one-node list separately.

Interview note: In a singly linked list, even with a tail pointer, deleting the last node still generally needs O(n) time because we need the node before tail.

09 • DELETION

📍 Delete a Node at a Given Position

Reach the node before the target position, bypass the target node, and then free it.

🧠 Example

Before deletion: head → 10 → 20 → 30 → 40 → NULL
Delete position 3.
After deletion: head → 10 → 20 → 40 → NULL

💡 Key Idea

For position p, stop at node p - 1. Save the target node in deleteNode, bypass it using temp->next = deleteNode->next, then call free(deleteNode).

Algorithm

1. If head == NULL or position < 1
      stop
2. If position == 1
      delete the beginning node
      stop
3. Set temp = head
4. Move temp to position - 1
5. If temp == NULL or temp->next == NULL
      position is invalid
6. Set deleteNode = temp->next
7. Set temp->next = deleteNode->next
8. free(deleteNode)
9. Return head

CodeBhavya

Singly Linked List Visualizer

Delete at Position

Existing list

Position

Speed

Load the list, then press Next to find and remove the target node.

temp10

Position3

Nodes4

💻 C Program — Delete at Position

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

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

struct Node *deleteAtPosition(struct Node *head, int position)
{
    struct Node *temp;
    struct Node *deleteNode;

    if(head == NULL || position < 1)
        return head;

    if(position == 1)
    {
        temp = head;
        head = head->next;
        free(temp);

        return head;
    }

    temp = head;

    for(int i = 1; i < position - 1 && temp != NULL; i++)
        temp = temp->next;

    if(temp == NULL || temp->next == NULL)
        return head;

    deleteNode = temp->next;
    temp->next = deleteNode->next;

    free(deleteNode);

    return head;
}

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
    struct Node *head;
    struct Node *temp;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;
    fourth->data = 40;

    first->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = NULL;

    head = first;

    head = deleteAtPosition(head, 3);

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Initial List

10 20 30 40

Output After Deleting Position 3

10 20 40

⚡ Complexity

Best Case: O(1)Deleting position 1 is immediate.

General Case: O(n)We may traverse to position - 1.

Extra Space: O(1)Only pointer variables are used.

Interview note: Always reconnect the list before freeing the target node. Otherwise, the address of the remaining part of the list may be lost.

10 • SEARCHING

🔍 Search in a Singly Linked List

Traverse node by node from head until the target value is found or the list ends.

🧠 Example

List: head → 10 → 20 → 30 → 40 → NULL
Target: 30
Result: 30 is found at position 3.

💡 Key Idea

A singly linked list does not support direct indexing like an array. To search for a value, start from head and compare each node's data one by one.

Algorithm

1. Set temp = head
2. Set position = 1
3. While temp != NULL
      a. If temp->data == target
            return position
      b. temp = temp->next
      c. position++
4. Return -1

CodeBhavya

Singly Linked List Visualizer

Search in Linked List

Existing list

Target

Speed

Load the list, then press Next to compare the target with each node.

temp—

Position—

ResultNot started

💻 C Program — Search in Linked List

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

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

int search(struct Node *head, int target)
{
    struct Node *temp = head;
    int position = 1;

    while(temp != NULL)
    {
        if(temp->data == target)
            return position;

        temp = temp->next;
        position++;
    }

    return -1;
}

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
    struct Node *head;
    int result;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;
    fourth->data = 40;

    first->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = NULL;

    head = first;

    result = search(head, 30);

    if(result == -1)
        printf("Not Found");
    else
        printf("Found at position %d", result);

    return 0;
}

Target

Output

Found at position 3

⚡ Complexity

Best Case: O(1)The target is in the first node.

Worst Case: O(n)The target is last or not present.

Extra Space: O(1)Only a temporary pointer and counter are used.

Interview note: Searching in an unsorted singly linked list is linear. Unlike arrays, binary search is not naturally efficient because the middle node cannot be accessed directly.

11 • POINTER MANIPULATION

🔁 Reverse a Singly Linked List

Reverse every next pointer so the last node becomes the new head.

🧠 Example

Before reversal: head → 10 → 20 → 30 → 40 → NULL
After reversal: head → 40 → 30 → 20 → 10 → NULL

💡 Three-Pointer Technique

Use three pointers: prev, current, and nextNode. Before reversing a link, save the next node first. Otherwise, the remaining part of the list would be lost.

Algorithm

1. Set prev = NULL
2. Set current = head
3. While current != NULL
      a. nextNode = current->next
      b. current->next = prev
      c. prev = current
      d. current = nextNode
4. Set head = prev
5. Return head

CodeBhavya

Singly Linked List Visualizer

Reverse Linked List

Existing list

Speed

Load the list, then press Next to reverse each link one by one.

prevNULL

current10

nextNode—

💻 C Program — Reverse Linked List

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

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

struct Node *reverseList(struct Node *head)
{
    struct Node *prev = NULL;
    struct Node *current = head;
    struct Node *nextNode;

    while(current != NULL)
    {
        nextNode = current->next;
        current->next = prev;

        prev = current;
        current = nextNode;
    }

    head = prev;

    return head;
}

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
    struct Node *head;
    struct Node *temp;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;
    fourth->data = 40;

    first->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = NULL;

    head = first;

    head = reverseList(head);

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Original List

10 20 30 40

Reversed Output

40 30 20 10

⚡ Complexity

Time: O(n)Every node is processed once.

Extra Space: O(1)Only three pointer variables are used.

In-placeNo extra linked list is created.

Interview note: The most common reversal mistake is changing current->next before saving the original next node. Always execute nextNode = current->next first.

12 • LINKED LIST TYPE

↔️ Doubly Linked List

Each node stores links to both the previous node and the next node.

A doubly linked list (DLL) is a linked list in which every node contains three parts: a pointer to the previous node, the data, and a pointer to the next node.

NULL

←

prevNULL

data10

next•

↔

prev•

data20

next•

↔

prev•

data30

nextNULL

→

NULL

Node Structure in C

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

⬅️ Previous Link

prev stores the address of the previous node.

📦 Data

data stores the actual value.

➡️ Next Link

next stores the address of the next node.

💡 Main Advantage

Unlike a singly linked list, a doubly linked list supports movement in both forward and backward directions.

Trade-off: Each node needs one extra pointer (prev), so a doubly linked list uses more memory than a singly linked list.

13 • DOUBLY LINKED LIST

🚶 Forward and Backward Traversal

Move using next from head to tail or use prev from tail to head.

🧠 Example

Forward: 10 → 20 → 30 → 40
Backward: 40 → 30 → 20 → 10

Algorithms

Forward Traversal

temp = head
while(temp != NULL)
{
    visit(temp->data)
    temp = temp->next
}

Reach Tail

temp = head
while(temp->next != NULL)
    temp = temp->next

Backward Traversal

while(temp != NULL)
{
    visit(temp->data)
    temp = temp->prev
}

CodeBhavya

Doubly Linked List Visualizer

Forward & Backward Traversal

Node values

Direction

Speed

Load the list, choose a direction, and press Next.

Current—

Visited0

DirectionForward

💻 C Program — Forward and Backward Traversal

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

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

int main()
{
    struct Node *first;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
    struct Node *head;
    struct Node *temp;

    first = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));

    first->data = 10;
    second->data = 20;
    third->data = 30;
    fourth->data = 40;

    first->prev = NULL;
    first->next = second;

    second->prev = first;
    second->next = third;

    third->prev = second;
    third->next = fourth;

    fourth->prev = third;
    fourth->next = NULL;

    head = first;

    temp = head;

    printf("Forward: ");

    while(temp->next != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    printf("%d", temp->data);

    printf("\nBackward: ");

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->prev;
    }

    return 0;
}

Forward

10 20 30 40

Backward

40 30 20 10

⚡ Complexity

Forward: O(n)Every node is visited once using next.

Backward: O(n)Every node is visited once using prev.

Extra Space: O(1)Only pointer variables are required.

Interview note: Backward traversal is a direct advantage of a doubly linked list. In a singly linked list, moving to the previous node is not directly possible.

14 • DOUBLY LINKED LIST

➕ Insertions in a Doubly Linked List

Insertion requires maintaining both prev and next links correctly.

Insert at Beginning

Set newNode->next = head, set the old head's prev to the new node, then make the new node the head.

Insert at End

Move to the last node, connect its next to the new node, and set newNode->prev to the old last node.

Insert at Position

Connect the new node between two existing nodes by updating four pointer relationships when both neighbours exist.

Algorithms

Insert at Beginning:
1. newNode->prev = NULL
2. newNode->next = head
3. If head != NULL
      head->prev = newNode
4. head = newNode

Insert at End:
1. Move temp to last node
2. temp->next = newNode
3. newNode->prev = temp
4. newNode->next = NULL

Insert at Position:
1. Move temp to position - 1
2. newNode->prev = temp
3. newNode->next = temp->next
4. If temp->next != NULL
      temp->next->prev = newNode
5. temp->next = newNode

CodeBhavya

Doubly Linked List Visualizer

Insertion Operations

Existing list

Operation

New value

Position

Choose an insertion type and press Load Operation.

temp—

Step0

Nodes3

💻 C Program — DLL Insertion Operations

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

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

struct Node *insertBeginning(struct Node *head, int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = head;

    if(head != NULL)
        head->prev = newNode;

    return newNode;
}

struct Node *insertEnd(struct Node *head, int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->next = NULL;

    if(head == NULL)
    {
        newNode->prev = NULL;
        return newNode;
    }

    struct Node *temp = head;

    while(temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
    newNode->prev = temp;

    return head;
}

struct Node *insertAtPosition(
    struct Node *head,
    int value,
    int position)
{
    if(position <= 1)
        return insertBeginning(head, value);

    struct Node *temp = head;

    for(int i = 1;
        i < position - 1 && temp != NULL;
        i++)
    {
        temp = temp->next;
    }

    if(temp == NULL)
        return head;

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

    newNode->data = value;
    newNode->prev = temp;
    newNode->next = temp->next;

    if(temp->next != NULL)
        temp->next->prev = newNode;

    temp->next = newNode;

    return head;
}

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

    head = insertEnd(head, 10);
    head = insertEnd(head, 20);
    head = insertEnd(head, 30);

    head = insertBeginning(head, 5);
    head = insertEnd(head, 40);
    head = insertAtPosition(head, 25, 4);

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Operations

Start: 10 20 30
Beginning: 5
End: 40
Position 4: 25

Output

5 10 20 25 30 40

⚡ Complexity

Beginning: O(1)No traversal is required.

End: O(n)Without a tail pointer, reach the last node first.

Position: O(n)Traversal may be needed to reach position - 1.

Interview note: For a middle insertion, always update both directions. A correct DLL insertion must keep next and prev relationships consistent.

15 • DOUBLY LINKED LIST

🗑️ Deletions in a Doubly Linked List

Deletion reconnects the previous and next neighbours before the target node is freed.

Delete Beginning

Move head to the second node and set the new head's prev to NULL.

Delete End

Move to the last node and use its prev pointer to reach the previous node directly.

Delete at Position

Reconnect target->prev and target->next to each other, then free the target.

Algorithms

Delete Beginning:
1. temp = head
2. head = head->next
3. If head != NULL
      head->prev = NULL
4. free(temp)

Delete End:
1. Move temp to last node
2. If temp->prev != NULL
      temp->prev->next = NULL
   Else
      head = NULL
3. free(temp)

Delete at Position:
1. Move temp to target position
2. temp->prev->next = temp->next
3. If temp->next != NULL
      temp->next->prev = temp->prev
4. free(temp)

CodeBhavya

Doubly Linked List Visualizer

Deletion Operations

Existing list

Operation

Position

Choose a deletion type and press Load Operation.

temp—

Step0

Nodes4

💻 C Program — DLL Deletion Operations

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

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

struct Node *insertEnd(struct Node *head, int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->next = NULL;

    if(head == NULL)
    {
        newNode->prev = NULL;
        return newNode;
    }

    struct Node *temp = head;

    while(temp->next != NULL)
        temp = temp->next;

    temp->next = newNode;
    newNode->prev = temp;

    return head;
}

struct Node *deleteBeginning(struct Node *head)
{
    if(head == NULL)
        return NULL;

    struct Node *temp = head;

    head = head->next;

    if(head != NULL)
        head->prev = NULL;

    free(temp);

    return head;
}

struct Node *deleteEnd(struct Node *head)
{
    if(head == NULL)
        return NULL;

    struct Node *temp = head;

    while(temp->next != NULL)
        temp = temp->next;

    if(temp->prev != NULL)
        temp->prev->next = NULL;
    else
        head = NULL;

    free(temp);

    return head;
}

struct Node *deleteAtPosition(
    struct Node *head,
    int position)
{
    if(head == NULL)
        return NULL;

    if(position <= 1)
        return deleteBeginning(head);

    struct Node *temp = head;

    for(int i = 1;
        i < position && temp != NULL;
        i++)
    {
        temp = temp->next;
    }

    if(temp == NULL)
        return head;

    temp->prev->next = temp->next;

    if(temp->next != NULL)
        temp->next->prev = temp->prev;

    free(temp);

    return head;
}

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

    head = insertEnd(head, 10);
    head = insertEnd(head, 20);
    head = insertEnd(head, 30);
    head = insertEnd(head, 40);

    head = deleteAtPosition(head, 3);

    temp = head;

    while(temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    return 0;
}

Initial List

10 20 30 40

After Deleting Position 3

10 20 40

⚡ Complexity

Beginning: O(1)The new head is directly available.

End: O(n)Without a tail pointer, traversal to the last node is required.

Position: O(n)Traversal is needed to locate the target node.

Interview note: Once a target node is already known, removing it from a doubly linked list can be O(1) because its previous and next neighbours are directly accessible.

16 • CIRCULAR LINKED LIST

🔄 Circular Singly Linked List

The last node does not point to NULL. Instead, it points back to the first node.

💡 Core Idea

In a circular singly linked list, the final node's next pointer stores the address of head. Therefore, starting from head and repeatedly following next eventually returns to the first node.

🔁 last->next = head

🧠 Example

Logical order: 10 → 20 → 30 → 40 → back to 10.
There is no NULL link at the end.

Node Structure

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

Traversal Algorithm

1. If head == NULL
      stop
2. Set temp = head
3. Do
      visit(temp->data)
      temp = temp->next
   while(temp != head)

CodeBhavya

Circular Singly Linked List Visualizer

Traversal / Insert / Delete

Existing list

Operation

Value for insertion

Choose an operation and press Load Operation.

Current—

Step0

Nodes4

💻 C Program — Circular Singly Linked List

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

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

struct Node *insertEnd(struct Node *head, int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;

    if(head == NULL)
    {
        newNode->next = newNode;
        return newNode;
    }

    struct Node *temp = head;

    while(temp->next != head)
        temp = temp->next;

    temp->next = newNode;
    newNode->next = head;

    return head;
}

struct Node *insertBeginning(struct Node *head, int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;

    if(head == NULL)
    {
        newNode->next = newNode;
        return newNode;
    }

    struct Node *last = head;

    while(last->next != head)
        last = last->next;

    newNode->next = head;
    last->next = newNode;

    return newNode;
}

struct Node *deleteBeginning(struct Node *head)
{
    if(head == NULL)
        return NULL;

    if(head->next == head)
    {
        free(head);
        return NULL;
    }

    struct Node *last = head;

    while(last->next != head)
        last = last->next;

    struct Node *temp = head;

    head = head->next;
    last->next = head;

    free(temp);

    return head;
}

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

    head = insertEnd(head, 10);
    head = insertEnd(head, 20);
    head = insertEnd(head, 30);
    head = insertBeginning(head, 5);

    temp = head;

    do
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    while(temp != head);

    head = deleteBeginning(head);

    printf("\nAfter deletion: ");

    temp = head;

    do
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    while(temp != head);

    return 0;
}

Before Deletion

5 10 20 30

After Deletion

10 20 30

⚡ Complexity

Traversal: O(n)Stop after returning to head.

Insert Beginning: O(n)Without a tail pointer, find the last node first.

Insert End: O(n)Without a tail pointer, reach the last node first.

Interview note: Never traverse a circular list using while(temp != NULL). Since no node points to NULL, that condition can cause an infinite loop.

17 • CIRCULAR LINKED LIST

🔁 Circular Doubly Linked List

The first and last nodes are connected in both directions.

💡 Core Idea

In a circular doubly linked list: tail->next = head and head->prev = tail. This forms a two-way closed loop.

Forward circular link

tail->next = head

Backward circular link

head->prev = tail

Node Structure

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

Traversal

Forward:
temp = head
do
{
    visit(temp->data)
    temp = temp->next
}
while(temp != head)

Backward:
temp = head->prev
do
{
    visit(temp->data)
    temp = temp->prev
}
while(temp != head->prev)

CodeBhavya

Circular Doubly Linked List Visualizer

Forward / Backward / Insert / Delete

Existing list

Operation

Value for insertion

Choose an operation and press Load Operation.

Current—

Step0

Nodes4

💻 C Program — Circular Doubly Linked List

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

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

struct Node *insertEnd(struct Node *head, int value)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->data = value;

    if(head == NULL)
    {
        newNode->next = newNode;
        newNode->prev = newNode;

        return newNode;
    }

    struct Node *tail = head->prev;

    newNode->prev = tail;
    newNode->next = head;

    tail->next = newNode;
    head->prev = newNode;

    return head;
}

struct Node *insertBeginning(struct Node *head, int value)
{
    head = insertEnd(head, value);

    if(head != NULL)
        head = head->prev;

    return head;
}

struct Node *deleteBeginning(struct Node *head)
{
    if(head == NULL)
        return NULL;

    if(head->next == head)
    {
        free(head);
        return NULL;
    }

    struct Node *tail = head->prev;
    struct Node *temp = head;

    head = head->next;

    head->prev = tail;
    tail->next = head;

    free(temp);

    return head;
}

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

    head = insertEnd(head, 10);
    head = insertEnd(head, 20);
    head = insertEnd(head, 30);
    head = insertBeginning(head, 5);

    temp = head;

    printf("Forward: ");

    do
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    while(temp != head);

    temp = head->prev;

    printf("\nBackward: ");

    do
    {
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    while(temp != head->prev);

    head = deleteBeginning(head);

    printf("\nAfter deletion: ");

    temp = head;

    do
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    while(temp != head);

    return 0;
}

Forward / Backward

Forward: 5 10 20 30
Backward: 30 20 10 5

After Deleting Beginning

10 20 30

⚡ Complexity

Traversal: O(n)Stop when the pointer returns to the starting node.

Insert End: O(1)With head->prev, tail is directly accessible.

Delete Beginning: O(1)Head and tail links can be updated directly.

Interview note: A circular doubly linked list can reach the tail directly through head->prev, making several end operations more efficient than in a basic singly linked list.

18 • REVISION

📊 Linked List Comparison

Compare the four important linked-list structures before choosing one for a problem.

Feature	Singly Linked List	Doubly Linked List	Circular Singly Linked List	Circular Doubly Linked List
Node links	next	prev + next	next	prev + next
Last node points to	NULL	next = NULL	head	next = head
First node's prev	Not available	NULL	Not available	tail
Forward traversal	Yes	Yes	Yes, circular	Yes, circular
Backward traversal	No	Yes	No	Yes, circular
Extra pointer memory	Lower	Higher	Lower	Higher
Typical stopping condition	temp == NULL	temp == NULL	temp == head	temp == start/head
Delete known node	Needs previous node	Can reconnect prev/next directly	Needs previous node	Can reconnect prev/next directly

When should you use each type?

Singly Linked List

Use when memory should be smaller and mainly forward traversal is needed.

Doubly Linked List

Use when backward movement and easier deletion around a known node are important.

Circular Singly

Useful for cyclic processing such as round-robin scheduling and repeating sequences.

Circular Doubly

Useful when cyclic navigation is required in both directions, such as next/previous navigation.

Quick memory rule: SLL = one direction, DLL = two directions, CSLL = one-direction loop, CDLL = two-direction loop.

COMMON QUESTIONS

❓ Common Interview Questions

Think about each question first. Open the answer only when you want to verify your understanding.

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

Arrays store elements in contiguous memory and support direct indexing. Linked-list nodes can be scattered in memory and are connected using pointers. Array access by index is O(1), while linked-list access to an arbitrary position is generally O(n). Linked lists can perform some insertions and deletions without shifting elements.

Interview answer: Arrays give fast indexed access; linked lists give flexible node insertion/deletion through pointers.

2. Why is random access not efficient in a linked list?

A linked-list node stores only its data and link information. It does not know the address of an arbitrary indexed node. To reach position k, traversal normally starts from head and follows links one by one.

Interview answer: Linked lists have no direct indexing, so reaching an arbitrary node generally takes O(n) traversal.

3. How do you reverse a singly linked list in O(n) time and O(1) extra space?

Use three pointers: prev, current, and nextNode. For each node, first save current->next, then reverse current->next to point to prev. Move prev and current forward. Finally, set head to prev.

Interview answer: Save the next node first, reverse the current link, then advance the three pointers.

4. How can you find the middle node in one traversal?

Use slow and fast pointers. Move slow by one node and fast by two nodes. When fast reaches the end of the list, slow points to the middle node. With the common loop condition, an even-length list produces the second middle node.

Interview answer: Use slow/fast pointers; fast moves twice as quickly, so slow reaches the middle when fast reaches the end.

5. How do you find the Nth node from the end without counting all nodes first?

Use two pointers. Move the fast pointer N nodes ahead. Then move slow and fast together one node at a time. When fast becomes NULL, slow points to the Nth node from the end.

Interview answer: Keep an N-node gap between fast and slow; when fast reaches NULL, slow is at the required node.

6. How does Floyd's cycle detection algorithm work?

Use slow and fast pointers. Slow moves by one link while fast moves by two. If a cycle exists, they eventually meet inside the loop. If fast reaches NULL, the list has no cycle. The method uses O(n) time and O(1) extra space.

Interview answer: If slow and fast pointers ever meet, a cycle exists; otherwise fast eventually reaches NULL.

7. Why can deleting the last node of a singly linked list still be O(n) even with a tail pointer?

A tail pointer gives direct access to the last node, but a singly linked list cannot move backward. To make the previous node the new tail, the program generally has to traverse from head to find the node whose next points to tail.

Interview answer: Tail gives the last node, but not its predecessor; finding that predecessor still requires traversal.

8. What extra advantage does a doubly linked list provide?

Every node contains both prev and next pointers, so traversal can move in both directions. When a target node is already known, its neighbours can often be reconnected directly during deletion. The trade-off is additional memory and more pointer updates.

Interview answer: A DLL supports forward/backward traversal and easier neighbour reconnection, at the cost of one extra pointer per node.

9. Why is a do-while loop often used for circular linked-list traversal?

Circular traversal starts at head and must process the starting node before checking whether the pointer has returned to head. A do-while loop naturally executes the body once before testing the circular stopping condition.

Interview answer: A do-while processes head first and then stops when traversal returns to the starting node.

10. What pointer mistakes commonly cause linked-list bugs?

Common mistakes include dereferencing NULL, losing the rest of the list before saving a next pointer, forgetting to update both links in a doubly linked list, freeing a node too early, ignoring empty or one-node special cases, and using temp != NULL as the stopping condition for a circular list.

Interview answer: Most linked-list bugs come from incorrect pointer-update order, missing edge cases, or using the wrong stopping condition.

20 • PRACTICE

💻 Linked List Practice Problems

20 problems from fundamentals to circular linked lists. Each problem has 5 judge tests.

20Problems

100Total Tests

CLanguage

Judge0Code Execution

🏆 Practice Scoring

Solve without help for up to 100 points. If you open a hint, the competitive score is capped at 90. If you open the complete program, you can still finish the problem, but it is marked Completed instead of competitively solved.

🔗 Linked List

📖 Introduction to Linked List

💡 Key Idea

🧠 Simple Example

Why do we use Linked Lists?

🧩 Node Structure in C

C Structure

Understanding each line

➡️ Singly Linked List

💡 Direction of movement

🚶 Create and Traverse a Singly Linked List

💡 Traversal Idea

Algorithm

💻 C Program — Create and Traverse

Sample Input

Sample Output

💻 Program

🧠 What is happening?

📊 Live Variables

🔗 Live Linked List

⚡ Complexity

➕ Insert a Node at the Beginning

🧠 Example

Algorithm

💻 C Program — Insert at Beginning

Initial List

Output After Inserting 5

💻 Program

🧠 What is happening?

📊 Live Variables

🔗 Live Linked List

⚡ Complexity

➕ Insert a Node at the End

🧠 Example

💡 Key Idea

Algorithm

💻 C Program — Insert at End

Initial List

Output After Inserting 40

💻 Program

🧠 What is happening?

📊 Live Variables

🔗 Live Linked List

⚡ Complexity

📍 Insert a Node at a Given Position

🧠 Example

💡 Why pointer-update order matters

Algorithm

💻 C Program — Insert at Position

Initial List

Output After Inserting 25 at Position 3

💻 Program

🧠 What is happening?

📊 Live Variables

🔗 Live Linked List

⚡ Complexity

🗑️ Delete a Node at the Beginning

🧠 Example

💡 Key Idea

Algorithm

💻 C Program — Delete at Beginning

Initial List

Output

💻 Program

🧠 What is happening?

📊 Live Variables

🔗 Live Linked List

⚡ Complexity

🗑️ Delete a Node at the End

🧠 Example

💡 Key Idea

Algorithm

💻 C Program — Delete at End

Initial List

Output

💻 Program

🧠 What is happening?

📊 Live Variables

🔗 Live Linked List

⚡ Complexity