C Linked Lists

What is a Linked List?

A linked list is a dynamic data structure where each element (called a node) contains data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory — nodes can be scattered anywhere in the heap.

Feature	Array	Linked List
Memory	Contiguous, fixed size	Dynamic, scattered
Access by index	O(1) — direct	O(n) — traverse
Insert at beginning	O(n) — shift elements	O(1)
Insert at end	O(1) (if space)	O(n) or O(1) with tail pointer
Delete	O(n) — shift elements	O(1) with pointer to node
Memory overhead	None	Extra pointer per node

Singly Linked List

Each node has data and a next pointer. The last node's next is NULL.

Singly Linked List — Full Implementation

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

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

// Create a new node
Node* createNode(int data) {
    Node *node = (Node*)malloc(sizeof(Node));
    if (!node) { perror("malloc"); exit(1); }
    node->data = data;
    node->next = NULL;
    return node;
}

// Insert at beginning — O(1)
Node* insertFront(Node *head, int data) {
    Node *node = createNode(data);
    node->next = head;
    return node;  // new head
}

// Insert at end — O(n)
Node* insertEnd(Node *head, int data) {
    Node *node = createNode(data);
    if (!head) return node;
    Node *curr = head;
    while (curr->next) curr = curr->next;
    curr->next = node;
    return head;
}

// Delete a node by value — O(n)
Node* deleteNode(Node *head, int data) {
    if (!head) return NULL;
    if (head->data == data) {
        Node *temp = head->next;
        free(head);
        return temp;
    }
    Node *curr = head;
    while (curr->next && curr->next->data != data)
        curr = curr->next;
    if (curr->next) {
        Node *temp = curr->next;
        curr->next = temp->next;
        free(temp);
    }
    return head;
}

// Search — O(n)
int search(Node *head, int data) {
    int pos = 0;
    while (head) {
        if (head->data == data) return pos;
        head = head->next;
        pos++;
    }
    return -1;
}

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

// Free all nodes
void freeList(Node *head) {
    while (head) {
        Node *temp = head;
        head = head->next;
        free(temp);
    }
}

int main() {
    Node *head = NULL;

    head = insertEnd(head, 10);
    head = insertEnd(head, 20);
    head = insertEnd(head, 30);
    head = insertFront(head, 5);

    printf("List: "); printList(head);
    // 5 -> 10 -> 20 -> 30 -> NULL

    head = deleteNode(head, 20);
    printf("After deleting 20: "); printList(head);
    // 5 -> 10 -> 30 -> NULL

    printf("Search 30: position %d\n", search(head, 30));  // 2
    printf("Search 99: position %d\n", search(head, 99));  // -1

    freeList(head);
    return 0;
}

Doubly Linked List

Each node has both a next and a prev pointer. This allows traversal in both directions and O(1) deletion when you have a pointer to the node.

Doubly Linked List

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

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

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

DNode* insertFront(DNode *head, int data) {
    DNode *node = createDNode(data);
    if (head) {
        node->next = head;
        head->prev = node;
    }
    return node;
}

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

    printf("Backward: ");
    while (tail) {
        printf("%d ", tail->data);
        tail = tail->prev;
    }
    printf("\n");
}

int main() {
    DNode *head = NULL;
    head = insertFront(head, 30);
    head = insertFront(head, 20);
    head = insertFront(head, 10);

    printForward(head);
    // Forward:  10 20 30
    // Backward: 30 20 10

    return 0;
}

Reverse a Linked List

Reverse a Singly Linked List

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

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

Node* reverse(Node *head) {
    Node *prev = NULL;
    Node *curr = head;
    while (curr) {
        Node *next = curr->next;  // save next
        curr->next = prev;        // reverse link
        prev = curr;              // move prev forward
        curr = next;              // move curr forward
    }
    return prev;  // new head
}

// helper: build list from array
Node* buildList(int arr[], int n) {
    Node *head = NULL, *tail = NULL;
    for (int i = 0; i < n; i++) {
        Node *node = malloc(sizeof(Node));
        node->data = arr[i]; node->next = NULL;
        if (!head) head = tail = node;
        else { tail->next = node; tail = node; }
    }
    return head;
}

void printList(Node *h) {
    while (h) { printf("%d%s", h->data, h->next ? " -> " : "\n"); h = h->next; }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    Node *head = buildList(arr, 5);
    printf("Original: "); printList(head);
    head = reverse(head);
    printf("Reversed: "); printList(head);
    return 0;
}
// Original: 1 -> 2 -> 3 -> 4 -> 5
// Reversed: 5 -> 4 -> 3 -> 2 -> 1

Previous Next

C Linked Lists

What is a Linked List?

Singly Linked List

Doubly Linked List

Reverse a Linked List

Ready to Level Up Your Skills?