Offensive Security Researcher & Quantum Cryptography Analyst

Elementary Data Structures: Implementing Pointers and Objects in C

Abdul Wahab Junaid
Elementary Data Structures: Implementing Pointers and Objects in C

Whenever I write data structures in C, I’m reminded that C doesn’t give me objects, references, or garbage collection out of the box the way languages like Java or Python do. Instead, I have to build the notion of “an object with fields, connected to other objects” myself, using structs and raw pointers, and I have to manage memory for those objects by hand. This topic is about exactly that: how I represent linked, object-like data using pointers in C, and — just as interestingly — how I could represent the same ideas without pointers at all, using plain arrays, in languages or environments where pointers aren’t available.

I find this a genuinely important topic because it’s the foundation underneath every linked list, tree, and graph structure I ever build in C. Understanding it well means I understand exactly what a “pointer-based object” costs in memory and time, and it also demystifies how higher-level languages implement their own object references under the hood.

History and Background

Pointers as a language-level concept trace back to early systems programming languages, most notably BCPL (developed by Martin Richards in 1966) and B (developed by Ken Thompson at Bell Labs around 1969), both direct ancestors of C. Dennis Ritchie developed C at Bell Labs in the early 1970s, refining pointer syntax and semantics into the form still recognizable today, with explicit pointer types tied to the type of data they referenced — a meaningful improvement over B’s untyped approach.

The idea of representing objects and pointer-based structures using plain arrays — sometimes called the “multiple-array” or “single-array” representation — predates widespread pointer support in early programming environments and assembly-level programming, where explicit memory addresses had to be simulated using array indices when a language or platform didn’t expose direct pointer arithmetic. This technique is still taught today, notably in Cormen, Leiserson, Rivest, and Stein’s “Introduction to Algorithms,” as a way of illustrating that “a pointer is really just an index,” a conceptual link that helps me understand pointers more deeply rather than treating them as pure magic.

Problem Statement

I want to represent structured, linked objects in memory — such as the nodes of a linked list or tree, each containing several fields and one or more references to other objects — using the low-level tools C actually gives me: structs, pointers, and manual memory allocation. I also want to understand the alternative technique of representing the same kind of linked structure using plain arrays and integer indices, for situations where true pointers aren’t available, aren’t desired (e.g., for serialization), or where I want tighter control over memory layout.

Core Concepts

How It Works

In C, I define a struct for my object type, listing its fields, including pointer fields that reference other objects of the same (or different) struct type. To create a new object, I call malloc to allocate enough memory to hold one instance of the struct, and I get back a pointer to that memory, which I then use to set the object’s fields, including linking it to other objects by assigning their addresses to my pointer fields.

For the array-based alternative, I instead pre-allocate one or more arrays, each large enough to hold up to $n$ objects’ worth of a particular field. Object number $i$’s data for a given field lives at index $i$ of that field’s array. A “pointer” in this scheme is simply an integer — the index of the referenced object — and NULL is typically represented by a reserved sentinel index, like $-1$ or $0$ (depending on convention), that can never be a valid object index.

To manage which array slots are currently “allocated” versus “free” in the array-based scheme, I maintain a free list: I link together all currently unused slots using one of the array’s own fields (commonly reusing the next field for this purpose), and I keep a single variable, free, pointing to (indexing) the head of this list. Allocating a new object means popping the head of the free list; freeing an object means pushing its index back onto the free list.

Working Principle

The pointer-based approach in C directly leverages the hardware’s ability to address memory arbitrarily: a pointer is, physically, just a memory address, and dereferencing it is a hardware-supported operation that the CPU executes essentially at the same speed regardless of where in memory the target object lives. This gives me flexible, dynamically-growable structures without needing to predict the maximum number of objects I’ll ever need.

The array-based approach, by contrast, works by pre-committing to a maximum capacity $n$ up front, in exchange for a very compact and predictable memory layout — all data lives within known array bounds, which can be advantageous for cache locality, serialization (writing the whole structure to disk as a flat block), or environments without dynamic memory allocation. The free list is what allows this approach to still support object creation and deletion efficiently, in $O(1)$ time, despite not having a general-purpose memory allocator behind it — it’s essentially a hand-rolled, specialized allocator restricted to fixed-size objects.

