Singly, Doubly, and Circular Linked Lists in C: Complete Code, Traversal & Memory Diagrams

Author: Bhuban Subedi | Subject: Data Structures and Algorithms (CACS201) | Semester: Third Semester

In the Tribhuvan University (TU) BCA Third Semester DSA (CACS201) curriculum, Linked Lists mark the transition from static contiguous memory structures (like Arrays) to true dynamic node-based data structures.

Why do we need Linked Lists when Arrays exist?
With arrays, inserting or deleting an element at the beginning requires shifting every single subsequent element to the right or left—an expensive $O(N)$ operation. Furthermore, contiguous memory allocation can fail if free RAM is fragmented.

A Linked List stores data across scattered heap memory locations, with each node containing a data field and one or more pointer links pointing to its neighbors.

In this master guide, we will break down Singly Linked Lists (SLL), Doubly Linked Lists (DLL), and Circular Linked Lists (CLL), analyze pointer manipulation step-by-step, and write production-grade C code.

1. Array vs. Linked List: The Architectural Showdown

+------------------------------------+------------------------------------+
| Arrays                             | Linked Lists                       |
+------------------------------------+------------------------------------+
| Fixed size (determined at compile  | Dynamic size (grows and shrinks at |
| time or initial allocation).       | runtime on demand).                |
+------------------------------------+------------------------------------+
| Contiguous memory allocation       | Scattered / Non-contiguous heap    |
| in RAM.                            | memory allocation.                 |
+------------------------------------+------------------------------------+
| Fast Random Access ($O(1)$ by index| Sequential Access ($O(N)$ traversal|
| `arr[i]`).                         | from `HEAD` pointer).              |
+------------------------------------+------------------------------------+
| Insertion/Deletion at beginning is | Insertion/Deletion at beginning is |
| slow ($O(N)$ element shifts).      | instant ($O(1)$ pointer update).   |
+------------------------------------+------------------------------------+
| Zero memory overhead per element.  | Extra memory overhead for storing  |
|                                    | pointers (`next`, `prev`).         |
+------------------------------------+------------------------------------+

2. Singly Linked List (SLL) Architecture

A Singly Linked List is a chain of nodes where each node contains data and a single pointer (next) pointing to the successive node. The last node points to NULL.

 HEAD
  |
  v
+------+------+     +------+------+     +------+------+
| Data | Next | --> | Data | Next | --> | Data | NULL |
|  10  | 2000 |     |  20  | 3000 |     |  30  |      |
+------+------+     +------+------+     +------+------+
Addr:  1000         Addr:  2000         Addr:  3000

Defining a Node in C:

struct Node {
    int data;
    struct Node *next; // Self-referential structure pointer
};

3. Singly Linked List Operations Explained

A. Insertion at the Beginning ($O(1)$ Time)

  1. Allocate memory for newNode using malloc.
  2. Set newNode->data = value.
  3. Set newNode->next = head.
  4. Update head = newNode.
 newNode               HEAD
+------+------+       +------+------+
|  5   | Next | ----> |  10  | Next | ---> ...
+------+------+       +------+------+

B. Insertion at the End ($O(N)$ Time)

  1. Allocate memory for newNode, set newNode->next = NULL.
  2. If head == NULL, set head = newNode.
  3. Otherwise, traverse from head until temp->next == NULL.
  4. Set temp->next = newNode.

C. Deletion by Value ($O(N)$ Time)

  1. If head->data == target, update head = head->next, and free(oldHead).
  2. Otherwise, use two pointers (prev and curr) to locate the target.
  3. Link prev->next = curr->next.
  4. Call free(curr).

4. Complete C Implementation: Singly Linked List

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

// Self-referential node structure
struct Node {
    int data;
    struct Node *next;
};

// Function prototypes
struct Node* createNode(int value);
void insertAtBeginning(struct Node **head, int value);
void insertAtEnd(struct Node **head, int value);
void deleteNode(struct Node **head, int key);
void reverseList(struct Node **head);
void displayList(struct Node *head);

