Structs and Linked Data Structures in C

A struct groups related values into one record. Its members have names and can have different types. A sensor reading, for example, needs both an identifier and a temperature.

Define and initialize a record

struct reading {
    int id;
    double temp_c;
};
struct reading r = {.temp_c = 21.5, .id = 7};
r.temp_c += 0.5;

The definition introduces the type struct reading; reading is its tag. The final semicolon belongs after the closing brace. Defining the type allocates no object. The declaration of r creates one object, and . selects its members. Here the temperature becomes 22.0 °C. With only a tag declared, the type name includes struct: reading r; needs a separate typedef.

An initializer such as {7, 21.5} follows declaration order. Designators such as .id = 7 let you name members in another order. Members omitted from an initializer receive zero values, so {0} initializes the whole record. A local declaration struct reading r; without an initializer leaves its members indeterminate until assigned.

A member has its own type and address. To read a temperature with scanf, use scanf("%lf", &r.temp_c) and check that the return value is 1. The dot binds before &, so this passes the address of the double member.

Copy and compare the values

struct reading s = r;
s.temp_c = -4.0;
int same = r.id == s.id && r.temp_c == s.temp_c;

Assignment copies all members. Changing s.temp_c leaves r.temp_c at 22.0. Fixed arrays inside structs are copied too: a char name[32] member belongs to the record. This works even though standalone C arrays cannot be assigned with =. Pointer members need extra care because the copied pointer still points at the same object.

C does not define == for whole structs. Compare the members that define equality for your task. memcmp compares raw bytes, including padding, and can report a difference between records whose member values are equal.

Follow the memory layout

Members appear in declaration order, with no padding before the first member. The compiler can add unused bytes between members and at the end to meet alignment requirements. On a common 64-bit platform with 4-byte int and 4-byte alignment, struct { char c; int i; char d; } occupies 12 bytes. Its members start at offsets 0, 4, and 8. Reordering to int i; char c; char d; commonly reduces the size to 8 bytes. Use sizeof for the actual size and offsetof from <stddef.h> for an offset.

Structs can nest. With struct point { double x_m, y_m; }; and struct rect { struct point corner; double width_m, height_m; };, box.corner.x_m reaches the corner's x-coordinate in meters. A struct cannot contain a complete member of its own type: that would require an endlessly large object. A pointer to its own type has a fixed size and makes linked nodes possible.

A typedef gives an existing type another name. It changes how you write the type, not how its objects behave. typedef double meters; makes meters another name for double.

Name a struct and pass it by value

typedef struct {
    int id;
    double temp_c;
} reading;

reading make_reading(int id, double t) {
    reading r = {id, t};
    return r;
}
void warm_copy(reading r) {
    r.temp_c += 1.0;
}

You can now declare reading r = make_reading(7, 21.5);. Returning a struct returns its value. Calling warm_copy(r) gives the function a copy, so the caller's temperature stays 21.5 °C. A copy of a small record is often the clearest interface when the caller's object should stay unchanged.

A self-referential type needs its tag inside the definition:

typedef struct node {
    int number;
    struct node *next;
} node;

The alias node becomes available after the declaration. Inside these braces, struct node already names the incomplete type and can be used for a pointer. The tag and the alias can have the same spelling because tags use their own namespace.

Reach the caller's object through a pointer

void warm(reading *p) {
    p->temp_c += 1.0;
}
reading r = {7, 21.5};
reading *p = &r;
p->temp_c -= 1.5;
warm(&r);

The subtraction changes r.temp_c to 20.0; warm then changes it to 21.0. The function receives a copy of the address, and both pointers still reach the same record. Use -> with a pointer and . with a struct object. p->temp_c means (*p).temp_c. The parentheses are necessary because member access binds more tightly than dereferencing: *p.temp_c tries to select a member from p before applying *.

For reading without a struct copy, accept const reading *p. Assigning to p->temp_c through that pointer is rejected. The pointer variable can still change, for example when it moves through an array. reading *const p instead makes the pointer itself fixed. For structs with pointer members, pointer-to-const does not make separately allocated pointed-to data read-only.

Give a heap record an owner

Include <stdlib.h> for allocation and <stdbool.h> for this success result:

bool make_heap_reading(reading **out, int id, double t) {
    reading *p = malloc(sizeof *p);
    if (p == NULL) return false;
    *p = (reading){.id = id, .temp_c = t};
    *out = p;
    return true;
}

