Data Structures and Algorithms in C (DSA)

📘 Linked Lists (Singly, Circular, Doubly)

A linked list is a dynamic data structure used to store a sequence of elements where each element (called a node) points to the next. Unlike arrays, linked lists do not require contiguous memory and can grow or shrink at runtime.

🧱 Basic Structure of a Node

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

🔗 Singly Linked List

Each node stores data and a pointer to the next node. The last node points to NULL.

// Creating nodes and linking
struct Node* head = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = NULL;
  

➡️ Traversing a Singly Linked List

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL");
}
  

🔁 Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circle.

• No NULL in the list
• Useful for cyclic operations, e.g., round-robin scheduling

🔄 Doubly Linked List

Each node contains two pointers — one to the next node and one to the previous node.

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

• Allows traversal in both directions
• More memory usage due to extra pointer

🔍 Use Cases of Linked Lists

• Dynamic memory allocation without fixed size
• Insertion/deletion without shifting elements
• Implementation of stacks, queues, graphs, adjacency lists

🧪 Example: Insert at Beginning (Singly)

void insertAtBeginning(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}
  

📚 Practice Tasks

• Create a singly linked list and print it
• Write functions to insert and delete nodes from beginning and end
• Convert singly linked list to circular
• Implement a doubly linked list with backward traversal

✅ Summary

• Linked lists are dynamic and flexible
• Singly → forward only, Circular → circular connection, Doubly → bidirectional
• Used for dynamic data management, memory-efficient operations

📤 Coming Next

In the next chapter, we’ll learn how to implement Stack in C using both Arrays and Linked Lists.