C was the first real programming language for most of us, and data structures were where programming started to feel like engineering. Decades later, both are still everywhere: the Linux kernel, Git, Redis, nginx and the Python interpreter are written in C, and every database, cache and message queue is built on the data structures from this subject.
Part 1: C programming
Why C still matters
C was created by Dennis Ritchie at Bell Labs in the early 1970s to write the Unix operating system. It sits close to the hardware: you manage memory yourself, and each line maps fairly directly to machine instructions. That makes C fast and portable, but also unforgiving.
Real world: the Linux kernel, Git, Redis, nginx, SQLite and CPython (the standard Python interpreter) are all written in C. When you run a container, the kernel features underneath it, namespaces and cgroups, are C code.
From source to program
A C program goes through four stages:
- Preprocessing: handles
#include,#defineand conditional compilation (#ifdef). - Compilation: turns C into assembly code.
- Assembly: turns assembly into machine code, as object files (
.o). - Linking: combines object files and libraries into one executable.
Real world:
gcc -Eshows the preprocessed output andgcc -cstops at the object file. “Undefined reference” errors come from the linker, not the compiler. Docker images built withmakefollow exactly these stages.
The basics
- Data types:
char,int,float,double, with modifiersshort,longandunsigned. Sizes depend on the platform; on most current systemsintis 4 bytes, andsizeoftells you for sure. - Operators: arithmetic, relational, logical (
&&,||,!), bitwise (&,|,^,<<,>>), and the increment and decrement operators (++,--). - Control flow:
if/else,switch, and the loopsfor,whileanddo-while, plusbreakandcontinue. - Functions split a program into reusable parts. C passes arguments by value: the function gets a copy.
- Recursion is a function calling itself, with a base case to stop. Factorial and Fibonacci are the classic examples, and each call takes space on the call stack.
- Storage classes:
auto(the default for local variables),static(keeps its value between calls),extern(declared in another file) andregister.
Real world: bitwise operators are how Linux file permissions work:
chmod 755sets bits for owner, group and others, and the kernel checks them with&. Network code uses bit shifts to build and read IP addresses.
Arrays and strings
An array is a fixed-size block of elements of the same type, stored next to each other in memory. Indexes start at 0. A string in C is an array of characters ending with a null character '\0'. Functions from <string.h>, such as strlen, strcpy, strcmp and strcat, rely on that terminator.
C does not check array bounds. Writing past the end of an array silently overwrites whatever is next in memory: a buffer overflow.
Real world: buffer overflows have caused some of the most serious security bugs in history. Heartbleed (2014) was an over-read in OpenSSL, written in C, that leaked server memory, including private keys. This is why safer functions such as
strncpyandsnprintfexist, and why newer systems code is increasingly written in memory-safe languages such as Rust.
Pointers: the heart of C
A pointer is a variable that holds a memory address.
int x = 10;
int *p = &x; /* p holds the address of x */
*p = 20; /* change x through the pointer; x is now 20 */&gives the address of a variable;*follows a pointer to its value.- Pointers and arrays are closely linked: the array name acts as a pointer to its first element, and
a[i]is the same as*(a + i). - Call by reference: passing a pointer lets a function change the caller’s variable. The classic example is
swap(&a, &b). - Pointers to pointers, pointers to functions and arrays of pointers build on the same idea.
- A null pointer points nowhere. Following it, or a pointer to freed memory (a dangling pointer), crashes the program.
Real world: “Segmentation fault (core dumped)” is the operating system stopping a program that touched memory it does not own, almost always through a bad pointer. Function pointers are how the Linux kernel lets each file system and device driver plug in its own
readandwritecode.
Structures, unions and files
- A structure (
struct) groups variables of different types into one record, such as a student with a name, roll number and marks. - A union stores different types in the same memory, one at a time, to save space.
typedefgives a type a shorter name.- Enumerations (
enum) give names to integer constants. - File handling uses
FILE *withfopen,fprintf,fscanf,fread,fwriteandfclose.
Real world: network packet headers are defined as C structs whose fields line up exactly with the bytes on the wire. In Linux, “everything is a file”, so the same file functions read from disks, pipes and devices.
Dynamic memory
Arrays have a fixed size, but often you only know how much memory you need while the program runs. C gives you the heap:
malloc(n)allocates n bytes;callocallocates and zeroes;reallocresizes.free(p)returns the memory.
Every malloc needs a matching free. Forgetting it causes a memory leak; using memory after freeing it causes crashes and security holes.
Real world: a service whose memory use climbs steadily until it is killed usually has a leak. Tools such as Valgrind and AddressSanitizer find them. In Kubernetes, a leaking container eventually hits its memory limit and is OOMKilled.
Part 2: Data structures
A data structure is a way of organising data so that the operations you need are fast. Choosing the right one often matters more than any other optimisation.
Measuring efficiency: Big-O
Time complexity describes how running time grows with input size n, ignoring constants:
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Array access by index, hash table lookup |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Scanning a list |
| O(n log n) | Linearithmic | Merge sort, quick sort on average |
| O(n²) | Quadratic | Bubble sort, nested loops |
For a million items, O(log n) is about 20 steps, while O(n²) is a trillion.
Real world: a database query that runs fine on a test table and crawls in production is often an O(n) table scan that needed an index. A missing index is a Big-O problem.
Stacks
A stack is last in, first out (LIFO): you push onto the top and pop from the top. It can be built with an array or a linked list.
Classic uses are reversing data, checking balanced brackets, converting infix expressions (a + b * c) to postfix (a b c * +) and evaluating them, and recursion.
Real world: every running program has a call stack: each function call pushes a frame and each return pops it. A stack trace in an error log is a printout of that stack, and infinite recursion causes a “stack overflow”. The undo button in an editor and the back button in a browser are stacks.
Queues
A queue is first in, first out (FIFO): you enqueue at the rear and dequeue from the front. Variations:
- A circular queue reuses array space by wrapping around.
- A deque (double-ended queue) allows adding and removing at both ends.
- A priority queue serves the highest-priority item first, usually built with a heap.
Real world: message queues such as Kafka and RabbitMQ, print queues, CI build queues and Kubernetes’ scheduling queue are all queues. Operating systems use priority queues to decide which process runs next.
Linked lists
A linked list is a chain of nodes, each holding data and a pointer to the next node.
- Variants are singly linked, doubly linked (pointers both ways) and circular.
- Inserting or deleting is O(1) once you are at the right place, because you only change pointers; arrays must shift elements.
- Finding the kth element is O(n), because you must walk the chain. Arrays do this in O(1).
Real world: the Linux kernel uses linked lists throughout, for example to track processes. An LRU cache, as in Redis and memcached eviction, combines a hash table for O(1) lookup with a doubly linked list to keep items in order of use.
Trees
A tree is a hierarchy of nodes with a single root. In a binary tree, each node has at most two children.
- Traversals: inorder (left, root, right), preorder (root, left, right), postorder (left, right, root) and level order (breadth first).
- A binary search tree (BST) keeps smaller keys on the left and larger ones on the right. Search, insert and delete take O(log n) if the tree is balanced, but degrade to O(n) if it becomes a chain.
- Balanced trees such as AVL and red-black trees rotate nodes to stay balanced.
- A heap is a complete binary tree in which each parent is greater (max-heap) or smaller (min-heap) than its children. It is the usual way to build a priority queue, and the basis of heap sort.
Real world: file systems and the DOM of a web page are trees. Database indexes in MySQL and PostgreSQL are B+ trees, wide, shallow balanced trees designed for disks, which is why indexed lookups stay fast on billions of rows. Linux’s process scheduler uses a red-black tree.
Graphs
A graph is a set of vertices connected by edges, which may be directed or weighted. It is stored as an adjacency matrix or an adjacency list.
- BFS (breadth-first search) explores level by level, using a queue.
- DFS (depth-first search) goes as deep as possible first, using a stack or recursion.
- Shortest path algorithms (Dijkstra) and minimum spanning trees (Prim, Kruskal) are built on these.
Real world: Google Maps finds routes with shortest-path algorithms. Social networks are graphs of people. Package managers, build systems and Terraform order their work by sorting a dependency graph, and a “dependency cycle” error is a cycle in that graph.
Searching
- Linear search checks each element: O(n), works on any list.
- Binary search repeatedly halves a sorted array: O(log n).
Real world:
git bisectis binary search over your commit history: it finds the commit that introduced a bug in about log₂(n) steps, so even 1,000 commits take only about ten checks.
Sorting
| Algorithm | Average time | Notes |
|---|---|---|
| Bubble sort | O(n²) | Swaps neighbours; simple, slow |
| Selection sort | O(n²) | Picks the minimum each pass |
| Insertion sort | O(n²) | Fast for small or nearly sorted data |
| Merge sort | O(n log n) | Divide and conquer; stable; needs extra memory |
| Quick sort | O(n log n) | Partitions around a pivot; usually the fastest in practice; worst case O(n²) |
| Heap sort | O(n log n) | Uses a heap; no extra memory |
A stable sort keeps equal items in their original order, which matters when sorting by several keys.
Real world: real libraries combine these. Python and Java use Timsort, a hybrid of merge sort and insertion sort, and C++’s standard sort typically uses introsort, which starts as quick sort and switches to heap sort if it detects the worst case.
Hashing
A hash table stores key-value pairs. A hash function turns each key into an array index, giving O(1) average lookup, insert and delete.
When two keys land on the same index (a collision), it is resolved by chaining (a linked list at each slot) or open addressing (probing for the next free slot). When the table gets too full, it is resized and every key is rehashed.
Real world: Python dictionaries, Redis, DNS caches and the routing of requests to cache servers all rely on hashing. Consistent hashing, a variation, is how distributed caches and databases such as Cassandra spread keys across nodes so that adding a server moves only a small share of the data.
One-minute recap
| Topic | Key idea | You meet it in |
|---|---|---|
| C compilation | Preprocess, compile, assemble, link | gcc, make, linker errors |
| Pointers | Variables holding addresses | Segfaults, kernel drivers |
| Arrays and strings | Fixed size, no bounds checks | Buffer overflows, Heartbleed |
| Dynamic memory | malloc needs a matching free |
Memory leaks, OOMKilled pods |
| Big-O | How time grows with input | Missing database indexes |
| Stack | LIFO | Call stacks, undo, stack traces |
| Queue | FIFO | Kafka, CI queues, schedulers |
| Linked list | Nodes joined by pointers | LRU caches, kernel lists |
| Trees | Hierarchy; BST, heap, B+ tree | Database indexes, file systems |
| Graphs | Vertices and edges; BFS, DFS | Maps, dependency graphs |
| Searching | Linear O(n), binary O(log n) | git bisect |
| Sorting | O(n²) simple, O(n log n) fast | Timsort in Python and Java |
| Hashing | O(1) average lookup | Dictionaries, Redis, consistent hashing |
Next in Engineering Revisited: English.
Written by Claude, Anthropic’s AI assistant, as part of Engineering Revisited, a quick refresher of the B.Tech subjects one at a time.