Theory
One question, two shapes
Two records the canteen keeps:
- Today's token list: 1, 2, 3, 4... every token has exactly one before it and one after it.
- The menu board: Menu splits into Snacks, Meals, Drinks; Meals splits into three thalis.
Ask "what comes after this?" The token list gives one answer. The menu gives three.
That single difference, one successor or many, is the official dividing line of all non-primitive data structures.
Theory
A queue vs a family tree
In the serving line, you have exactly one person ahead and one behind: pure sequence.
In your family tree, your grandfather connects to several children, each connecting to several more: pure branching.
Nobody draws a family as a queue, and nobody serves customers by family tree. Structures are shapes, and shapes must match the relationships they hold.
Theory
The two families, formally
Linear data structure: elements form a single sequence. Every element (except the first and last) has exactly one predecessor and one successor. You can traverse everything in one straight pass.
Examples: array, stack, queue, linked list.
Non-linear data structure: elements attach hierarchically or as a network; one element may connect to many others. Traversal needs a strategy (which branch first?).
Examples: tree, graph.
At a glance
The exam table
| Aspect | Linear | Non-linear |
|---|---|---|
| Arrangement | Single sequence | Hierarchy or network |
| Neighbours | One predecessor, one successor | One element, many connections |
| Traversal | One straight pass | Needs a strategy (DFS, BFS) |
| Implementation | Simpler | More complex |
| Examples | Array, stack, queue, linked list | Tree, graph |
| Typical use | Token lists, undo, schedules | File systems, maps, networks |
Quiz
Which group contains ONLY linear data structures?
- Array, linked list, stack, queue
- Array, tree, stack, queue
- Stack, queue, graph, array
- Tree, graph, linked list, array
Show the answer
Array, linked list, stack, queue
The four linear structures are exactly array, linked list, stack and queue: each keeps one sequence. Every other option smuggles in a tree or a graph, the two non-linear members. Examiners build this question by hiding one branching structure inside a linear list; scan for tree/graph and the wrong options eliminate themselves.
Think first
The tricky case
A student stores a tree inside an array (parent at index i, children at 2i and 2i+1, the classic heap layout). The data now sits in a linear array. Before tapping: is the structure linear or non-linear, and why?
Show the answer
Non-linear. Classification follows the logical relationships, not the storage medium: each parent still has up to two children, so elements still have multiple successors. The array is just the shelf it is kept on. This distinction (logical structure vs physical storage) is precisely the trap exams set with this question, and heaps in later semesters rely on it.
Watch out
Two classification slips
Linked list feels branchy because of arrows in diagrams, but every node points to exactly ONE next node: linear.
A tree stored in an array stays non-linear (see above). The test that never fails: count the successors an element can have. One at most: linear. Possibly many: non-linear. Apply the test instead of memorizing lists and no rephrased exam question can shake you.
Theory
Why the split matters ahead
Everything remaining in BCA304 (stack applications, queues in three flavours) lives on the linear side: master sequences now. The non-linear side (trees, graphs) arrives in later semesters carrying databases, file systems and Google-Maps-style routing. The one-successor test you learned today keeps working there too.
Summary
Key takeaways
- Linear: one sequence, each element with at most one predecessor and one successor.
- Non-linear: hierarchy or network, one element may connect to many.
- Linear members: array, stack, queue, linked list. Non-linear: tree, graph.
- Traversal: one straight pass vs strategy-based (DFS/BFS).
- Classification follows logical relationships, not how the data is physically stored.
- Memory hook: serving line vs family tree.