Structure and Pointer

Programming Language & Its Applications — Pointers, Structure and Data Files in C, NEC licence examination syllabus (Nepal Engineering Council).

Structure and Pointer

The arrow operator, self-referential structs, and the moment C stops being a calculator and starts building data structures.

A struct containing a pointer to its own type is the seed of every dynamic data structure — linked lists, trees, graphs, hash-table buckets. This is the single most consequential idea in the C syllabus, because everything in the DSA paper is built from it. Once you can allocate a node and link it to another, array-size limits stop being a constraint.

🌍 Where this lives: open Task Manager or ps and you are looking at a linked list — the Linux kernel keeps every running process in one, defined in sched.h as a struct holding pointers to the next and previous task. Your browser's Back button is a linked list. Undo in any editor is a linked list. The Nepali word-suggestion on your phone keyboard walks a trie, which is a tree of these nodes. When you understand this page, you understand the shape of all of them.

Dot versus arrow

Student s; Student *p = &s; s.roll ✔ dot: the object itself p->roll ✔ arrow: through a pointer (*p).roll ✔ identical to p->roll *p.roll ✗ ERROR — . binds tighter than *, so this parses as *(p.roll) The arrow exists ONLY as shorthand. p->x is defined to be exactly (*p).x. The parentheses in (*p).x are mandatory, which is why -> was invented. Chaining: p->joined.yyyy pointer, then nested member p->next->next->data walking a list

arrow.c

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

typedef struct { int dd, mm, yyyy; } Date;
typedef struct {
    int   roll;
    char  name[20];
    Date  dob;
} Student;

int main(void) {
    Student s = {101, "Ram Bahadur", {15, 3, 2004}};
    Student *p = &s;

    /* three spellings of the same access */
    printf("%d %d %d\n", s.roll, p->roll, (*p).roll);

    /* chaining into the nested struct */
    printf("%s born %02d/%02d/%d\n",
           p->name, p->dob.dd, p->dob.mm, p->dob.yyyy);

    /* modifying through the pointer changes s */
    p->dob.yyyy = 2005;
    printf("s.dob.yyyy is now %d\n", s.dob.yyyy);
    return 0;
}
Output:
101 101 101
Ram Bahadur born 15/03/2004
s.dob.yyyy is now 2005

Self-referential structures

struct Node { int data; struct Node *next; /* pointer to the SAME type */ }; Why "struct Node *" and not "struct Node"? A struct cannot contain ITSELF by value — that would need infinite size. But it can contain a POINTER to itself, because a pointer is always 8 bytes regardless of what it points to. struct Bad { int d; struct Bad inner; }; ← ERROR: "field has incomplete type" Note: inside the declaration you must write the full "struct Node *", because a typedef name is not yet visible. The common idiom: typedef struct Node { int data; struct Node *next; /* tag name works here */ } Node; /* typedef name usable after */

Worked example 1 — a working linked list

linkedlist.c

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

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

Node *make_node(int v) {
    Node *n = malloc(sizeof *n);
    if (!n) { perror("malloc"); exit(1); }
    n->data = v; n->next = NULL;
    return n;
}

/* head can CHANGE, so we take Node** */
void push_front(Node **head, int v) {
    Node *n = make_node(v);
    n->next = *head;
    *head   = n;
}

void push_back(Node **head, int v) {
    Node *n = make_node(v);
    if (!*head) { *head = n; return; }
    Node *c = *head;
    while (c->next) c = c->next;
    c->next = n;
}

int delete_value(Node **head, int v) {
    Node **cur = head;
    while (*cur) {
        if ((*cur)->data == v) {
            Node *dead = *cur;
            *cur = dead->next;      /* unlink */
            free(dead);
            return 1;
        }
        cur = &(*cur)->next;
    }
    return 0;
}

void reverse(Node **head) {
    Node *prev = NULL, *cur = *head;
    while (cur) {
        Node *nxt = cur->next;
        cur->next = prev;
        prev = cur; cur = nxt;
    }
    *head = prev;
}

void print(const char *tag, const Node *h) {
    printf("%-10s", tag);
    for (; h; h = h->next) printf("%d -> ", h->data);
    printf("NULL\n");
}

void destroy(Node **head) {
    while (*head) { Node *d = *head; *head = d->next; free(d); }
}

int main(void) {
    Node *list = NULL;
    push_back(&list, 10);
    push_back(&list, 20);
    push_back(&list, 30);
    print("built", list);

    push_front(&list, 5);
    print("push 5", list);

    delete_value(&list, 20);
    print("del 20", list);

    reverse(&list);
    print("reversed", list);

    destroy(&list);
    print("destroyed", list);
    return 0;
}
Output:
built     10 -> 20 -> 30 -> NULL
push 5    5 -> 10 -> 20 -> 30 -> NULL
del 20    5 -> 10 -> 30 -> NULL
reversed  30 -> 10 -> 5 -> NULL
destroyed NULL