The function writes *out only after allocation succeeds. The caller can declare reading *item = NULL;, call make_heap_reading(&item, 8, -2.0), handle a false result, and later call free(item). sizeof *p measures the pointed-to type even before p points at an initialized record; this expression does not read that record.

A pointer to an automatic local struct becomes dangling when the function returns. Return the struct value or a heap allocation with a clear owner. Returning &r from a function whose local variable is r cannot extend its lifetime.

An array of structs keeps records side by side. Use an index to select a record and then a dot to select a member. This makes scans, searches, and sorting work much like they do with an array of numbers.

Scan records with an explicit count

reading readings[4] = {
    {1, 21.5}, {2, -3.0}, {3, 18.25}, {4, 30.0}
};
size_t n = sizeof readings / sizeof readings[0];
size_t best = 0;
for (size_t i = 1; i < n; ++i) {
    if (readings[i].temp_c > readings[best].temp_c)
        best = i;
}

Here reading is the alias for the identifier-and-temperature struct. The best index progresses from 0 to 3, so the warmest record has id 4 and temperature 30.0 °C. Starting with a real element also works when every temperature is negative; starting with a supposed maximum of zero can fail. This scan requires at least one element. A reusable search must report an empty array before reading element 0.

The sizeof count works where readings is an array. In a function parameter, an array declaration becomes a pointer, so pass n separately. (items + i)->temp_c and items[i].temp_c reach the same member.

Supply a comparator for qsort

Include <stdlib.h>. For finite temperature values, this comparator returns a sign without converting a small temperature difference to an integer:

int cmp_temp(const void *a, const void *b) {
    const reading *x = a;
    const reading *y = b;
    return (x->temp_c > y->temp_c)
         - (x->temp_c < y->temp_c);
}
/* With the array above: */
qsort(readings, n, sizeof readings[0], cmp_temp);

The comparator receives addresses of elements. Negative means the first comes earlier, zero means a tie, and positive means later. The sorted id order is 2, 3, 1, 4. Returning the raw double difference truncates a difference such as −0.25 to zero. Subtracting integer keys can overflow. Comparing first avoids those errors. qsort does not preserve the original order of ties.

Grow an array without losing its storage

Keep its used count and capacity separately. For an allocated array with positive cap, use a temporary pointer when doubling capacity. Include <stdint.h> for SIZE_MAX:

if (cap > SIZE_MAX / 2 / sizeof *items) return false;
size_t new_cap = 2 * cap;
reading *tmp = realloc(items, new_cap * sizeof *items);
if (tmp == NULL) return false;
items = tmp;
cap = new_cap;

These statements belong inside a function returning bool; items is its array pointer and cap its positive capacity. On failure the old allocation remains available. On success the allocation may move, so old pointers to its elements must be replaced. A zero starting capacity needs its own initial allocation.

Decide what a copy owns

With typedef struct { char *name; int age; } person;, person b = a; copies the address in name. Both records reach the same string. Freeing both copies as owners would free the same allocation twice. For an independent copy, allocate strlen(a.name) + 1 bytes, check success, and use strcpy from <string.h>. A fixed member char name[32] is copied with the struct. strdup performs allocation and copying, but it belongs to POSIX and C23, not the C17 standard library.

An enumeration gives readable names to integer choices. Names such as HIGH make a condition's purpose visible without requiring the reader to remember what the number 10 represents.

Follow the numbering

enum weekday { MON, TUE, WED, THU, FRI, SAT, SUN };
enum level { LOW = 1, MEDIUM, HIGH = 10, CRITICAL };
enum level alert = HIGH;

An omitted first value is zero. Later omitted values increase the previous value by one. Thus MON is 0 and SUN is 6; the levels are 1, 2, 10, and 11. An explicit value restarts the counting at that point. Different constants can share a value, but identical values cannot appear as separate case labels in the same switch.

An alias can shorten a declaration: typedef enum { RED, YELLOW, GREEN } light; allows light signal = RED;. Enumeration constants share the ordinary identifier namespace in their scope. Two different enums cannot both declare RED in the same scope. Prefixes such as LIGHT_RED and PAINT_RED keep the names distinct.

Handle each choice

const char *level_name(enum level value) {
    switch (value) {
        case LOW: return "low";
        case MEDIUM: return "medium";
        case HIGH: return "high";
        case CRITICAL: return "critical";
    }
    return "unknown";
}

