October 17, 2026

1. Introduction to Linked Lists

What Is a Linked List?

A linked list is a linear data structure made up of individual elements called nodes. Each node stores data and one or more pointers that connect it to other nodes.

Unlike an array, linked-list nodes do not need to occupy consecutive memory locations. Nodes are connected using pointers.

A basic singly linked-list node contains:

1. Data: The value stored in the node.

2. Next pointer: The address of the next node.

Example:

HEAD
  |
  v
[10 | next] -> [20 | next] -> [30 | NULL]

Here:

• HEAD points to the first node.

• The first node stores 10.

• The second node stores 20.

• The third node stores 30.

• NULL indicates that there is no next node.

Array vs Linked List

Important: A linked list does not automatically make every operation faster. For example, accessing the 100th element requires traversing the preceding nodes.

When Are Linked Lists Useful?

Linked lists can be useful when:

• The number of elements changes frequently.

• Insertions and deletions occur at known positions.

• A stack or queue needs a dynamically growing representation.

• Nodes represent relationships between records.

2. Node Creation Using Structures and Pointers

In C, a linked-list node is commonly represented using a struct containing data and a pointer to another node of the same type.

Defining a Node

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

Explanation:

• int data stores the node's value.

• struct Node *next stores a pointer to another struct Node.

• NULL is used when a node has no next node.

Creating a Node Dynamically

We can use malloc() to allocate memory for a node at runtime. The stdlib.h header is required.

#include 
#include 

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

int main(void) {
    struct Node *newNode = malloc(sizeof *newNode);

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }

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

    printf("Data: %d\n", newNode->data);

    free(newNode);
    return 0;
}

Output:

Data: 10

Understanding the Arrow Operator

The expression:

newNode->data = 10;

accesses the data member through a pointer. It is equivalent to:

(*newNode).data = 10;

Always check whether malloc() returns NULL before using the allocated memory.

Memory rule: Memory allocated with malloc() must eventually be released using free() when it is no longer needed.

3. Singly Linked List

What Is a Singly Linked List?

A singly linked list is a linked list in which each node contains a pointer to the next node.

HEAD
  |
  v
[10 | *] -> [20 | *] -> [30 | NULL]

Traversal normally starts at HEAD and moves forward until a pointer becomes NULL.

Creating and Displaying a Singly Linked List

The following program creates three nodes and connects them.

#include 
#include 

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

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

    head = malloc(sizeof *head);
    second = malloc(sizeof *second);
    third = malloc(sizeof *third);

    if (head == NULL || second == NULL || third == NULL) {
        printf("Memory allocation failed\n");
        free(head);
        free(second);
        free(third);
        return 1;
    }

    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = NULL;

    struct Node *current = head;

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

    printf("NULL\n");

    free(third);
    free(second);
    free(head);

    return 0;
}

Output:

10 -> 20 -> 30 -> NULL

The program creates three nodes, connects them, traverses the list, and releases the allocated memory.

For larger programs, helper functions are more convenient than manually creating each node.

4. Insertion Operations

Insertion means adding a new node to a linked list.

Common insertion operations are:

1. Insert at the beginning.

2. Insert at the end.

3. Insert at a specified position.

In the examples below, positions are 1-based: position 1 means the beginning of the list.

A. Insert at the Beginning

Suppose the list is:

10 -> 20 -> 30 -> NULL

Insert 5 at the beginning:

5 -> 10 -> 20 -> 30 -> NULL

The new node points to the old head, and then head is updated.

newNode->next = head;
head = newNode;

Time complexity: (O(1)).

B. Insert at the End

Suppose the list is:

10 -> 20 -> 30 -> NULL

Insert 40:

10 -> 20 -> 30 -> 40 -> NULL

Traverse to the last node and set its next pointer to the new node.

Time complexity: (O(n)) when only the head pointer is maintained.

C. Insert at a Specified Position

To insert 25 at position 3:

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

After:  10 -> 20 -> 25 -> 30 -> NULL

The new node is connected between the second and third nodes.

Complete Insertion Program

#include 
#include 

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

struct Node *createNode(int value) {
    struct Node *node = malloc(sizeof *node);

    if (node == NULL) {
        return NULL;
    }

    node->data = value;
    node->next = NULL;
    return node;
}

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