Mathematical Foundation

Space overhead of pointer-based objects. Each struct instance requires space for its declared fields plus, on most platforms, potential padding/alignment overhead imposed by the compiler for performance reasons. If a struct has $f$ fields with total declared size $S$ bytes, actual allocated size $S’$ often satisfies:

$$ S’ \ge S $$

due to alignment padding, and each malloc call typically carries additional hidden bookkeeping overhead $O_{malloc}$ used by the memory allocator itself, so the true per-object cost is:

$$ \text{Cost per object} = S’ + O_{malloc} $$

Space of the array-based (multiple-array) representation. For $n$ objects with $f$ fields each of size $s_1, s_2, \dots, s_f$ bytes, the total space is simply:

$$ \text{Total space} = n \sum_{i=1}^{f} s_i $$

with no per-object allocator overhead, since all memory is claimed once, up front, in a small number of large array allocations rather than $n$ separate malloc calls.

Free list operation cost. Both ALLOCATE-OBJECT and FREE-OBJECT on a free-list-managed array take:

$$ O(1) $$

time, since both operations only touch the head of the free list and the specific slot being allocated or freed — no scanning or searching is required.

Diagrams

flowchart TD
    A[Request new object] --> B{free list head is NULL?}
    B -->|Yes| C[Error: out of space<br/>no free slots remain]
    B -->|No| D[x = free list head]
    D --> E[Advance free list head to next free slot]
    E --> F[Return x as the newly allocated object index]
    G[Free an object x] --> H[Set x.next = current free list head]
    H --> I[Set free list head = x]

Pseudocode

Pointer-based linked list node operations (for comparison):

ALLOCATE-OBJECT()
    if free == NIL
        error "out of space"
    else
        x = free
        free = x.next
        return x

FREE-OBJECT(x)
    x.next = free
    free = x

Multiple-array representation initialization (n objects, using indices 1..n, with 0 or n+1 as NIL sentinel):

INIT-FREE-LIST(key, next, prev, n)
    free = 1
    for i = 1 to n - 1
        next[i] = i + 1
    next[n] = NIL

Using the array-based object system to build a simple linked list:

LIST-INSERT-ARRAY(L, key, next, prev, free, k)
    x = ALLOCATE-OBJECT()
    key[x] = k
    next[x] = L
    prev[x] = NIL
    if L != NIL
        prev[L] = x
    L = x
    return L

Step-by-Step Example

Let me trace the array-based (multiple-array) representation with capacity $n = 5$, using arrays key[], next[], and a free list.

Initial state after INIT-FREE-LIST: free = 1, and the free list threads through next[] as 1 -> 2 -> 3 -> 4 -> 5 -> NIL.

I call ALLOCATE-OBJECT() to get a slot for key 10:

I call ALLOCATE-OBJECT() again for key 20:

Now I call FREE-OBJECT(1) to release the first object:

The free list is now 1 -> 3 -> 4 -> 5 -> NIL, and slot 1 is available for reuse. If I now call ALLOCATE-OBJECT() again for key 30:

This demonstrates the free list correctly recycling freed slots in constant time, without needing to scan the array for an empty spot.

Time Complexity

Space Complexity

Pointer-based objects use $\Theta(n)$ total space for $n$ live objects, plus per-object allocator overhead that, while technically constant per object, has a real, sometimes significant, constant factor (commonly 16–32 bytes of hidden bookkeeping per allocation on many malloc implementations). The array-based representation uses $\Theta(n)$ space as well, but for the maximum number of objects $n$ ever needed, since the arrays must be pre-sized — this can waste space if far fewer than $n$ objects end up being used simultaneously, but it avoids malloc overhead entirely and is often more cache-friendly since array elements are stored contiguously.

Correctness Analysis

Correctness of the pointer-based approach follows directly from C’s memory model: as long as I only dereference pointers that point to valid, allocated memory, and I never use a pointer after freeing the memory it points to (a “dangling pointer” or “use-after-free” bug), the structure behaves exactly as intended, since each pointer genuinely and uniquely identifies one memory location.

