Part A (2 marks each)

Q1. Define a linear data structure with one example. A data structure in which elements are arranged sequentially — each (except first/last) has exactly one predecessor and one successor. Example: an array, a fixed-size sequence in contiguous memory with $O(1)$ index access.

Q2. Give an example of a non-linear data structure and one use. A tree — hierarchical structure with a root and children. Used in databases (B-tree index), file systems, decision-tree machine-learning models.

Q3. What is the difference between a stack and a queue?

• Stack — LIFO (Last-In-First-Out); operations at the top.
• Queue — FIFO (First-In-First-Out); enqueue at back, dequeue at front.

---

Part B (20 marks)

Q. Give an overview of linear and non-linear data structures. Discuss the main types of each, their operations and time complexities, with examples and use-cases.

Linear Data Structures.

Elements arranged sequentially; each has one predecessor / successor.

1. Array.

• Fixed-size, contiguous memory.
• Index access $O(1)$.
• Insert / delete $O(n)$ (shift).
• Use: storing scores, numerical computation (NumPy arrays).

2. Linked List.

• Nodes scattered, connected by pointers.
• Insert / delete at known node $O(1)$.
• Random access $O(n)$.
• Variants: singly, doubly, circular.
• Use: dynamic data with frequent insertions/deletions; LRU caches.

3. Stack (LIFO).

• Push / pop at top, both $O(1)$.
• Use: function-call stack, undo/redo, balanced parentheses, DFS.

4. Queue (FIFO).

• Enqueue at back, dequeue at front, both $O(1)$.
• Use: BFS, scheduling, IO buffers.
• Variants: deque (double-ended), priority queue.

Non-Linear Data Structures.

Elements form a hierarchy or network.

1. Tree. Root + child nodes.

• Binary Search Tree (BST) — $O(\log n)$ search/insert if balanced.
• AVL / Red-Black trees — self-balancing.
• Heap — complete binary tree; root is min/max; priority queues.
• B-Tree / B+ Tree — multi-way; backbone of databases (MySQL InnoDB index).
• Trie — prefix tree for strings; autocomplete, IP routing.

2. Graph. Vertices and edges.

• Represented by adjacency matrix ($O(V^2)$) or adjacency list ($O(V + E)$).
• Use: social networks, knowledge graphs, road networks, dependency graphs.

3. Hash Table. Key → value via hash function.

• Average $O(1)$ lookup; worst $O(n)$.
• Collision handling: chaining, open addressing.
• Use: Python dict, Java HashMap, caches.

Time complexity cheat sheet.

DS	Access	Search	Insert	Delete
Array	$O(1)$	$O(n)$	$O(n)$	$O(n)$
Sorted Array	$O(1)$	$O(\log n)$	$O(n)$	$O(n)$
Linked List	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Stack/Queue	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Hash Table	–	$O(1)$ avg	$O(1)$ avg	$O(1)$ avg
Balanced BST	–	$O(\log n)$	$O(\log n)$	$O(\log n)$
Heap	–	$O(n)$	$O(\log n)$	$O(\log n)$

Choosing a DS — examples.

Need	Best DS
Fast random access	Array
Frequent insert/delete in the middle	Linked list
LIFO history	Stack
FIFO queue	Queue
Fast key lookup	Hash table
Sorted with fast range queries	Balanced BST
Always extract min/max	Heap
Word autocomplete	Trie
Networks of relationships	Graph

Why it matters in Data Science.

• pandas DataFrame uses arrays + hash tables under the hood.
• Graph algorithms power knowledge graphs and recommenders.
• Heaps drive priority-based ML training schedulers.
• B+ Trees power SQL indexes that speed feature lookups.

Picking the right data structure can convert an $O(n^2)$ problem into $O(n \log n)$ — often the difference between a working ML pipeline and one that times out.