Each return ends its case. If a case instead performs an action and should then stop, give it a break; reaching the next label continues execution there. With GCC, -Wall enables warnings for missing enum cases when there is no default; Clang also diagnoses such omissions by default. A warning can reveal a missing case when you later add a constant.

Validate input as a set of choices

The enum type does not enforce membership in the named set. C17 permits assignment from an integer, so enum level x = 42; can compile. A check that the number lies from 1 through 11 still admits unnamed values such as 6. Test the actual allowed values:

#include <stdbool.h>
bool valid_level(int value) {
    return value == LOW || value == MEDIUM
        || value == HIGH || value == CRITICAL;
}

Only after that check should input become a level. For the consecutive weekdays, a range check from MON through SUN is sufficient. In an ordinary C17 enum, the enumerator constants have type int. C23 additionally supports a specified underlying type, such as enum color : unsigned char; that syntax is not C17.

Print names and use counts

printf("%d\n", SUN) prints "6", not "SUN". For consecutive values starting at zero, a name array gives the text: const char *day_names[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};. After validating an index, day_names[SUN] is "Sun". Indexing such an array with a level value such as HIGH would need a different mapping because the level values have gaps.

Adding DAY_COUNT immediately after SUN gives it value 7, useful as a loop bound or array size. It counts days but is not itself a valid day. Enum names follow C scope rules and can be shown by debuggers; a #define instead performs preprocessor text substitution.

A union gives several members the same storage. It fits a value that can be one of several kinds. A struct gives each member its own storage and fits a record that needs all those values together.

Store one alternative

union value {
    int i;
    double d;
    char c;
};
union value v = {.d = 2.5};

All members begin at the same address. The union must hold its largest member and meet alignment needs; with an 8-byte double on common platforms, this union occupies 8 bytes. A plain initializer {42} initializes its first member, i; .d = 2.5 chooses d explicitly.

Writing v.i = 42 after the initializer replaces the stored alternative. Reading v.d afterward does not convert 42 into a double: it interprets the stored bytes using another representation. That representation can be invalid. Read the member belonging to the value you stored.

Record which member is valid

Pair the union with an enum. The enum is the tag, and the union is the payload:

enum kind { K_INT, K_DOUBLE, K_CHAR };
struct tagged {
    enum kind kind;
    union value as;
};
struct tagged make_double(double d) {
    return (struct tagged){.kind = K_DOUBLE, .as = {.d = d}};
}

A helper sets both pieces together. Writers keep the two fields synchronized. If code writes t.as.i but leaves t.kind as K_DOUBLE, a later reader chooses the wrong representation.

#include <stdio.h>
void print_cell(struct tagged t) {
    switch (t.kind) {
        case K_INT: printf("%d", t.as.i); break;
        case K_DOUBLE: printf("%.1f", t.as.d); break;
        case K_CHAR: printf("%c", t.as.c); break;
    }
}

Calling this function for cells holding 42, 2.5, and 'x', with spaces printed between calls, produces "42 2.5 x". Each case chooses both the matching member and the matching format. A calculator token can similarly hold either a number or an operator.

On common 64-bit platforms, a 4-byte enum, padding, and this 8-byte union make struct tagged occupy 16 bytes. A struct storing the enum plus all three alternatives separately commonly takes 24 bytes. These are layout examples; query the actual types with sizeof.

Pack small flags into bit-fields

struct flags {
    unsigned int ready : 1;
    unsigned int mode : 3;
};

The width follows the colon. A 1-bit unsigned field holds 0 or 1; a 3-bit field holds 0 through 7. Storing 9 in mode keeps the low three bits and stores 1. This loses information, so validate a mode before storing it when larger values indicate an error.

A bit-field has no separately addressable location, so &flags.mode is invalid for a variable named flags. Its allocation order and packing depend on the implementation. Do not use a bit-field declaration as a portable promise about an exact file or device layout. A named width specifies the field's value range, not the layout of every byte around it.

A singly linked list stores each item in a separately allocated node. Each node holds its value and the address of the next node. The head points at the first node; NULL marks both an empty list and the end of a chain.

Define the link and prepend

#include <stdbool.h>
#include <stdlib.h>
typedef struct node {
    int number;
    struct node *next;
} node;

bool prepend(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *head;
    *head = n;
    return true;
}

Start with node *list = NULL;. Call prepend(&list, value) and handle a false result. The function takes the address of the caller's head pointer. *head therefore names the pointer that must change. Taking only node *head and assigning to that local pointer would leave the caller's head unchanged.

