Linked List in C - Singly, Doubly, Circular

Linked List Basics

A linked list is a linear data structure where elements are stored in nodes, and each node contains data and a pointer to the next node.

Types of Linked Lists

Singly Linked List - Each node points to next node
Doubly Linked List - Each node points to next and previous
Circular Linked List - Last node points to first

Singly Linked List:
[Data|Next] --> [Data|Next] --> [Data|Next] --> NULL

Singly Linked List

singly_linked_list.c

#include 
#include 

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

// Create new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert at beginning
void insertAtBeginning(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// Insert at end
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
}

// Delete node
void deleteNode(Node** head, int key) {
    Node* temp = *head, *prev = NULL;
    
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) return;
    
    prev->next = temp->next;
    free(temp);
}

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

int main() {
    Node* head = NULL;
    
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtBeginning(&head, 5);
    
    printf("Linked List: ");
    printList(head);
    
    deleteNode(&head, 20);
    printf("After deleting 20: ");
    printList(head);
    
    return 0;
}

Complexity Analysis

Operation	Time Complexity	Space Complexity
Insert at beginning	O(1)	O(1)
Insert at end	O(n)	O(1)
Delete	O(n)	O(1)
Search	O(n)	O(1)

Doubly Linked List

doubly_linked_list.c

#include 
#include 

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

// Create new node
DNode* createDNode(int data) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Insert at beginning
void insertAtBeginning(DNode** head, int data) {
    DNode* newNode = createDNode(data);
    newNode->next = *head;
    if (*head != NULL)
        (*head)->prev = newNode;
    *head = newNode;
}

// Print forward
void printForward(DNode* head) {
    printf("Forward: ");
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Print backward
void printBackward(DNode* head) {
    if (head == NULL) return;
    while (head->next != NULL)
        head = head->next;
    
    printf("Backward: ");
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->prev;
    }
    printf("\n");
}

int main() {
    DNode* head = NULL;
    
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
    
    printForward(head);
    printBackward(head);
    
    return 0;
}

Circular Linked List

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

Circular Linked List:
[Data|Next] --> [Data|Next] --> [Data|Next] --+
      ^                                        |
      +----------------------------------------+