Linked List in C (Singly, Doubly, Circular) with Complete Examples

This tutorial explains Linked Lists in C, a dynamic data structure used to store data efficiently. It covers Singly, Doubly, and Circular Linked Lists, along with insertion, deletion, traversal, and practical examples to strengthen problem-solving skills.

1. What is a Linked List

  1. A linked list is a linear data structure where elements (nodes) are connected using pointers
  2. Unlike arrays, memory is allocated dynamically and elements are not stored contiguously
  3. Each node contains:
  4. Data
  5. Pointer to the next node (and previous node in doubly linked list)

2. Singly Linked List

  1. Each node points to the next node
  2. Last node points to NULL

Node structure:


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

Example: Create and Traverse Singly Linked List


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

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

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

// Allocate memory
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));

// Assign data
head->data = 10; head->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = NULL;

// Traverse
struct Node *ptr = head;
while(ptr != NULL) {
printf("%d -> ", ptr->data);
ptr = ptr->next;
}
printf("NULL\n");
return 0;
}

Output:


10 -> 20 -> 30 -> NULL

3. Doubly Linked List

  1. Each node has two pointers:
  2. next → points to next node
  3. prev → points to previous node

Node structure:


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

Example: Create and Traverse Doubly Linked List


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

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

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

head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));

head->data = 10; head->prev = NULL; head->next = second;
second->data = 20; second->prev = head; second->next = NULL;

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

return 0;
}

Output:


10 -> 20 -> NULL

4. Circular Linked List

  1. Last node points back to the head
  2. Can be singly or doubly circular

Singly Circular Example:


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

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

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

head->data = 10; head->next = second;
second->data = 20; second->next = third;
third->data = 30; third->next = head; // circular

// Traverse (stop after one full circle)
struct Node *ptr = head;
int count = 0;
do {
printf("%d -> ", ptr->data);
ptr = ptr->next;
count++;
} while(ptr != head && count < 10);
printf("(back to head)\n");

return 0;
}

Output:


10 -> 20 -> 30 -> (back to head)

5. Key Points to Remember

  1. Singly: simple, one-direction traversal, less memory
  2. Doubly: two-way traversal, extra memory for prev pointer
  3. Circular: last node points back to first node, useful for circular queues or round-robin scheduling
  4. Linked lists are dynamic, no fixed size, unlike arrays
  5. Common operations: insertion, deletion, traversal, search