int main() {
    struct Node *head = NULL; // Initially empty list

    printf("--- SINGLY LINKED LIST DEMONSTRATION ---\n");
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
    printf("List after inserting 10, 20, 30 at beginning:\n");
    displayList(head);

    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    printf("\nList after inserting 40, 50 at end:\n");
    displayList(head);

    printf("\nDeleting node with value 30...\n");
    deleteNode(&head, 30);
    displayList(head);

    printf("\nReversing the entire Linked List in-place...\n");
    reverseList(&head);
    displayList(head);

    return 0;
}

// Helper to allocate a node
struct Node* createNode(int value) {
    struct Node *newNode = (struct Node*) malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Insertion at beginning - O(1)
void insertAtBeginning(struct Node **head, int value) {
    struct Node *newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

// Insertion at end - O(N)
void insertAtEnd(struct Node **head, int value) {
    struct Node *newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node *temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Deletion of a specific node
void deleteNode(struct Node **head, int key) {
    struct Node *temp = *head;
    struct Node *prev = NULL;

    // Case 1: Key is at the head
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        printf("[DELETED] Successfully removed %d\n", key);
        return;
    }

    // Case 2: Search for key
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("[NOT FOUND] Value %d not found in list.\n", key);
        return;
    }

    // Unlink node and free memory
    prev->next = temp->next;
    free(temp);
    printf("[DELETED] Successfully removed %d\n", key);
}

// In-place Reversal Algorithm - O(N) Time, O(1) Space
void reverseList(struct Node **head) {
    struct Node *prev = NULL;
    struct Node *curr = *head;
    struct Node *next = NULL;

    while (curr != NULL) {
        next = curr->next;  // Store next node
        curr->next = prev;  // Reverse pointer
        prev = curr;        // Move prev forward
        curr = next;        // Move curr forward
    }
    *head = prev;
}

// Display list elements
void displayList(struct Node *head) {
    struct Node *temp = head;
    if (temp == NULL) {
        printf("List is empty.\n");
        return;
    }
    while (temp != NULL) {
        printf("[%d] -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

5. Doubly Linked List (DLL)

A Doubly Linked List allows bidirectional traversal (both forward and backward). Each node contains two pointers: next and prev.

         HEAD
          |
          v
NULL <-- +------+------+------+ <===> +------+------+------+ --> NULL
         | Prev | Data | Next |       | Prev | Data | Next |
         +------+------+------+       +------+------+------+

Structure Definition in C:

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

Why Use a Doubly Linked List?

  • Can be traversed in both directions.
  • Deletion of a given node pointer is $O(1)$ because you can access node->prev directly without traversing from head.
  • Drawback: Requires extra memory for the prev pointer per node and extra pointer assignments during insertion/deletion.

6. Circular Linked List (CLL)

In a Circular Linked List, the last node does not point to NULL. Instead, it stores the address of the HEAD node, creating an infinite traversable loop.

       +---------------------------------------------+
       |                                             |
       v                                             |
+------+------+     +------+------+     +------+-----+
| Data | Next | --> | Data | Next | --> | Data | Next |
|  10  | 2000 |     |  20  | 3000 |     |  30  | 1000 |
+------+------+     +------+------+     +------+------+

Key Application:

  • Used in Operating System round-robin CPU schedulers to cycle through running processes in a continuous time-slice loop.

Frequently Asked Questions (FAQ)

Q1: What is a Self-Referential Structure?

A self-referential structure is a struct in C that contains a pointer member of its own structure type (struct Node *next). It is essential for creating dynamic nodes in linked lists, trees, and graphs.

Q2: Why do we pass a double pointer struct Node **head into insertion functions?

When an insertion modifies the head pointer itself (e.g., adding at the beginning), C passes pointers by value. To change the original head pointer stored in main(), we must pass its memory address (&head), which requires a double pointer parameter (struct Node **head).

LEAVE A REPLY

Please enter your comment!
Please enter your name here