Data Structures

Question 1

Array ( Java )

Answer 1

Definition:
A contiguous block of memory storing elements of the same type, enabling random access by index.

• Access: O(1)
• Search: O(n)
• Insertion/Deletion: O(n) (in the worst case)
• Space: O(n) (fixed size).

Question 2

Dynamic Array (e.g., Python list)

Answer 2

Definition:
A resizable array that automatically reallocates memory when capacity is exceeded.

• Access: O(1) amortized
• Search: O(n)
• Insertion (append): O(1) amortized, can be O(n) worst case
• Space: O(n).

Question 3

Singly Linked List

Answer 3

Definition:
Each node stores data and a pointer to the next node.

• Access/Search: O(n)
• Insertion/Deletion at head: O(1)
• Space: O(n).

Question 4

Doubly Linked List

Answer 4

Definition:
Each node stores pointers to both its next and previous nodes.

• Access/Search: O(n)
• Insertion/Deletion given a node reference: O(1)
• Space: O(n).

Question 5

Stack

Answer 5

Definition:
A LIFO (Last In, First Out) structure supporting push and pop at one end.

• Push/Pop/Peek: O(1)
• Space: O(n)
• Commonly used for function calls, undo operations, expression parsing.

Question 6

Queue

Answer 6

Definition:
A FIFO (First In, First Out) structure supporting enqueue (add) at one end and dequeue (remove) at the other.

• Enqueue/Dequeue: O(1)
• Space: O(n).

Question 7

Hash Table

Answer 7

Definition:

Question 8

Binary Search Tree (BST)

Answer 8

Definition:

Question 9

Heap (Min-Heap/Max-Heap)

Answer 9

Definition:
A complete binary tree that satisfies the heap property (parent < children in a min-heap).

• Peek (min/max): O(1)
• Insert/Remove: O(log n)
• Space: O(n)
• Often used in priority queues.

Question 10

Trie

Answer 10

Definition:
A prefix tree that stores strings character by character in nodes.

• Insert/Search/Delete: O(k), where k is the string length
• Space: O(n * k) in worst case
• Used in auto-completion, spell-checking, IP routing.

Question 11

Red-Black Tree

Answer 11

Definition:
A generalization of BST where each node can have multiple children, commonly used in databases/filesystems.

• Search/Insert/Delete: O(log n)
• Space: O(n)
• Minimizes disk access by storing multiple keys per node.

Question 12

Disjoint Set (Union-Find)

Answer 12

Definition:
Manages elements partitioned into disjoint sets and efficiently merges them.

• Union/Find: ~O(α(n)), where α is the inverse Ackermann function
• Space: O(n)
• Useful in Kruskal’s MST and connectivity problems.