The order of the final assignments preserves the old list. First connect the new node to the old head; then replace the head. Reversing those statements sets n->next to n itself and loses the old chain. For arrivals 1, 2, and 3, successive prepends produce 1, then 2 → 1, then 3 → 2 → 1 → NULL. Front insertion reverses arrival order.

Walk without moving the owner

#include <stdio.h>
void print_list(const node *head) {
    for (const node *p = head; p != NULL; p = p->next)
        printf("%d ", p->number);
}

The traversal pointer p moves while head stays available. The example prints "3 2 1 " with a trailing space. For an empty list, the loop body runs zero times. There is no array index: each step reads one link to find the next node. The allocations can be scattered throughout memory, and inserting a node does not move existing nodes.

Add at the back

bool append(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    node **link = head;
    while (*link != NULL) link = &(*link)->next;
    *link = n;
    return true;
}

link starts at the caller's head. It then moves to the address of each next member until it names the terminating null link. Assigning there works for an empty list too. Without a saved tail pointer, every append must first follow the existing chain to its end. A function can also return a new head, provided the caller stores it and handles allocation failure without losing the old list.

Release nodes in a safe order

void clear_list(node **head) {
    while (*head != NULL) {
        node *old = *head;
        *head = old->next;
        free(old);
    }
}

Read the successor while old is still alive, move the head, and then free the old node. After the loop the caller's head is NULL. Reading old->next after freeing old is a use-after-free even if the memory appears unchanged. A memory checker can help reveal invalid reads and forgotten allocations; cleanup must also run after a later operation fails.

Searching a list follows one link at a time. Insertion and deletion need something more: the address of the link that must change. That link may be the head pointer or a next member inside an earlier node.

Search by value

Using the node type with number and next members:

node *find(node *head, int value) {
    for (node *p = head; p != NULL; p = p->next)
        if (p->number == value) return p;
    return NULL;
}

A match returns the actual node's address. A missing value returns NULL. Reaching the 1,000th node requires following 999 links from the head, even when you know its position in advance.

Keep a pointer to the link that will change

A node ** can point at either the head or a node's next field. Call it link: *link is the node currently reached by that link. Advancing with link = &(*link)->next changes which link you inspect; it does not change the list.

bool insert_sorted(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number < value)
        link = &(*link)->next;
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *link;
    *link = n;
    return true;
}

Include <stdbool.h> and <stdlib.h>. The input list must already be in ascending order. Stop before the first value that is not smaller than the new one, so duplicates go before equal values. The left side of && checks for NULL before the right side dereferences the node. Swapping those tests would dereference a null pointer at the end.

For insertions 5, 2, 8, and 4, the final list is 2 → 4 → 5 → 8. When inserting 4 into 2 → 5 → 8, link moves from the head to 2.next. The new node points to 5, and 2.next is redirected to the new node. If the new item is smallest, link still names the head. At the end, it names the final null link.

Unlink before freeing

bool remove_first(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number != value)
        link = &(*link)->next;
    if (*link == NULL) return false;
    node *old = *link;
    *link = old->next;
    free(old);
    return true;
}

The loop finds the incoming link. Saving its target as old keeps the node available while *link is changed to its successor. Only then is the removed node freed. Removing 5 from 2 → 4 → 5 → 8 gives 2 → 4 → 8. Removing 2 next changes the head and leaves 4 → 8. If the value is absent, the function returns false without changing the list.

A two-pointer version keeps prev and cur. When prev is null, the match is the head and the head must change; otherwise update prev->next. Forgetting the head case leaves a pointer to freed memory. The link-address version handles both through the same assignment.

Check empty input, a one-node list, first and last matches, and a missing value. For each change, identify the incoming link, the affected node, and its successor before writing an assignment. No remaining node should become unreachable, and no link should point at a freed node.

The useful question is which operations your program performs. Arrays and lists can hold the same values, but they reach and move those values differently.

Compare the operations

A list does not make finding a position free. Insertion after a node you already hold is direct, but deletion also needs the predecessor or the link that points at the node. With only the node's address, a singly linked list generally needs a walk from the head to find that incoming link.

Storage also matters. On a typical 64-bit platform, a node with a 4-byte int and an 8-byte pointer occupies 16 bytes after padding. For 1,000 integers, nodes use 16,000 bytes plus allocation bookkeeping; a contiguous integer array uses 4,000 bytes. Scanning the array is usually faster because nearby values are stored together.