Tracing reverse() on 5 → 10 → 30: step 0: prev=NULL cur=[5] step 1: nxt=[10]; [5].next=NULL; prev=[5]; cur=[10] list so far: NULL <- 5 step 2: nxt=[30]; [10].next=[5]; prev=[10]; cur=[30] NULL <- 5 <- 10 step 3: nxt=NULL; [30].next=[10]; prev=[30]; cur=NULL NULL <- 5 <- 10 <- 30 loop ends, *head = prev = [30] result: 30 -> 10 -> 5 -> NULL ✔ Three pointers, one pass, no extra memory: O(n) time, O(1) space. This exact function is one of the most-asked technical interview questions in the world.

Array versus linked list — the real trade-off

ARRAY LINKED LIST access a[i] O(1) O(n) must walk insert at front O(n) shift O(1) relink insert at end O(1) amortised O(n) or O(1) with tail delete found node O(n) shift O(1) relink memory per item 0 overhead +8 bytes for next cache behaviour excellent poor, nodes scattered size fixed / realloc grows freely The overhead is real: storing 1,000,000 ints array : 4,000,000 bytes list : 4 + 8 = 12 bytes/node (plus malloc bookkeeping, often 16 more) → ~24,000,000 bytes → 6× the memory for the same data. That is why real code uses arrays (or dynamic arrays like C++ vector) by default, and lists only when the insert and delete pattern genuinely demands it.

Do not read the table as "lists are better at inserting". A list insert is O(1) once you already hold the node. Finding it is O(n). For a middle insert in a 1000-element collection, the array's memmove of 500 contiguous ints often beats the list's 500-node pointer chase — because the array touches ~8 cache lines and the list touches ~500. Big-O is not the whole story on real hardware.

Worked example 2 — a binary search tree

bst.c

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

typedef struct TNode {
    int data;
    struct TNode *left, *right;
} TNode;

TNode *insert(TNode *root, int v) {
    if (!root) {
        TNode *n = malloc(sizeof *n);
        n->data = v; n->left = n->right = NULL;
        return n;
    }
    if (v < root->data) root->left  = insert(root->left,  v);
    else if (v > root->data) root->right = insert(root->right, v);
    return root;                /* duplicates ignored */
}

void inorder(const TNode *r) {   /* gives SORTED order */
    if (!r) return;
    inorder(r->left);
    printf("%d ", r->data);
    inorder(r->right);
}

int height(const TNode *r) {
    if (!r) return 0;
    int l = height(r->left), q = height(r->right);
    return 1 + (l > q ? l : q);
}

int search(const TNode *r, int v, int *steps) {
    while (r) { (*steps)++;
        if (v == r->data) return 1;
        r = (v < r->data) ? r->left : r->right;
    }
    return 0;
}

int main(void) {
    int vals[] = {50, 30, 70, 20, 40, 60, 80};
    TNode *root = NULL;
    for (int i = 0; i < 7; i++) root = insert(root, vals[i]);

    printf("inorder (sorted): "); inorder(root); printf("\n");
    printf("height = %d\n", height(root));

    int steps = 0;
    printf("search 60: %s in %d steps\n",
        search(root, 60, &steps) ? "found" : "absent", steps);
    steps = 0;
    printf("search 45: %s in %d steps\n",
        search(root, 45, &steps) ? "found" : "absent", steps);
    return 0;
}
Output:
inorder (sorted): 20 30 40 50 60 70 80
height = 3
search 60: found in 3 steps
search 45: absent in 3 steps

The tree built from 50,30,70,20,40,60,80: 50 / \ 30 70 / \ / \ 20 40 60 80 height = 3, and 7 nodes = 2³ − 1, so it is PERFECTLY balanced. Search cost = height = 3 = log₂(8). Insert 60: 60 > 50 go right; 60 < 70 go left; found. 3 steps. The catch: insert 10,20,30,40,50 IN ORDER and you get 10 \ 20 \ 30 ... height = n, search = O(n) — a linked list wearing a tree costume. Fixing this is what AVL and red-black trees do, and it is the next chapter of the DSA syllabus.

🌍 Why this matters beyond the exam: the balanced version of this tree is inside almost everything you use. PostgreSQL and MySQL index every table with a B-tree — a fatter cousin of this BST — which is why SELECT ... WHERE id = 5 on a ten-million-row table returns instantly instead of scanning ten million rows. Your filesystem indexes directories the same way. If you want to go deeper, look up "why databases use B-trees and not binary trees": the answer is disk block size, and it is one of the most satisfying explanations in computer science.

💡 Exam angle: write the node struct correctly from memory (struct Node *next, not struct Node next) and be able to explain why. The linked-list operations — create, insert at front/end, delete, reverse, traverse — are standard full-mark programming questions. Know the array-vs-list comparison table with reasons, and be able to draw a BST from an insertion sequence and give its height. Explain why Node** is needed when the head may change.

Syllabus points

Pointer to structure; arrow operator

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.