Data Structures

Question 1

What is a linked list, and what are its key operations?

Answer 1

A linked list is a linear data structure with nodes containing data and a pointer to the next node. Key operations: insertion (O(1)), deletion (O(1) with pointer), traversal (O(n)).

Question 2

What is a binary search tree (BST)?

Answer 2

A tree where each node’s left child has a smaller value, and right child has a larger value. Supports search, insertion, and deletion in O(log n) average case, O(n) worst case if unbalanced.

Question 3

What is a hash table, and how does it handle collisions?

Answer 3

A hash table maps keys to values using a hash function. Collisions are resolved via chaining (linked lists at each bucket) or open addressing (probing).

Question 4

What is the difference between a stack and a queue?

Answer 4

Stack is LIFO (Last In, First Out); supports push/pop. Queue is FIFO (First In, First Out); supports enqueue/dequeue.

Question 5

What is a heap, and what are its types?

Answer 5

A heap is a complete binary tree satisfying the heap property. Max-heap: parent ≥ children. Min-heap: parent ≤ children. Used in priority queues and sorting (heapsort).