Keep list metadata together

typedef struct {
    node *head;
    node *tail;
    size_t count;
} list_t;

Initialize a wrapper with list_t list = {0};. Its empty-state rules are head == NULL, tail == NULL, and count == 0. Each successful insertion or deletion must update the count as well as the links. A failed allocation changes none of them.

With a tail pointer, appending after a checked allocation takes these assignments:

n->next = NULL;
if (list.tail == NULL) list.head = n;
else list.tail->next = n;
list.tail = n;
++list.count;

Here n is an initialized node. For the first node, head and tail become equal. Removing the last node must move the tail back; for a singly linked list this requires the predecessor. Removing the only node sets both ends to NULL and the count to zero.

Link both directions

typedef struct dnode {
    int value;
    struct dnode *prev, *next;
} dnode;
typedef struct {
    dnode *head, *tail;
} dlist;

void unlink_node(dlist *list, dnode *d) {
    if (d->prev != NULL) d->prev->next = d->next;
    else list->head = d->next;
    if (d->next != NULL) d->next->prev = d->prev;
    else list->tail = d->prev;
    free(d);
}

This function receives a live node belonging to the list. Both neighbors are repaired before it is freed. End cases change head or tail instead of a missing neighbor. A doubly linked list can walk backward and delete a held node without searching for its predecessor, at the cost of another pointer per node and more links to maintain.

Release owned data before its node

A word_node may own both a node allocation and a string allocation through word. Save next, call free(n->word), then free(n), and move to the saved successor. Freeing only the node leaks the string. Reading n->word after freeing the node is invalid. Ownership describes which code must release each allocation, even when several pointers can reach it.

A stack removes the most recently added item first: last in, first out (LIFO). Its operations define an abstract data type independently of whether an array or linked nodes hold the values. push adds at the top, pop removes the top, and peek reads the top without removing it.

Use an array and a count

#include <stdbool.h>
#define STACK_CAP 100
typedef struct {
    int items[STACK_CAP];
    int top;
} stack;

bool push(stack *s, int value) {
    if (s->top == STACK_CAP) return false;
    s->items[s->top++] = value;
    return true;
}
bool pop(stack *s, int *out) {
    if (s->top == 0) return false;
    *out = s->items[--s->top];
    return true;
}

Initialize with stack s = {0};. Here top is the number of stored items, so the top occupied index is top - 1. A successful push writes the next free slot and increases the count. A successful pop first lowers the count and then reads that index. The caller supplies a valid out pointer and checks the result before using its value.

Pushing 4, 7, and 1 then popping twice returns 1 and 7, leaving 4. Without a capacity check, a full push writes items[STACK_CAP] past the end. Without the empty check, the signed top drops from 0 to −1 and pop reads items[-1]. Both accesses have undefined behavior.

Use a list head as the top

A linked stack pushes by prepending a checked allocation. Pop removes the head:

bool pop_linked(node **top, int *out) {
    if (*top == NULL) return false;
    node *old = *top;
    *out = old->number;
    *top = old->next;
    free(old);
    return true;
}

node has an integer number and a next pointer. A linked stack has no fixed array capacity, but a push can fail when allocation fails. It still needs empty checks and cleanup of nodes left at the end.

Match nested delimiters

Scan input from left to right. Push each opening parenthesis, square bracket, or brace. For each closing delimiter, pop and check that the types match. A closer with no opener fails immediately. Finish by checking that the stack is empty: leftover openers also mean a mismatch.

The text "( [ ] { } )" balances. For "( ]", the closer does not match the popped opener. For "( ( )", one opener remains after scanning. A simple count of openers and closers would miss incorrect nesting such as "( [ ) ]".

Evaluate postfix expressions

Push numbers as they arrive. For a binary operator, pop the right operand first, then the left operand, compute left operator right, and push the result. For "3 4 + 2 *", + combines 3 and 4 into 7, then * combines 7 and 2 into 14. For "9 4 -", pop 4 as the right operand and 9 as the left, producing 5. Reversing them produces −5. Reject insufficient operands and require one final result; division also needs a nonzero right operand.

Function calls use stack-shaped lifetimes: a called function returns before its caller continues. Each active call needs a frame, so very deep recursion can exhaust the call stack even when heap allocations succeed.

