How to Define a Node in C: The Standard Implementation Pattern Used in Node.js

The most common way to implement or define a node in C is by creating a struct that combines a payload data field—typically declared as void * for type flexibility—with one or more pointers to adjacent nodes, enabling the construction of linked lists, trees, and graphs.

When building linked data structures in systems programming, knowing how to properly define a node in C is fundamental. The Node.js codebase, which combines high-performance C and C++ components, demonstrates this pattern extensively through its native module system and dependencies. This implementation approach appears consistently across the repository, from module linking to heap management.

The Canonical Node Structure Pattern

The standard implementation uses a self-referential structure containing two essential components:

1. Payload data – Stores the actual value, often as void * to accommodate any data type without duplicating structure definitions.
2. Connectivity pointers – References to neighboring nodes (next for lists, left/right for trees, etc.).

A minimal singly-linked list node definition illustrates this pattern:

typedef struct Node {
    void *data;          /* Generic payload storage */
    struct Node *next;   /* Link to subsequent node */
} Node;

This layout separates data storage from structural relationships while maintaining memory efficiency.

Production Examples in the Node.js Source Code

The Node.js repository contains multiple implementations of this pattern for different use cases.

Module Linking Nodes (src/node.h)

In src/node.h at line 1252, the codebase defines struct node_module to maintain a linked list of native modules:

struct node_module {
    int nm_flags;
    void *nm_dso_handle;
    const char *nm_filename;
    node::addon_register_func nm_register_func;
    node::addon_context_register_func nm_context_register_func;
    const char *nm_modname;
    void *nm_priv;
    struct node_module *nm_link;  /* Pointer to next module in chain */
};

The nm_link field implements the singly-linked list pattern, allowing the runtime to traverse registered modules sequentially.

Heap Management Nodes (deps/uv/src/heap-inl.h)

The libuv dependency demonstrates a more complex node structure for binary heap operations in deps/uv/src/heap-inl.h at line 27:

struct heap_node {
    struct heap_node *left;
    struct heap_node *right;
    struct heap_node *parent;
};

This structure supports parent-child relationships required for heap ordering, using three pointers instead of one to enable bidirectional traversal and tree balancing operations.

Practical Implementation Examples

Singly-Linked List Creation and Traversal

The following example demonstrates allocating nodes, storing string data, and linking them:

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

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

int main(void) {
    Node *a = malloc(sizeof(Node));
    Node *b = malloc(sizeof(Node));
    Node *c = malloc(sizeof(Node));

    a->data = "first";
    b->data = "second";
    c->data = "third";

    a->next = b;
    b->next = c;
    c->next = NULL;

    for (Node *cur = a; cur != NULL; cur = cur->next) {
        printf("%s\n", (char *)cur->data);
    }

    free(c);
    free(b);
    free(a);
    return 0;
}

Binary Tree Node Definition

For hierarchical data, the pattern extends to multiple child pointers:

typedef struct TreeNode {
    int key;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
} TreeNode;

This matches the implementation found in deps/uv/src/heap-inl.h, providing references to both children and the parent for efficient tree traversal.

Why This Pattern Dominates C Development

The payload-plus-pointer approach persists across codebases for specific technical reasons:

• Type Agnosticism: Using void * for data allows the same node structure to handle integers, strings, or complex objects without modification.
• Memory Efficiency: Nodes store only necessary pointers (one for singly-linked lists, two for doubly-linked, three for binary trees), minimizing overhead.
• Predictable Performance: Traversal operates at O(n) complexity with direct pointer chasing, avoiding cache misses from unnecessary indirection.
• Simple Allocation: Standard malloc(sizeof(Node)) calls suffice for dynamic creation, with pointer assignment handling connectivity.

Summary

• Define a node in C using a struct containing a void *data payload and struct Node *next (or similar) pointers.
• The Node.js codebase implements this pattern in src/node.h (struct node_module with nm_link) and deps/uv/src/heap-inl.h (struct heap_node with left/right/parent).
• Use malloc(sizeof(Node)) for dynamic allocation and set pointer fields to establish connections.
• This structure supports linked lists, trees, and graphs while maintaining type flexibility through generic pointers.

Frequently Asked Questions

Why do C programmers use void * for the payload instead of specific types?

Using void * allows a single node structure definition to store any data type, from primitive integers to complex structures. This generic approach prevents code duplication that would occur if you defined separate IntNode, StringNode, and StructNode types. Programmers cast the pointer back to the appropriate type when accessing the data.

How do you allocate memory for a node in C?

Allocate nodes dynamically using malloc(sizeof(Node)), which reserves heap memory sized to fit the structure. Always verify the pointer returned is not NULL before dereferencing. When removing nodes from the structure, call free() on the node pointer to prevent memory leaks.

What distinguishes a singly-linked node from a doubly-linked node?

A singly-linked node contains one pointer (typically next) referencing the subsequent node, enabling forward-only traversal. A doubly-linked node adds a prev pointer to the previous node, allowing bidirectional traversal and O(1) deletion when you already hold the node reference, at the cost of additional memory per node.

Where can I find production examples of node structure implementations?

The Node.js repository provides concrete examples: examine src/node.h for the struct node_module implementation used in native module linking, and deps/uv/src/heap-inl.h for the struct heap_node binary heap implementation. These demonstrate how the canonical pattern adapts to specific algorithmic requirements in high-performance systems code.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}