DSA Quick Kit: quick revision, 20 bites

Data Structures: The Foundation

Organize data for efficiency.

A **data structure** is a way to store and organize data so that operations like insertion, deletion, and searching can be done efficiently. **Linear** structures (arrays, linked lists, stacks, queues) arrange elements sequentially, while **non-linear** structures (trees, graphs) arrange them hierarchically or in netwo…

Takeaway. Data structures are the blueprint for efficient data management.

Time and Space Complexity

Measure algorithm efficiency.

**Time complexity** measures how runtime grows with input size ($n$), while **space complexity** measures memory usage. They are expressed using asymptotic notations like **Big O**, **Omega (Ω)**, and **Theta (Θ)**.

Takeaway. Complexity analysis predicts performance as input scales.

Big O, Omega, and Theta

Three bounds of growth.

**Big O (O)** gives the worst-case upper bound. **Omega (Ω)** gives the best-case lower bound. **Theta (Θ)** gives a tight bound when both O and Ω match.

Takeaway. Big O for worst, Omega for best, Theta for exact growth.

Linear vs Binary Search

Sequential vs divide-and-conquer.

Takeaway. Binary search is faster but requires sorted data.

Binary Search Algorithm

Halve the search space.

Takeaway. Binary search repeatedly halves the range to find an element.

Stack: LIFO Principle

Last in, first out.

A **stack** follows **LIFO** (Last In, First Out). Main operations: **push** (add to top), **pop** (remove from top), and **peek** (view top without removal). Applications include function calls, expression evaluation, and undo operations.

Takeaway. Stack operations are constant time and LIFO-based.

Infix to Postfix Conversion

Use precedence and stack.

Convert an infix expression (e.g., A+B*C) to postfix (ABC*+) using operator precedence and associativity.

Takeaway. Postfix eliminates parentheses and simplifies evaluation.

Queue: FIFO Principle

First in, first out.

A **queue** follows **FIFO** (First In, First Out). Operations: **enqueue** (add to rear) and **dequeue** (remove from front). Variants: **circular queue** (reuses space), **priority queue** (elements have priority).

Takeaway. Queues manage data in order of arrival.

Stack vs Queue

LIFO vs FIFO.

Takeaway. Stack reverses order; queue preserves order.

Singly Linked List Basics

Nodes linked linearly.

A **singly linked list** consists of nodes, each with data and a pointer to the next node. Traversal goes one direction. Insertion and deletion are efficient if you have the pointer, but access is sequential.

Takeaway. Linked lists allow dynamic memory but no random access.

Singly vs Doubly Linked List

One pointer vs two.

Takeaway. Doubly lists are more flexible but use more memory.

Binary Tree Traversals

Visit nodes systematically.

**Preorder** (root, left, right), **Inorder** (left, root, right), **Postorder** (left, right, root). Inorder of a BST gives sorted order.

Takeaway. Traversal order determines the sequence of node visits.

Binary Search Tree (BST)

Sorted structure for fast search.

A **BST** is a binary tree where left child < parent < right child. Operations: **insertion**, **deletion**, and **searching** average O(log n) for balanced trees.

Takeaway. BST enables efficient sorted data operations.

AVL Tree Rotations

Balance the tree.

An **AVL tree** is a self-balancing BST. When imbalance occurs, rotations fix it: **LL**, **RR**, **LR**, **RL**. Each rotation maintains BST property and balances height.

Takeaway. Rotations keep AVL height O(log n).

B Tree vs B+ Tree

Multi-way search trees.

Takeaway. B+ tree has all data in leaves, enabling faster range queries.

Sorting Algorithms Complexity

Know the best and worst.

Takeaway. Merge and Heap are stable O(n log n) worst-case; Quick is fast but risky.

Quick Sort Steps

Partition and conquer.

Takeaway. Quick sort is efficient on average but O(n²) in worst case.

Merge Sort Steps

Divide, conquer, merge.

Takeaway. Merge sort guarantees O(n log n) but uses extra space.

Hashing Fundamentals

Direct access via keys.

**Hashing** maps keys to indices using a **hash function**. It enables O(1) average search, insert, delete. **Collisions** occur when two keys map to same index; resolved by **chaining** or **open addressing**.

Takeaway. Hashing provides near-constant-time operations with good hash functions.

BFS vs DFS

Level order vs depth first.

Takeaway. BFS finds shortest path in unweighted graphs; DFS uses less memory on sparse graphs.