A queue removes the earliest item first: first in, first out (FIFO). Enqueue adds at the back; dequeue removes from the front. After enqueuing A, B, and C, the next two removals return A and B. This fits work that must be handled in arrival order.

Keep both ends of a linked queue

Using nodes with number and next members, and including <stdbool.h> and <stdlib.h>:

typedef struct { node *head, *tail; } queue;

bool enqueue(queue *q, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    if (q->tail == NULL) q->head = n;
    else q->tail->next = n;
    q->tail = n;
    return true;
}
bool dequeue(queue *q, int *out) {
    if (q->head == NULL) return false;
    node *old = q->head;
    *out = old->number;
    q->head = old->next;
    if (q->head == NULL) q->tail = NULL;
    free(old);
    return true;
}

Initialize with queue q = {0};. Enqueue sets the old tail's link before moving the tail. For the first node, it also sets the head. Dequeue moves the head forward. When that removes the only node, the tail must become NULL too. Otherwise the next enqueue writes through a dangling tail pointer. Neither operation needs to walk the list.

Reuse a fixed array as a ring

A plain array queue that always removes index 0 must shift its remaining values. A circular buffer instead tracks a front index and an item count:

#define CAP 4
typedef struct {
    char items[CAP];
    unsigned head, count;
} ring;

bool ring_put(ring *q, char value) {
    if (q->count == CAP) return false;
    q->items[(q->head + q->count) % CAP] = value;
    ++q->count;
    return true;
}
bool ring_get(ring *q, char *out) {
    if (q->count == 0) return false;
    *out = q->items[q->head];
    q->head = (q->head + 1) % CAP;
    --q->count;
    return true;
}

Initialize a ring with {0}. head always identifies the front item when the queue is nonempty. The next insertion index is the front plus the number of items, wrapped by % CAP. Read the front before moving head. The count distinguishes empty from full without giving up a slot.

Trace the wrap

Enqueue A, B, and C into slots 0, 1, and 2. Dequeue A: head becomes 1 and count becomes 2. D enters slot 3; E enters slot 0. The physical array now holds E, B, C, D, but logical removal order is B, C, D, E. The ring is full because count is 4, even though the front is at index 1.

Another design tracks head and the next free tail index without a count. In that design equal indexes could mean empty or full, so a common policy leaves one slot unused. Empty is head == tail; full is (tail + 1) % CAP == head. Do not mix that policy with the count-based version's capacity rules. Queues also support level-by-level tree visits by holding nodes awaiting their turn.

A binary tree gives each node at most two children, called left and right. The root is the top node. A leaf has no children, and a node together with all its descendants is a subtree. A missing child and an empty tree are represented by NULL.

Represent the branches

typedef struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
} tnode;

Each child pointer leads to the root of another tree. The same definition therefore describes a leaf, a large branching tree, or a long chain. Height counts edges on the longest root-to-leaf path: a root alone has height 0. Use −1 for an empty tree so a leaf's two empty subtrees lead naturally to height 0. Counting levels instead would give one more.

Apply the rule to whole subtrees

A binary search tree, or BST, orders the keys. For every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. Store each key once. This condition includes distant descendants. A root 50 with left child 30 and a right child 60 under that 30 is invalid: 60 is still in the left subtree of 50.

Insert 50, 30, 70, 20, 40, 60, and 80 into an empty BST. The root is 50; 30 and 70 are its children. The children of 30 are 20 and 40, and those of 70 are 60 and 80. Each branching choice preserves bounds inherited from the ancestors.

Choose one branch at each step

#include <stddef.h>
tnode *search(tnode *t, int key) {
    while (t != NULL) {
        if (key == t->key) return t;
        if (key < t->key) t = t->left;
        else t = t->right;
    }
    return NULL;
}

Searching for 60 in the example visits 50, goes right to 70, then left to 60: three nodes. Searching for 65 takes the same path, then tries the right child of 60. That child is NULL, so 65 is absent. You do not need to inspect the left subtree of 50 because every key there is smaller than 50.

The recursive form first handles t == NULL and a matching key, then searches the selected child. The empty-subtree test is the base case. Without it, an unsuccessful search eventually dereferences a null pointer. The loop version stops at the same boundary without adding recursive calls.

Let shape explain the work

A perfectly balanced tree with 20 levels holds 1,048,575 keys, and a search visits at most 20 nodes. Inserting already sorted keys 10, 20, 30, 40, 50 instead makes a rightward chain. Its height is 4, and finding 50 visits all five nodes. A BST's ordering rule alone does not keep the tree short. Self-balancing trees such as AVL trees rearrange branches to control height.