int insertAtBeginning(struct Node **head, int value) {
    struct Node *node = createNode(value);

    if (node == NULL) {
        return 0;
    }

    node->next = *head;
    *head = node;
    return 1;
}

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

    if (node == NULL) {
        return 0;
    }

    if (*head == NULL) {
        *head = node;
        return 1;
    }

    struct Node *current = *head;

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

    current->next = node;
    return 1;
}

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

    if (position == 1) {
        return insertAtBeginning(head, value);
    }

    struct Node *current = *head;
    int i;

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

    if (current == NULL) {
        return 0;
    }

    struct Node *node = createNode(value);

    if (node == NULL) {
        return 0;
    }

    node->next = current->next;
    current->next = node;

    return 1;
}

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

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

    if (!insertAtEnd(&head, 10) ||
        !insertAtEnd(&head, 20) ||
        !insertAtEnd(&head, 30)) {
        printf("Memory allocation failed\n");
        freeList(head);
        return 1;
    }

    printf("Original list: ");
    display(head);

    if (!insertAtBeginning(&head, 5) ||
        !insertAtEnd(&head, 40) ||
        !insertAtPosition(&head, 25, 4)) {
        printf("Insertion failed\n");
        freeList(head);
        return 1;
    }

    printf("After insertion: ");
    display(head);

    freeList(head);
    return 0;
}

Output:

Original list: 10 -> 20 -> 30 -> NULL
After insertion: 5 -> 10 -> 20 -> 25 -> 30 -> 40 -> NULL

Notice that the position used for inserting 25 is 4 because the list already begins with 5.

5. Deletion Operations

Deletion removes a node from the linked list. In C, deleting a node also requires releasing its allocated memory.

Common operations include:

• Delete the first node.

• Delete the last node.

• Delete a node at a specified position.

A. Delete from the Beginning

Before:

10 -> 20 -> 30 -> NULL

After deleting the first node:

20 -> 30 -> NULL

The head is moved to the second node, and the old first node is freed.

B. Delete from the End

Before:

10 -> 20 -> 30 -> NULL

After:

10 -> 20 -> NULL

Traverse to the second-last node, free the last node, and set the second-last node's next pointer to NULL.

C. Delete from a Specified Position

Before deleting position 2:

10 -> 20 -> 30 -> NULL

After:

10 -> 30 -> NULL

The previous node is linked directly to the node after the one being removed.

Deletion Functions in C

Add these functions to the insertion program above:

int deleteAtBeginning(struct Node **head) {
    if (*head == NULL) {
        return 0;
    }

    struct Node *temp = *head;
    *head = (*head)->next;

    free(temp);
    return 1;
}

int deleteAtEnd(struct Node **head) {
    if (*head == NULL) {
        return 0;
    }

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

    struct Node *current = *head;

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

    free(current->next);
    current->next = NULL;

    return 1;
}

int deleteAtPosition(struct Node **head, int position) {
    if (position < 1 || *head == NULL) {
        return 0;
    }

    if (position == 1) {
        return deleteAtBeginning(head);
    }

    struct Node *current = *head;
    int i;

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

    if (current == NULL || current->next == NULL) {
        return 0;
    }

    struct Node *temp = current->next;
    current->next = temp->next;

    free(temp);
    return 1;
}

These functions return 1 when deletion succeeds and 0 if the position is invalid or the list is empty.

Important: Never dereference a pointer to a node after freeing that node.

6. Traversal and Searching

Traversal

Traversal means visiting each node from the beginning to the end of the list.

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

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

    printf("NULL\n");
}

If the list is:

10 -> 20 -> 30 -> NULL

The output is:

10 -> 20 -> 30 -> NULL

Traversal takes (O(n)) time because every node may need to be visited.

Searching for an Element

Searching means finding whether a particular value exists in the linked list.

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

    while (head != NULL) {
        if (head->data == key) {
            return position;
        }

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

    return -1;
}

Example:

int position = search(head, 20);

if (position != -1) {
    printf("Found at position %d\n", position);
} else {
    printf("Element not found\n");
}

If the list contains 10 -> 20 -> 30 -> NULL, the output is:

Found at position 2

The search function returns the first matching position or -1 if the value is absent.

Time complexity: (O(n)) in the worst case.

7. Reversing a Linked List

What Is Reversal?

Reversing a singly linked list changes the direction of its links so that the last node becomes the first node.

Before:

HEAD -> 10 -> 20 -> 30 -> NULL

After:

HEAD -> 30 -> 20 -> 10 -> NULL

A common iterative approach uses three pointers:

• prev: The previous node.

• current: The node currently being processed.

• next: Saves the next node before the current link is reversed.

Reversal Algorithm

1. Initialize prev to NULL.

2. Set current to the head.

3. Save current->next in next.

4. Point current->next to prev.

5. Move prev and current one node forward.

6. Repeat until current becomes NULL.

7. Update the head to prev.

Reverse Function in C

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

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

        prev = current;
        current = next;
    }

    return prev;
}

Use it like this:

head = reverseList(head);
display(head);

