Singly and Doubly Linked Lists in C Using Pointers

Linked lists are linear data structures where elements, called nodes, are allocated dynamically on the heap and linked together using memory pointers. Unlike arrays, linked lists do not store elements in contiguous memory locations, allowing for efficient insertions and deletions without reallocation. This article demonstrates how to implement both singly linked lists (unidirectional traversal) and doubly linked lists (bidirectional traversal) from scratch in C, covering structure design, node allocation, insertion, traversal, and memory cleanup.

Singly Linked List Implementation

A singly linked list consists of nodes containing a data payload and a single pointer pointing to the next node in the sequence. The final node points to NULL, marking the end of the list.

1. Defining the Node Structure

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

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

2. Creating and Inserting Nodes

To add an element to the front of a singly linked list, allocate memory using malloc, assign the data, set the new node's next pointer to the current head, and update the head pointer.

void insertAtHead(Node** headRef, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        perror("Allocation failed");
        return;
    }
    newNode->data = value;
    newNode->next = *headRef;
    *headRef = newNode;
}

3. Traversal and Memory Deallocation

Traversing the list requires moving a pointer from the head node until reaching NULL. Because nodes are allocated on the heap, every node must be explicitly freed to prevent memory leaks.

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

void freeList(Node** headRef) {
    Node* current = *headRef;
    Node* nextNode = NULL;

    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    *headRef = NULL;
}

Doubly Linked List Implementation

A doubly linked list expands upon the singly linked list by including two pointers per node: one referencing the next node and another referencing the previous node. This allows traversal in both forward and backward directions.

1. Defining the Doubly Linked Node Structure

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

2. Insertion at the Front

When inserting at the beginning of a doubly linked list, both the next and prev pointers must be maintained to keep the bidirectional link intact.

void insertDNodeHead(DNode** headRef, int value) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    if (newNode == NULL) {
        perror("Allocation failed");
        return;
    }
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = *headRef;

    if (*headRef != NULL) {
        (*headRef)->prev = newNode;
    }

    *headRef = newNode;
}

3. Traversal and Deallocation

A doubly linked list can be traversed forward like a singly linked list, or backward if starting from the tail.

void printDListForward(DNode* head) {
    DNode* current = head;
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void freeDList(DNode** headRef) {
    DNode* current = *headRef;
    DNode* nextNode = NULL;

    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    *headRef = NULL;
}

Pointer Mechanics and Trade-offs

• Pointer Overhead: Singly linked lists require one pointer (sizeof(void*), typically 8 bytes on modern 64-bit systems) per node, making them more memory-efficient. Doubly linked lists require two pointers (16 bytes) per node.
• Deletion Complexity: Deleting a specific node in a singly linked list requires a pointer to the preceding node to update links. In a doubly linked list, a node can be unlinked directly using its own prev and next pointers.
• Bidirectional Movement: Doubly linked lists simplify operations requiring reverse traversal (such as navigating history buffers), while singly linked lists can only traverse forward from the head.