Data Structures Basics: Concepts, Formulas, and Clear Examples

DS basics in aptitude cover complexity, array vs linked list, stack/queue, tree terminology, hash idea, and sorting concept—not implementation coding. You compare time/space and pick the right structure for a scenario.

Expect MCQs on LIFO/FIFO, inorder/preorder/postorder, BST property, heap max/min, and Big-O of search in sorted vs unsorted data.

Complexity notation

Big-O (upper bound)

$$T(n) = O(f(n)) \text{ if growth } \le k\cdot f(n)$$

• O(1) access by index in array; O(n) search unsorted array.
• Sorted array search O(log n) binary search.

Linear structures

• Stack: push/pop O(1) amortized; applications—parentheses, DFS.
• Queue: enqueue/dequeue O(1); BFS, scheduling.
• Singly linked list: insert at head O(1); search O(n).

Trees

• BST: left < root < right; inorder gives sorted sequence.
• Complete binary tree height h: nodes ≤ $2^{h+1}-1$.

Example — BST check

Inorder traversal 2,5,9 → could be BST output. If 9,2,5 appears, not valid BST inorder.

Hashing (conceptual)

Key → hash function → bucket; collision resolution: chaining, open addressing. Average O(1) lookup ideal; worst O(n) if all collide.

Sorting awareness

• Comparison sort lower bound O(n log n); counting sort O(n+k) for small range.
• Stable sort preserves equal element order.

Choosing a DS

• Frequent insert/delete at both ends → deque.
• Priority scheduling → heap.

Step-by-step method for exam questions

1. Identify operation mix: search, insert, delete, min/max.
2. Map to complexity needs.
3. Eliminate structures violating constraints (need sorted order → BST or sorted array).
4. Recall LIFO/FIFO or traversal rule for tree questions.
5. Pick option; verify worst-case if question asks.

Formula cheat sheet

Frequently asked questions

Implement code in exam?

Rare—pseudo and complexity dominate.

Graph vs tree?

Tree: connected acyclic; graph may have cycles.

Heap vs BST for min?

Heap O(1) peek min; BST O(h) min at left spine.

Practice on this platform

Use 4 practice sets (10 MCQs, detailed solution after each answer) and 2 timed mocks (20 minutes) on this topic to convert formulas into speed and accuracy.