Output for the original list 10 -> 20 -> 30:

30 -> 20 -> 10 -> NULL

Complexity

• Time: (O(n)).

• Auxiliary space: (O(1)).

The iterative method is memory-efficient because it reverses the links in place.

8. Doubly Linked List

What Is a Doubly Linked List?

A doubly linked list stores two pointers in each node:

• prev: Points to the previous node.

• next: Points to the next node.

This allows traversal in both directions.

NULL <- [10] <-> [20] <-> [30] -> NULL

The first node's prev pointer is NULL, and the last node's next pointer is NULL.

Node Structure

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

Creating and Displaying a Doubly Linked List

#include 
#include 

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

int main(void) {
    struct DNode *first = malloc(sizeof *first);
    struct DNode *second = malloc(sizeof *second);
    struct DNode *third = malloc(sizeof *third);

    if (first == NULL || second == NULL || third == NULL) {
        printf("Memory allocation failed\n");
        free(first);
        free(second);
        free(third);
        return 1;
    }

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

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

    third->data = 30;
    third->prev = second;
    third->next = NULL;

    struct DNode *current = first;

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

    printf("\nBackward: ");
    current = third;

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

    printf("\n");

    free(third);
    free(second);
    free(first);

    return 0;
}

Output:

Forward: 10 20 30
Backward: 30 20 10

Advantages

• Supports forward and backward traversal.

• Deleting a known node can be efficient because its previous node is directly available.

• Useful for navigation systems that move both forward and backward.

Disadvantages

• Requires extra memory for the prev pointer.

• Insertions and deletions must maintain both pointer links correctly.

9. Circular Linked List

What Is a Circular Linked List?

In a circular linked list, the last node points back to the first node instead of pointing to NULL.

HEAD -> [10] -> [20] -> [30]
          ^                 |
          |_________________|

There is no NULL link at the end of a non-empty circular singly linked list.

Creating and Traversing a Circular List

#include 
#include 

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

int main(void) {
    struct Node *first = malloc(sizeof *first);
    struct Node *second = malloc(sizeof *second);
    struct Node *third = malloc(sizeof *third);

    if (first == NULL || second == NULL || third == NULL) {
        printf("Memory allocation failed\n");
        free(first);
        free(second);
        free(third);
        return 1;
    }

    first->data = 10;
    first->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = first;

    struct Node *current = first;

    printf("Circular list: ");

    if (current != NULL) {
        do {
            printf("%d ", current->data);
            current = current->next;
        } while (current != first);
    }

    printf("(back to head)\n");

    third->next = NULL;

    free(third);
    free(second);
    free(first);

    return 0;
}

Output:

Circular list: 10 20 30 (back to head)

The do-while loop is useful because it visits the first node before checking whether traversal has returned to the head.

Before freeing the nodes, the example breaks the circular link to make the cleanup straightforward.

Important: Do not use a normal while (current != NULL) traversal for this circular list. It would never terminate because the links eventually lead back to the first node.

Applications

Circular linked lists are useful for:

• Round-robin CPU scheduling.

• Repeating playlists.

• Turn-based games.

• Cyclic task management.

10. Applications of Linked Lists

Linked lists are used in several data-structure and software-design scenarios.

A. Implementing Stacks

A stack can use a linked list to support push and pop operations at the head.

• Push at head: (O(1)).

• Pop from head: (O(1)).

B. Implementing Queues

A linked-list queue can maintain both front and rear pointers.

• Enqueue at rear: (O(1)).

• Dequeue from front: (O(1)).

These complexities assume the queue maintains the appropriate pointers.

C. Music Playlists

A doubly linked list can support moving to the next and previous tracks.

D. Browser Navigation

A doubly linked list is one possible way to represent backward and forward navigation history, although actual browsers may use more sophisticated structures.

E. Graph Representation

Adjacency lists can use linked-list-like structures to represent each vertex's neighbors.

F. Dynamic Memory Management

Linked structures can represent collections whose sizes change during execution.

Linked List Operations: Complexity Summary

For insertion or deletion at a known node, pointer updates can be (O(1)), but finding that node may still require (O(n)) traversal. A singly linked list also needs access to the previous node to delete a given node in the general case.

Final Summary

In Module 05, we covered:

1. Introduction to linked lists.

2. Node creation using structures and pointers.

3. Singly linked lists.

4. Insertion operations.

5. Deletion operations.

6. Traversal and searching.

7. Reversing a linked list.

8. Doubly linked lists.

9. Circular linked lists.

10. Applications of linked lists.

The central idea is that a linked list stores data in nodes connected through pointers. Understanding how those pointers change during insertion, deletion, and reversal is essential for writing correct C programs.