Non-Linear Data Structures

Non-Linear Data Structures is a core building block of the Data Structures & Algorithms toolkit in C. This chapter walks you through the definition, the C-flavoured implementation, and the Big-O trade-offs you need to discuss in any interview.

Non-Linear Data Structures — Trees, graphs, heaps — branching, hierarchical shapes.

1. It's asked in every major coding interview (DSA is non-negotiable for a CS role).
2. It shows up in real production systems — databases, compilers, OS schedulers, routers.
3. Mastering it teaches you to reason about memory and pointers — the skills that transfer to every lower-level language.
4. It gives you vocabulary ("this is O(log n)", "we'll hash it") that unlocks working with senior engineers.

1. Where this structure lives in memory (stack / heap / contiguous / linked).
2. The operations it supports (insert, delete, search, traverse) and the cost of each.
3. Its Big-O time AND space in average / worst cases.
4. When to prefer it vs a neighbouring structure (array vs linked list, stack vs queue, BST vs hash).

c Run in compiler
#include <stdio.h>
int main(void) {
    printf("Hello, Data Structures with C!\n");
    return 0;
}

(compile and run in the Codekilla compiler — output will vary by the input you provide)

1. Always initialise pointers to NULL before using them.
2. Every malloc needs a matching free — leaks bite in long-running programs.
3. Test the edge cases FIRST: empty, single element, full capacity.
4. Worst case is what interviewers ask about — know it cold.

1. Gives the algorithm the right shape for the data — speed gains that beat any micro-optimisation.
2. Makes the code self-documenting (Stack s communicates LIFO to every reader).
3. Lets you reason mathematically about scaling before you ever run a benchmark.
4. Transferable knowledge — the pattern shows up in Java, Python, JavaScript — everywhere.

• Non-Linear Data Structures is part of the standard DSA vocabulary — be fluent.
• Know the Big-O of every operation BEFORE you need it.
• Choose the structure that matches the access pattern of your data.
• Walk through each operation on paper — pointer arithmetic is easier on paper than in your head.
• Interviewers reward clean, bug-free code over clever tricks.

1. Implement non-linear data structures in C from scratch — no libraries.
2. Add a unit test covering empty / one-element / many-element cases.
3. Benchmark it for n = 10³, 10⁴, 10⁵ and plot the runtime.
4. Write an interview-style explanation (< 90 seconds) for a friend.

• Hand-trace every pointer diagram before coding — pointer bugs are hard to debug after the fact.
• Use assert() liberally — it turns pointer mistakes into clear crashes.
• Draw the structure (boxes + arrows) before you write the first line of C.
• If you get stuck, explain what you want to happen out loud — the solution usually drops out.