C Programming

Module 7· 6 min read· 10 Questions·completed

7. Canonical Algorithms & Idioms in C

Pointer-to-pointer linked lists (Linus idiom), generic qsort comparators with overflow guards, generic swap with memcpy, dynamic vector doubling, and Floyd's cycle detection

GATE CS & UGC NET JRF Core Subject Exam Weightage: 3–4 Questions analyzing algorithm tracing in C, double-pointer linked list mutations, custom comparator return rules in qsort, and pointer rewiring without memory leaks.

1. Technical Jargon & The Idiomatic C Mindset#

Implementing algorithms in C requires direct control over memory layout, pointer indirection, and byte-level manipulation.

  1. Pointer-to-Pointer (T**): A pointer that stores the address of another pointer variable. Used to modify caller pointer references (such as a list head pointer) without return statements.
  2. Generic Comparator: A function pointer matching int (*)(const void *, const void *) that returns negative, zero, or positive to dictate relative ordering.
  3. Amortized Analysis: Averaging the running time per operation over a sequence of operations (e.g., dynamic array doubling gives O(1)O(1) amortized insertion despite occasional O(n)O(n) reallocations).
  4. Sentinel Node: A dummy head/tail node used to simplify boundary conditions by ensuring every real element has a predecessor and successor.
  5. In-Place Mutation: Modifying data structures directly within their existing memory without allocating auxiliary buffers (O(1)O(1) auxiliary space).

2. Idiom 1: Pointer-to-Pointer (Node**) for Linked Lists#

In traditional beginner code, inserting or deleting the head of a linked list requires a special if (head == NULL) or if (prev == NULL) check.

Linus Torvalds famously highlighted the Pointer-to-Pointer Idiom as the mark of "good taste" in C programming:

Diagram / Text
Traditional with Special Case:
To delete node 'curr':
if (curr == *head) {
    *head = curr->next;
} else {
    prev->next = curr->next;
}

Idiomatic with Pointer-to-Pointer:
'indirect' points directly to the pointer that points to 'curr'!
Whether 'curr' is the head or in the middle, the update is IDENTICAL:
*indirect = curr->next;

2.1 Elegant Sorted Insertion in C#

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

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

// Zero special cases! Works identically whether inserting at head, middle, or tail.
void insert_sorted(struct Node **head_ref, int new_val) {
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->val = new_val;

    // 'indirect' points to the pointer leading to the next node
    struct Node **indirect = head_ref;

    while (*indirect != NULL && (*indirect)->val < new_val) {
        indirect = &((*indirect)->next);
    }

    new_node->next = *indirect;
    *indirect = new_node;
}

3. Idiom 2: Generic Type-Agnostic Swap with memcpy#

How do you implement a single swap function in C that works for integers, doubles, strings, and custom structures?

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

void generic_swap(void *a, void *b, size_t size) {
    // Allocate small stack buffer for typical primitive copies
    unsigned char temp[256];
    void *buf = (size <= sizeof(temp)) ? temp : malloc(size);

    if (!buf) return; // Allocation guard

    memcpy(buf, a, size);
    memcpy(a, b, size);
    memcpy(b, buf, size);

    if (buf != temp) {
        free(buf);
    }
}

4. Idiom 3: qsort & The Integer Subtraction Overflow Trap#

The C Standard Library provides qsort in <stdlib.h>:

C
void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

4.1 Comparator Contract:#

  • Return <0< 0 if first element should precede second element.
  • Return 00 if both elements are equivalent.
  • Return >0> 0 if first element should follow second element.

4.2 The Dangerous Subtraction Trap in GATE:#

C
// THE DANGEROUS WAY (Common GATE Trap):
int cmp_bad(const void *a, const void *b) {
    return (*(int *)a - *(int *)b); // BUG: INTEGER OVERFLOW!
    // If *a is INT_MAX (2,147,483,647) and *b is -1:
    // INT_MAX - (-1) overflows signed int into NEGATIVE value!
    // Result: qsort incorrectly sorts positive numbers as smaller than negative!
}

// THE SAFE DEFENSIVE WAY:
int cmp_safe(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

5. Idiom 4: Dynamic Resizing Array (Vector) in Pure C#

Implementing a growable dynamic array in C with O(1)O(1) amortized insertion:

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

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} Vector;

Vector* vector_create(size_t initial_cap) {
    Vector *v = (Vector *)malloc(sizeof(Vector));
    if (!v) return NULL;
    v->size = 0;
    v->capacity = initial_cap ? initial_cap : 4;
    v->data = (int *)malloc(v->capacity * sizeof(int));
    if (!v->data) {
        free(v);
        return NULL;
    }
    return v;
}

void vector_push_back(Vector *v, int val) {
    if (v->size == v->capacity) {
        // Amortized doubling strategy:
        size_t new_cap = v->capacity * 2;
        int *new_data = (int *)realloc(v->data, new_cap * sizeof(int));
        if (!new_data) return; // Allocation failure
        v->data = new_data;
        v->capacity = new_cap;
    }
    v->data[v->size++] = val;
}

void vector_destroy(Vector *v) {
    if (v) {
        free(v->data);
        free(v);
    }
}

6. Idiom 5: Floyd's Cycle Detection (Tortoise & Hare) in C#

Given a linked list, detect whether it contains a cycle and locate the cycle's starting node in O(n)O(n) time and O(1)O(1) auxiliary space:

C
#include <stdbool.h>

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

bool has_cycle(struct Node *head) {
    struct Node *slow = head;
    struct Node *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;          // 1 step
        fast = fast->next->next;    // 2 steps

        if (slow == fast) {
            return true; // Cycle detected!
        }
    }
    return false; // Reached end of linear list
}

Mathematical Proof: Why They Meet#

Let kk be the distance from head to cycle entrance, LL be the cycle loop length, and mm be the distance from entrance to meeting point:

  • Distance traveled by slow: Dslow=k+mD_{\text{slow}} = k + m
  • Distance traveled by fast: Dfast=2(k+m)D_{\text{fast}} = 2(k + m)
  • Since fast is ahead by an integer number of loops nLnL: 2(k+m)−(k+m)=nL  ⟹  k+m=nL  ⟹  k=nL−m2(k + m) - (k + m) = nL \implies k + m = nL \implies k = nL - m
  • Corollary: If one pointer resets to head and both advance at speed 1, they meet precisely at the cycle entrance!

7. Best Practices & Production Standards in C#

  1. Always Match Function Signatures for qsort Exactly: Cast parameters inside the comparator body, not in the comparator function header.
  2. Guard Free Pointers: Set pointers to NULL immediately after freeing to prevent use-after-free bugs.
  3. Use size_t for Counts and Offsets: Never use signed int for memory buffer sizes, loop indices on arrays, or allocation byte counts.

Practice Quiz

Test your understanding with step-by-step solutions

Practice Quiz

10 questions · 90s per question

Each question has a 90-second time limit. Unanswered questions will be auto-submitted when time runs out.