Part 8 — Data Structures and Algorithms in C

Data Structure Foundations and Complexity

This chapter establishes the foundation for the data-structures part: how to think about data structures in C, and how to reason about their complexity.

Why This Matters

In C, you build your own data structures — there is no standard container library. Choosing the right structure (and understanding its time/space cost) is the difference between a working system and one that collapses under load.

Prerequisites

c.memory.3 — ownership and lifetime.

Core Concept

A data structure is a way of organizing data plus the operations to access and modify it. In C, structures are built from:

struct — grouping related fields;
pointers — linking nodes;
dynamic allocation — variable size;
arrays — contiguous storage.

Complexity

Big-O describes how an operation's cost grows with input size n:

Notation	Growth	Example
O(1)	constant	array indexing, hash lookup (avg)
O(log n)	logarithmic	binary search, balanced tree lookup
O(n)	linear	linear search, array insert (shift)
O(n log n)	linearithmic	efficient sorts
O(n²)	quadratic	nested loops, insertion sort

Complexity is about growth rate, not wall-clock time; constant factors matter in practice but are hidden by Big-O.

How It Works

Each structure trades off different costs. Arrays give O(1) random access but O(n) insertion; linked lists give O(1) insertion at a known position but O(n) search; hash tables give O(1) average lookup but poor worst case; balanced trees give O(log n) worst-case operations with ordering.

Variations

Intrusive vs. container

Intrusive: the link fields live inside your node struct.
Container: the structure wraps/stores your data separately.

Intrusive structures avoid extra allocations and are common in kernels and embedded code.

Common Mistakes

Ignoring worst-case complexity (hash tables).
Using a linked list where an array is better (cache locality).
Not freeing nodes on destruction (leaks).
Confusing struct with a heap object (a struct can live on the stack).

Undefined Behavior

Dereferencing a NULL/dangling node pointer. VERIFIED
Use-after-free when a node is freed but still linked. VERIFIED

Portability

These structures are plain C and portable; their performance depends on the

allocator and cache behavior.

Under the Hood

Arrays are contiguous (cache-friendly); linked structures chase pointers (cache-unfriendly but flexible). Balanced trees and hash tables trade memory for speed. c.perf.2 covers locality.

Practical Usage

Use arrays for random access and cache locality.
Use linked structures for frequent insertion/deletion.
Use hash tables for fast key lookup; trees for ordered access.

Exercises

1. Classify the complexity of array push (amortized), linked-list prepend, and hash-table lookup. 2. Write a struct for a singly linked node (intrusive style) and a function to create/destroy a list.

Deep Challenge

Explain why a linked list can be slower than a vector even for operations the list is "supposed" to win, citing cache locality and allocation overhead. Give a concrete scenario.

c.memory.3 — ownership.
c.perf.2 — cache locality.
c.ds.2+ — specific structures.

References

Standard algorithms/data-structures literature.

Verification

Big-O definitions are standard computer science. VERIFIED
No example was executed during generation unless noted. `Execution not

verified.`

Progress

[ ] Read
[ ] Understand
[ ] Complete examples
[ ] Complete exercises
[ ] Complete deep challenge

Concept checkboxes

[ ] Big-O complexity
[ ] Intrusive vs. container
[ ] Complexity trade-offs

Mastery levels

Concept	Current level (0–8)	Target level
c.ds.complexity	0	5

← Prev Next →