To find a minimum, follow left children until the next left link is NULL. To find a maximum, follow right children. In the seven-node example these keys are 20 and 80. The same direction choices work at any subtree root because the ordering rule applies there too.

Tree functions work on a subtree and connect their result to its parent. Keep the empty-subtree case explicit, and distinguish operations that change links from operations that only visit nodes.

Insert through the subtree link

With tnode containing key, left, and right, include <stdbool.h> and <stdlib.h>:

bool insert(tnode **link, int key) {
    if (*link == NULL) {
        tnode *n = malloc(sizeof *n);
        if (n == NULL) return false;
        *n = (tnode){.key = key, .left = NULL, .right = NULL};
        *link = n;
        return true;
    }
    if (key < (*link)->key) return insert(&(*link)->left, key);
    if (key > (*link)->key) return insert(&(*link)->right, key);
    return true;
}

Call with insert(&root, key) and check its result. An existing key leaves the tree unchanged and counts as success. The link address lets insertion update either the caller's root or a child pointer. In a return-root interface, store every result: t->left = insert(t->left, key) and root = insert(root, key). Ignoring a returned allocation when the original subtree was empty leaves that node unlinked and leaks it.

Choose when to visit the root

For insertions 50, 30, 70, 20, 40, 60, 80, the in-order output is "20 30 40 50 60 70 80". Pre-order gives "50 30 20 40 70 60 80"; post-order gives "20 40 30 60 80 70 50".

