I built a terminal-based interactive DSA library in C (~4000 lines) — the graph chapter nearly broke me, here's why
Project: full DSA library in C, terminal-based and interactive. Linked lists (singly, doubly, circular), stacks, queues, BST with traversals, graphs (adjacency matrix + adjacency list, DFS/BFS), infix-to-postfix + postfix evaluation, hashing, sorting, searching. Manual memory management throughout, Valgrind-clean.
GitHub: https://github.com/darshan2456/C_DSA_interactive_suite
The linked list and tree chapters were hard but survivable. Linked list reversal in-place taught me pointer discipline the hard way — silent heap corruption from one misplaced assignment is a very effective teacher. BST traversals broke and then permanently fixed my mental model of the call stack during recursion.
The infix-to-postfix chapter was different — not painful, but it's where I first understood what composing abstractions actually means in practice. I didn't use a standalone stack. I built a stack on top of my linked list implementation, then used that stack to implement the Shunting Yard algorithm. So the call chain was: algorithm → stack operations → linked list pointer manipulation — all code I wrote, all the way down. When it worked, I could trace exactly why it worked at every layer. That kind of end-to-end ownership over your abstractions doesn't happen when a language hands them to you.
But the graph chapter was a different category of hard entirely, specifically adjacency list representation.
Adjacency matrix is clean — a 2D array, index by vertex, done. I was comfortable.
Then adjacency list: conceptually it's just each vertex storing a list of its neighbors. Simple enough. In C it means an array of linked lists, where each list is dynamically allocated and grown independently. Suddenly you have:
- `struct Node** adjList` — a pointer to an array of pointers to linked list heads
- dynamic allocation for every single edge insertion
- pointer-to-pointer manipulation for list insertions
- freeing a graph means iterating every list, freeing every node, then freeing the array itself — in the right order
And the edge cases multiply fast. What happens when you insert a duplicate edge? What if the vertex index is out of bounds? What does a partial free look like when malloc fails halfway through building a graph?
It also made the complexity tradeoff concrete in a way Big-O notation alone never did. O(V²) space and traversal on a sparse adjacency matrix isn't just inefficient on paper — you feel it when you've implemented both.
Feedback on the implementation very welcome — especially around the graph memory management and whether my adjList structure could be cleaner.