C Programming Data Structures Singly Doubly And Circular Linked Lists Complete Guide

Last Update:2025-06-23T00:00:00 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION. 12 mins read Difficulty-Level: beginner

Understanding the Core Concepts of C Programming data structures Singly, Doubly, and Circular Linked Lists

C Programming Data Structures: Singly, Doubly, and Circular Linked Lists

Singly Linked List

A Singly Linked List is the simplest form of a linked list. In this structure, each node contains data fields and a reference (or link) to the next node in the sequence. This means traversal can only be done in one direction, from the head (first node) to the tail (last node).

Structure:

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

Data: The value stored in the node.
Next: A pointer to the next node in the list. The last node's next pointer is NULL.

Operations:

Insertion:
- At the beginning.
- At the end.
- At a specific position.
Deletion:
- From the beginning.
- From the end.
- From a specific position.
Search: Locate a node containing a specific value.

Advantages:

Easy to implement.
Insertion and deletion are efficient, especially at the beginning.

Disadvantages:

Traversal is unidirectional.
Deletion and insertion at arbitrary positions are inefficient compared to arrays.

Applications:

Implementing stacks (using head node as top).
Implementing queues (using pointers to both head and tail).
Memory management in operating systems.

Doubly Linked List

A Doubly Linked List enhances the singly linked list by adding a pointer to the previous node in each node. This bidirectional capability allows traversal in both directions—forward from the head to the tail and backward from the tail to the head.

Structure:

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

Data: The value stored in the node.
Prev: A pointer to the previous node.
Next: A pointer to the next node.

Operations:

Insertion:
- At the beginning.
- At the end.
- At a specific position.
Deletion:
- From the beginning.
- From the end.
- From a specific position.
Search: Locate a node containing a specific value.

Advantages:

Traversal is bidirectional.
Insertion and deletion are more efficient at arbitrary positions due to the prev pointer.
Easier to implement structures like a doubly ended queue (deque).

Disadvantages:

Requires additional memory for the prev pointer.
More complex implementation compared to singly linked lists.

Applications:

Implementing deques.
Implementing hash tables due to ability to handle collisions efficiently with double linking.
Graph traversal algorithms like DFS and BFS.

Circular Linked List

A Circular Linked List is a variation where the last node points back to the first node, forming a circular chain. This structure can be either singly or doubly linked. The circular nature allows for more efficient looping through the list without using NULL pointer checks at the end.

Structure (Singly Circular):

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

Data: The value stored in the node.
Next: A pointer to the next node. The last node points to the head node.

Operations:

Insertion:
- At the beginning.
- At the end.
- At a specific position.
Deletion:
- From the beginning.
- From the end.
- From a specific position.
Search: Locate a node containing a specific value.

Advantages:

No NULL pointer at the end, simplifying circular loop logic.
Efficiently traversing nodes without needing special termination conditions.
Useful for implementing structures needing circular behavior.

Disadvantages:

Slightly more complex implementations for insertion and deletion.
Additional consideration for edge cases like the empty list.

Applications:

Implementing round-robin scheduling algorithms.
Circular queues.
Multiplayer games and simulations requiring a circular progression of players or processes.

Important Information:

Node Management: Proper memory management is crucial in linked lists to prevent memory leaks. Use malloc to allocate memory for new nodes and free to deallocate memory when nodes are removed.
Time Complexity: Basic operations like insertion, deletion, and search have different time complexities depending on the type of linked list. Average time for search in a linked list is (O(n)).
Memory Overhead: Each node in a doubly linked list requires additional memory for the prev pointer, which can be significant depending on the number of nodes.

Online Code run

🔔 Note: Select your programming language to check or run code at

💻 Run Code Compiler

Step-by-Step Guide: How to Implement C Programming data structures Singly, Doubly, and Circular Linked Lists

Singly Linked List

Step 1: Define the Node Structure

The node in a singly linked list contains a data field and a pointer to the next node.

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

// Define the structure for a Node in a singly linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new Node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Step 2: Insert Nodes into the List

Nodes can be inserted at the beginning, in the middle, or at the end of the list.

// Function to insert a Node at the beginning
void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head)
        newNode->next = *head;
    *head = newNode;
}

// Function to insert a Node at the end
void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
}

// Function to insert after a given Node
void insertAfterNode(struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }

    struct Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

Step 3: Delete Nodes from the List

Nodes can be deleted based on their position or value.

// Function to delete the first Node
void deleteFirstNode(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

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

// Function to delete the last Node
void deleteLastNode(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = *head;
    struct Node* prev;

    if (temp->next == NULL) {
        *head = NULL;
    } else {
        while (temp->next != NULL) {
            prev = temp;
            temp = temp->next;
        }
        prev->next = NULL;
    }
    free(temp);
}

// Function to delete a Node by value
void deleteNodeByValue(struct Node** head, int value) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* temp = *head;
    struct Node* prev = NULL;

    // If the Data is at Head
    if (temp->data == value) {
        *head = temp->next;
        free(temp);
        return;
    }

    // Traversing the List for the Data
    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }

    // If the Data is not in the List
    if (temp == NULL) {
        printf("Value %d not found\n", value);
        return;
    }

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

Step 4: Display the List

Function to print all elements in the singly linked list.

// Function to display the List
void displayList(struct Node* head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Main function to test the operations
int main() {
    struct Node* head = NULL;

    // Insert nodes at the beginning
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 10);

    // Display list
    printf("Initial List:\n");
    displayList(head);

    // Insert node at the end
    insertAtEnd(&head, 15);

    // Display list
    printf("List after inserting 15 at the end:\n");
    displayList(head);

    // Insert node after a specific node
    insertAfterNode(head->next, 20); // after second element

    // Display list
    printf("List after inserting 20 after the second element:\n");
    displayList(head);

    // Deleting a node by value
    deleteNodeByValue(&head, 10);

    // Display list
    printf("List after deleting value 10:\n");
    displayList(head);

    // Deleting first and last node
    deleteFirstNode(&head);
    deleteLastNode(&head);

    // Display list
    printf("List after deleting first and last node:\n");
    displayList(head);

    return 0;
}