void free_tree(tnode *t) {
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

After free_tree(root), set the owner's root = NULL. The function frees children first so it can read their addresses from the live parent. Size is zero for an empty subtree, otherwise one plus both child sizes. Height is −1 for empty, otherwise one plus the larger child height. The example has size 7 and height 2.

Delete without breaking the order

A leaf becomes NULL. A node with one child is replaced by that child. For two children, copy the smallest key from the right subtree into the node, then delete that successor from its original position:

tnode *erase(tnode *t, int key) {
    if (t == NULL) return NULL;
    if (key < t->key) t->left = erase(t->left, key);
    else if (key > t->key) t->right = erase(t->right, key);
    else {
        if (t->left == NULL || t->right == NULL) {
            tnode *child = t->left != NULL ? t->left : t->right;
            free(t);
            return child;
        }
        tnode *s = t->right;
        while (s->left != NULL) s = s->left;
        t->key = s->key;
        t->right = erase(t->right, s->key);
    }
    return t;
}

Call as root = erase(root, key). Deleting 50 from the example puts 60 in the root and removes the old 60 node. The in-order output becomes "20 30 40 60 70 80"; pre-order becomes "60 30 20 40 70 80". A successor can have a right child, so its removal must reconnect that child.

For word keys, use the sign of strcmp, not pointer equality, and give each owned word its own allocation. Free the word before its node. A two-child deletion of such records also needs an ownership plan for the moved word and any associated value; copying an owning pointer and then freeing its original node's word would leave a dangling key.

A hash table chooses a starting location from a key. A hash function produces a number; reducing that number modulo a positive bucket count gives an index. Separate chaining keeps a linked list at each bucket, so lookup searches the selected chain.

Separate hashing from equality

A useful hash is deterministic, quick to calculate, and spreads the expected keys across buckets. Equal keys must produce equal hashes. Different keys may still share an index: this is a collision, and every table must handle it. With more possible keys than buckets, some collisions are unavoidable.

For letter-initial words on an ASCII-compatible system, toupper((unsigned char)word[0]) - 'A' assigns 26 letter buckets; "Luigi" starts in bucket 11. Many English words start with "s" and few with "x", so this rule can leave very uneven chains. The cast is needed because <ctype.h> functions require an unsigned-character value or EOF. Validate the initial letter and the character-set assumption before using this indexing rule.

A character-sum hash also has weaknesses. Using ASCII codes and ten buckets, "cat" sums to 99 + 97 + 116 = 312 and reaches bucket 2; "dog" sums to 314 and reaches bucket 4. "act" also sums to 312. Addition loses letter order, so every rearrangement collides.

Mix character order into the hash

unsigned long hash_word(const char *word) {
    unsigned long h = 5381;
    const unsigned char *p = (const unsigned char *)word;
    while (*p != '\0') {
        h = h * 33 + *p;
        ++p;
    }
    return h;
}

This djb2 pattern uses unsigned arithmetic, whose overflow wraps in a defined way. Signed overflow would have undefined behavior. For the ASCII strings "cat" and "act", the values are 193488125 and 193486013. Reduce with hash_word(word) % N, where N is the positive bucket count. Letter order changes these hashes, although reducing them can still produce a collision.

If a table treats "Cat" and "cat" as equal, both hashing and comparison must use the same case rule. Ignoring case only during comparison can send equal keys into different buckets, where lookup will not compare them. A negative signed hash remainder is also unsuitable as an array index.

Choose a collision strategy

Separate chaining stores every collision in a bucket's linked list. Lookup compares keys until it finds a match or reaches the end. Open addressing stores entries in the array itself. With linear probing, a collision tries the following slot and wraps at the end. Lookup follows the same probe sequence, so it can inspect several array slots.

Rebuild indexes when the table grows

The load factor is the number of stored keys divided by the bucket count. Twelve keys in eight buckets gives 1.5 entries per bucket on average. Sixteen buckets reduces that average to 0.75. This average does not guarantee that every chain is short; a poor hash may put all keys together.

A bucket index depends on the bucket count. After allocating and initializing a larger bucket array, recompute each stored key's index for the new count and relink it there. Copying the old head pointers into the same numbered new buckets leaves keys in places where the new lookup will not search. A chained table can hold more entries than buckets; open addressing needs unused slots for new entries and reliable probing.

A chained table combines an array, list links, string comparison, and ownership. Each entry owns its copied key. The bucket array owns the chains, and each chain ends at NULL.

Initialize buckets and look up text

#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#define N 26
typedef struct entry {
    char *key;
    int count;
    struct entry *next;
} entry;
static entry *table[N];

Static storage starts with null pointers in every bucket. A local array instead needs an initializer such as entry *table[N] = {NULL};. Use the unsigned hash_word function that starts at 5381 and mixes each byte with multiplier 33.

entry *find_word(const char *key) {
    size_t i = hash_word(key) % N;
    for (entry *e = table[i]; e != NULL; e = e->next)
        if (strcmp(e->key, key) == 0) return e;
    return NULL;
}

strcmp tests text. e->key == key would test whether the pointers name the same location. Two separate buffers can hold equal words, so pointer equality is not a word lookup.

Count an existing key or install a new one

bool add_word(const char *key) {
    entry *e = find_word(key);
    if (e != NULL) {
        if (e->count == INT_MAX) return false;
        ++e->count;
        return true;
    }
    e = malloc(sizeof *e);
    if (e == NULL) return false;
    e->key = malloc(strlen(key) + 1);
    if (e->key == NULL) {
        free(e);
        return false;
    }
    strcpy(e->key, key);
    e->count = 1;
    size_t i = hash_word(key) % N;
    e->next = table[i];
    table[i] = e;
    return true;
}

The caller supplies a null-terminated string. The INT_MAX check reports failure before a count would overflow its int storage. The extra byte in the string allocation holds '\0'. If the second allocation fails, free the unattached entry. The bucket head changes only after both allocations and initialization succeed.

Saving e->key = key instead would retain the caller's storage. If input repeatedly reuses one buffer, every saved pointer could show the newest word. Copying the text gives each entry a lifetime independent of that buffer. strdup provides that operation in POSIX and C23; explicit allocation and strcpy work in C17.

With a ten-bucket character-sum example, inserting "cat", "dog", "act" leaves "act" → "cat" in bucket 2 and "dog" in bucket 4. Looking up "tac" searches bucket 2, compares both words, and reaches NULL. A matching bucket is only a candidate location, not evidence of an equal key.

Free payloads, nodes, and bucket heads

void clear_table(void) {
    for (size_t i = 0; i < N; ++i) {
        entry *e = table[i];
        while (e != NULL) {
            entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
        table[i] = NULL;
    }
}

Saving next and freeing the key happen while the entry is still live. Resetting each bucket permits reuse. Memory-checking tools help verify exercised paths; allocation-failure paths need cleanup too. Hash order is not sorted order. To print alphabetically, collect keys for sorting or store them in a BST.

In open addressing, deletion needs a tombstone marker so lookup continues through a removed slot to later colliding keys. A truly unused slot can end an unsuccessful lookup. Probe sequences must be bounded, and the table must grow before every slot is occupied.