Correctness of the array-based approach requires an additional invariant I have to maintain carefully myself: the free list must, at all times, contain exactly the set of indices that are not currently in use as live objects, and no index should ever appear in the free list more than once (which would corrupt the free list into a cycle or cause the same slot to be “allocated” twice simultaneously). As long as ALLOCATE-OBJECT and FREE-OBJECT are the only two operations that modify the free list, and they’re implemented exactly as shown (push/pop from the head), this invariant is preserved by induction on the sequence of operations performed.

Advantages

Pointer-based (native C pointers):

Array-based (multiple-array representation):

Disadvantages

Pointer-based:

Array-based:

Applications

Implementation in C

I’ll show both representations side by side for a simple linked list of integers, so the contrast is direct and concrete.

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

/* ---------- Pointer-based representation ---------- */

typedef struct PtrNode {
    int key;
    struct PtrNode *next;
} PtrNode;

PtrNode* ptrListInsert(PtrNode* head, int key) {
    PtrNode* node = (PtrNode*)malloc(sizeof(PtrNode));
    node->key = key;
    node->next = head;
    return node;   /* new head of the list */
}

void ptrListPrint(PtrNode* head) {
    while (head != NULL) {
        printf("%d ", head->key);
        head = head->next;
    }
    printf("\n");
}

void ptrListFree(PtrNode* head) {
    while (head != NULL) {
        PtrNode* temp = head;
        head = head->next;
        free(temp);
    }
}

/* ---------- Array-based (multiple-array) representation ---------- */

#define CAPACITY 5
#define NIL_IDX -1

int key[CAPACITY];
int next[CAPACITY];
int freeHead;

void initFreeList(void) {
    freeHead = 0;
    for (int i = 0; i < CAPACITY - 1; i++) {
        next[i] = i + 1;
    }
    next[CAPACITY - 1] = NIL_IDX;
}

int allocateObject(void) {
    if (freeHead == NIL_IDX) {
        printf("Error: out of space\n");
        return NIL_IDX;
    }
    int x = freeHead;
    freeHead = next[x];
    return x;
}

void freeObject(int x) {
    next[x] = freeHead;
    freeHead = x;
}

int arrayListInsert(int listHead, int k) {
    int x = allocateObject();
    if (x == NIL_IDX) return listHead;
    key[x] = k;
    next[x] = listHead;
    return x;  /* new head of the list */
}

void arrayListPrint(int listHead) {
    while (listHead != NIL_IDX) {
        printf("%d ", key[listHead]);
        listHead = next[listHead];
    }
    printf("\n");
}

int main(void) {
    /* --- Pointer-based demo --- */
    printf("Pointer-based list:\n");
    PtrNode* pHead = NULL;
    pHead = ptrListInsert(pHead, 30);
    pHead = ptrListInsert(pHead, 20);
    pHead = ptrListInsert(pHead, 10);
    ptrListPrint(pHead);
    ptrListFree(pHead);

    /* --- Array-based demo --- */
    printf("\nArray-based list:\n");
    initFreeList();
    int aHead = NIL_IDX;
    aHead = arrayListInsert(aHead, 30);
    aHead = arrayListInsert(aHead, 20);
    aHead = arrayListInsert(aHead, 10);
    arrayListPrint(aHead);

    return 0;
}

I want to draw attention to how closely arrayListInsert mirrors ptrListInsert — the logic is nearly identical, just substituting array-index “pointers” for real ones, and substituting allocateObject()/freeObject() for malloc()/free(). This side-by-side similarity is exactly the point: once I understand the correspondence, I can translate almost any pointer-based structure into an array-based one, and vice versa.

Sample Input and Output

Input:
Pointer-based: insert 30, then 20, then 10 (each at the head)
Array-based:   insert 30, then 20, then 10 (each at the head)

Output:
Pointer-based list:
10 20 30 

Array-based list:
10 20 30

Both representations produce identical logical results, confirming that the array-based version faithfully reproduces the same linked-list behavior as the native pointer-based version, just using a different underlying mechanism.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version