Doubly Linked List

Step 1: Define the Node Structure

In a doubly linked list, each node contains a data field and pointers to both the next and previous nodes.

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

// Define the structure for a Node in a doubly linked list
struct DoublyNode {
    int data;
    struct DoublyNode* next;
    struct DoublyNode* prev;
};

// Function to create a new Node
struct DoublyNode* createDoublyNode(int data) {
    struct DoublyNode* newNode = (struct DoublyNode*)malloc(sizeof(struct DoublyNode));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

Step 2: Insert Nodes

Insert nodes at the beginning, end, and after a specific node.

// Function to insert a Node at the beginning
void insertAtDoublyBeginning(struct DoublyNode** head, int data) {
    struct DoublyNode* newNode = createDoublyNode(data);
    newNode->next = *head;

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

    *head = newNode;
}

// Function to insert a Node at the end
void insertAtDoublyEnd(struct DoublyNode** head, int data) {
    struct DoublyNode* newNode = createDoublyNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct DoublyNode* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;

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

// Function to insert a Node after a specific Node
void insertAfterDoublyNode(struct DoublyNode* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }

    struct DoublyNode* newNode = createDoublyNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
    newNode->prev = prevNode;

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

Step 3: Delete Nodes

Delete nodes from any position in the list.

// Function to delete a Node by value
void deleteDoublyNodeByValue(struct DoublyNode** head, int value) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct DoublyNode* temp = *head;

    // Find the Node with the specified value
    while (temp->data != value && temp->next != NULL)
        temp = temp->next;

    // If the Node is not found
    if (temp->data != value) {
        printf("Value %d not found\n", value);
        return;
    }

    // If the Node is the head
    if (temp->prev == NULL)
        *head = temp->next;
    else
        temp->prev->next = temp->next;

    // If the Node is not the last Node
    if (temp->next != NULL)
        temp->next->prev = temp->prev;

    free(temp);
}

Step 4: Display the List

Display the doubly linked list in both forward and backward directions.

// Function to display the List in forward direction
void displayDoublyForward(struct DoublyNode* head) {
    while (head) {
        printf("%d <-> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Function to display the List in reverse direction
void displayDoublyBackward(struct DoublyNode* tail) {
    while (tail) {
        printf("%d <-> ", tail->data);
        tail = tail->prev;
    }
    printf("NULL\n");
}

// Main function to test the operations
int main() {
    struct DoublyNode* head = NULL;

    // Insert nodes at the beginning
    insertAtDoublyBeginning(&head, 10);
    insertAtDoublyBeginning(&head, 20);

    // Insert node at the end
    insertAtDoublyEnd(&head, 30);

    // Insert node after a specific node
    insertAfterDoublyNode(head->next, 40); // after second element

    // Display list in forward and reverse directions
    printf("List in forward order:\n");
    displayDoublyForward(head);

    struct DoublyNode* tail = head;
    while (tail->next != NULL)
        tail = tail->next;

    printf("List in reverse order:\n");
    displayDoublyBackward(tail);

    // Deleting a node by value
    deleteDoublyNodeByValue(&head, 20);

    // Display list
    printf("List after deleting value 20:\n");
    displayDoublyForward(head);

    return 0;
}

Circular Linked List

Step 1: Define the Node Structure

Here, each node contains a data field and a pointer to the next node, but the last node points back to the head node.

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

// Define the structure for a Node in a circular linked list
struct CircularNode {
    int data;
    struct CircularNode* next;
};

// Function to create a new Node
struct CircularNode* createCircularNode(int data) {
    struct CircularNode* newNode = (struct CircularNode*)malloc(sizeof(struct CircularNode));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Step 2: Insert Nodes

Insert nodes at the beginning or end of the list.

// Function to insert a Node at the beginning
void insertAtCircularBeginning(struct CircularNode** head, int data) {
    struct CircularNode* newNode = createCircularNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = *head;
        return;
    }
    
    struct CircularNode* temp = *head;
    while (temp->next != *head)
        temp = temp->next;

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

// Function to insert a Node at the end
void insertAtCircularEnd(struct CircularNode** head, int data) {
    struct CircularNode* newNode = createCircularNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = *head;
        return;
    }

    struct CircularNode* temp = *head;
    while (temp->next != *head)
        temp = temp->next;

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

Step 3: Delete Nodes

Handle deletion of nodes in a circular linked list.

// Function to delete a Node by value
void deleteCircularNodeByValue(struct CircularNode** head, int value) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct CircularNode* current = *head, * prev = NULL;
    
    if ((current->next == *head) && (current->data == value)) { // Only one node in the list
        free(current);
        *head = NULL;
        return;
    }

    // Check if it's the head node
    if (current->data == value) {
        // Find the last node
        while (current->next != *head)
            current = current->next;

        current->next = (*head)->next;
        free(*head);
        *head = current->next;
        return;
    }

    // Traverse the list for the value
    while ((current->next)->data != value && current->next != *head)
        current = current->next;

    // If value was not found in the list
    if ((current->next)->data != value) {
        printf("Value %d not found\n", value);
        return;
    }

    // Unlink the node to be deleted
    prev = current->next;
    current->next = prev->next;
    free(prev);
}

Step 4: Display the List

Display the circular linked list.

C Programming Data Structures Singly Doubly And Circular Linked Lists Complete Guide