Linked List in C

A Linked List is a linear dynamic data structure where elements (called nodes) are not stored in contiguous memory locations. Each node contains data and a pointer (link) to the next node.

Unlike arrays, linked lists can grow or shrink easily at runtime and do not require contiguous memory allocation.

• Dynamic size
• No random access (O(n) time)
• Efficient insertion/deletion (O(1) if position known)
• Extra memory for pointers

1. Self-Referential Structure for Linked List Node

              
C

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

Note: Most common & recommended way using typedef

2. Core Operations of Singly Linked List

Operation	Time Complexity	Description
Create/Insert at Beginning	O(1)	Fastest insertion
Insert at End	O(n) / O(1) with tail	Common when no tail pointer
Insert at Position	O(n)	Need to traverse
Delete from Beginning	O(1)	Very fast
Delete from End	O(n)	Need previous node
Delete by Value	O(n)	Search + delete
Traverse/Print	O(n)	Linear traversal
Search	O(n)	No random access
Reverse	O(n)	Iterative or Recursive

3. Complete Singly Linked List Implementation

              
            
C

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

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

// Function prototypes
Node* createNode(int data);
void insertAtBeginning(Node** head, int data);
void insertAtEnd(Node** head, int data);
void deleteNode(Node** head, int key);
void printList(Node* head);
void freeList(Node** head);

int main() {
    Node* head = NULL;

    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtEnd(&head, 40);
    insertAtBeginning(&head, 10);

    printf("Original List: ");
    printList(head);

    deleteNode(&head, 20);
    printf("After deleting 20: ");
    printList(head);

    freeList(&head);
    return 0;
}

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

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

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;
}

void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* 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);
}

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

void freeList(Node** head) {
    Node* current = *head;
    Node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}
          

4. Array vs Linked List - Quick Comparison

Feature	Array	Linked List
Memory Allocation	Contiguous	Non-contiguous
Size	Fixed (static)	Dynamic
Access Element	O(1)	O(n)
Insert/Delete at Beginning	O(n)	O(1)
Insert/Delete at End	O(1) (if dynamic)	O(n) without tail
Extra Memory	No	Yes (pointers)

5. Next Steps / Advanced Topics

Doubly Linked List
Circular Linked List
Circular Doubly Linked List
Reverse a Linked List (Iterative + Recursive)
Find middle of Linked List (Fast-Slow pointer)
Detect Loop (Floyd’s Cycle Detection)
Merge two sorted Linked Lists
Polynomial representation using Linked List