2. Why do we use Data Structure?

Array: [10] [20] [30] [40]
Index:   0    1    2    3

For example:

Dynamic memory allocation is the process of allocating and deallocating memory during program execution according to the program's requirements.

• malloc() – Allocates a block of memory.

• calloc() – Allocates memory and initializes it to zero.

• realloc() – Changes the size of previously allocated memory.

• free() – Releases allocated memory.

Example: In C++, dynamic memory can be allocated using new and released using delete. Containers such as vector manage memory automatically.

┌─────────┬─────────┐
│  Data   │  Next   │
└─────────┴─────────┘

Linked List Structure

 [10 | •] → [20|.] -> [30|NULL] 

Key Features

NULL ← [Prev | Data | Next] ↔ [Prev | Data | Next] → NULL

Advantages of Linked Lists

• Dynamic size

• Efficient insertion and deletion when the required position is known

• Does not require contiguous memory

• Easy implementation of stacks and queues

Disadvantages:

• No direct/random access

• Extra memory required for pointers

• Sequential traversal is required

21. What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In First Out) principle.

The last element inserted is the first element removed.

Key Features

• Follows LIFO order
• Insertion and deletion happen at the top
• Only one end is accessible

Basic Operations

Example

       ┌────┐
       │ 30 │ ← Top
       ├────┤
       │ 20 │
       ├────┤
       │ 10 │
       └────┘
        LIFO
  Last In → First Out

A stack can be implemented using:

• Array
• Linked List

Applications

• Expression evaluation
• Undo / Redo
• Function calls
• Recursion
• Balanced parentheses

22.How do you Reverse a Singly Linked List?

A singly linked list can be reversed by changing the direction of its pointers so that each node points to its previous node.

Approach:

Before:10 → 20 → 30 → NULL

After:
30 → 20 → 10 → NULL

A stack supports operations that allow elements to be added, removed, and accessed following the LIFO principle.

1. Push

Adds an element to the top of the stack.

Time Complexity: O(1)

2. Pop

Removes the top element.

Time Complexity: O(1)

3. Peek / Top

Returns the top element without removing it.

Time Complexity: O(1)

4. isEmpty

Checks whether the stack is empty.

5. isFull

Checks whether the stack is full.

This is mainly applicable to fixed-size array implementations.

Example

Stack = [10, 20, 30]

  Push(40)
      ↓
[10, 20, 30, 40]

   Pop()
      ↓
[10, 20, 30]

   Peek()
      ↓
     30

24. What are the Applications of Stack?

Stacks are useful whenever data needs to be processed in a LIFO manner.

1. Function Call Management

The stack maintains the call stack and stores function calls and local variables.

It is especially important for recursion.

2. Expression Evaluation

Stacks are used for:

• Infix
• Postfix
• Prefix

expressions.

3. Parentheses Matching

Stacks help check whether expressions contain balanced parentheses.

4. Undo and Redo

Text editors use stacks to track changes and support undo / redo operations.

5. Backtracking

Used in:

• Maze solving
• DFS
• Puzzles

6. Reversing Data

A stack can be used to reverse strings or sequences.

7. Browser Navigation

Stacks can support back and forward navigation.

Key Idea:
Whenever you need to reverse, backtrack, or process the latest item first, think about a Stack.

25. What is a Queue?

A queue is a linear data structure that follows the FIFO (First In First Out) principle.

The element inserted first is the first element removed.

Key Features

• Follows FIFO order
• Insertion happens at the rear
• Deletion happens from the front
• Has two ends: front and rear

Basic Operations

• Enqueue – Add an element at the rear
• Dequeue – Remove an element from the front
• Front / Peek – View the front element
• isEmpty – Check whether queue is empty
• isFull – Check whether queue is full

Example

 Front                 Rear
  ↓                     ↓
[10] → [20] → [30] → [40]
  ↑
First In              Last In

FIFO → First In First Out

• CPU scheduling
• Printer queue
• Breadth First Search (BFS)
• Server request handling

26. Why do we use Queue?

A queue is used when data needs to be processed in a First In First Out (FIFO) manner.

Key Reasons

1. FIFO Processing

Ensures fair and ordered processing.

The first inserted element is handled first.

2. Efficient Operations

• Enqueue → O(1)
• Dequeue → O(1)

3. Scheduling and Resource Management

Used in:

• CPU scheduling
• Task management

4. Handling Requests

Useful when requests arrive continuously.

Examples:

• Server requests
• Printer queues

5. Traversal Algorithms

Queues are used in Breadth First Search (BFS) to process nodes level by level.

Applications

• Task scheduling
• Printer management
• Server requests
• BFS

Remember:
Queue → FIFO → First In, First Out

27. What is the Difference Between Stack and Queue?

Queues are classified based on how elements are inserted, removed, and organized.

1. Simple Queue

Follows the standard FIFO principle.

• Insertion → Rear
• Deletion → Front

2. Circular Queue

The last position connects back to the first position.

It provides better memory utilization.

3. Priority Queue

Elements are processed based on their priority rather than simply their insertion order.

It can follow:

• Min-priority
• Max-priority

4. Deque

A Double-Ended Queue allows insertion and deletion from both ends.

Comparison

29. What is a Circular Queue?

A circular queue is a type of queue where the last position is connected back to the first position, forming a circular structure.

It follows FIFO while making better use of available memory.

Key Features

• Follows FIFO
• Rear can wrap around to the front
• Provides better memory utilization
• Reduces wasted space

Working Principle

When the rear reaches the last index, it can move back to the first index.

This is commonly handled using the modulo operation.

Example

For a queue of size 5:

 [0] [1] [2] [3] [4]  ↑               │
  └───────────────┘

If rear = 4, the next available position can be 0.

Advantages

• Better memory utilization
• Reuses empty positions
• Suitable for fixed-size queues

Disadvantages

• Slightly more complex
• Requires careful handling of front and rear

30. What is a Deque (Double-Ended Queue)?

A deque is a linear data structure in which insertion and deletion can be performed from both ends.

Key Features

• Insertion from front and rear
• Deletion from front and rear
• More flexible than a simple queue
• Can behave like both a stack and queue

Types of Deque

1. Input-Restricted Deque

• Insertion → One end only
• Deletion → Both ends

2. Output-Restricted Deque

• Deletion → One end only
• Insertion → Both ends

Basic Operations

• InsertFront
• InsertRear
• DeleteFront
• DeleteRear

Example

       Front              Rear
          ↓                  ↓
       [10] [20] [30] [40]
          ↑                  ↑
       Delete             Delete
       Insert             Insert

• Sliding window problems
• Palindrome checking
• Undo / Redo
• Task scheduling

31. What is Recursion?

Recursion is a programming technique in which a function calls itself to solve a problem by breaking it into smaller subproblems.

Key Features

• A function calls itself
• Problem is divided into smaller instances
• Must have a base case
• Uses the call stack

Components

1. Base Case

The condition where recursion stops.

2. Recursive Case

The part where the function calls itself with a smaller input.

Example: Factorial

 factorial(n)      │
      ├── Base Case: n = 0
      │       ↓
      │       1
      │
      └── Recursive Case
              ↓
       n × factorial(n-1)

5! = 5 × 4 × 3 × 2 × 1

• Simplifies complex problems
• Useful in divide and conquer
• Can make code cleaner

Disadvantages

• Uses extra call stack memory
• Can be slower than iteration
• Risk of stack overflow

32. What is the Difference Between Recursion and Iteration?

Both recursion and iteration can be used to repeat operations, but they work differently.

• Recursion → Function calls itself
• Iteration → Uses loops

Key Differences

Example

Recursion:

fact(n) = n × fact(n-1)

Iteration:

for i = 1 to n
    multiply result by i

When to Use?

Use Recursion when:

• Problem naturally divides into smaller subproblems
• Working with trees
• Using divide and conquer

Use Iteration when:

• Performance is important
• Memory usage should be minimized
• Problem involves simple repetition

33. What is Linear Search?

Linear search is a simple searching algorithm that checks each element sequentially until the target is found or the list ends.

Key Features

• Checks elements one by one
• Works on sorted and unsorted data
• Simple to implement

Algorithm Steps

1. Start from the first element
2. Compare it with the target
3. If a match is found → return the index
4. Otherwise move to the next element
5. Continue until the target is found or the array ends

Example

Array:  [10] [20] [30] [40]
Index:    0    1    2    3
                  ↑
                Target

Target = 30

10 → No
20 → No
30 → Found at index 2

Time Complexity

• Best Case: O(1)
• Worst Case: O(n)

Advantages

• Simple
• Works on unsorted data
• Requires no extra memory

Disadvantages

• Slow for large datasets
• Less efficient than binary search for sorted data

34. What is Binary Search?

Binary search is an efficient searching algorithm that finds an element in a sorted array by repeatedly dividing the search space in half.

Key Features

• Works only on sorted data
• Uses divide and conquer
• Reduces the search space by half

Algorithm

1. Find the middle element
2. If target = middle → Found
3. If target < middle → Search left half
4. If target > middle → Search right half
5. Repeat until found or search space becomes empty

Example

[10] [20] [30] [40] [50]
            ↑
          Middle

Target = 30

The middle element is 30, so the target is found immediately.

Flow

• Best Case: O(1)
• Worst Case: O(log n)

Advantages

• Much faster for large sorted datasets
• Efficient searching

Disadvantages

• Requires sorted data
• More complex than linear search

35. What is Bubble Sort?

Bubble sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order.

The largest element gradually bubbles up to the end after each pass.

Algorithm Steps

1. Compare adjacent elements
2. Swap if they are in the wrong order
3. Continue through the array
4. Repeat multiple passes
5. Stop when no swaps are required

Example

Array:

[5, 3, 2, 4]

Pass 1:

5, 3 → swap → [3, 5, 2, 4]

5, 2 → swap → [3, 2, 5, 4]

5, 4 → swap → [3, 2, 4, 5]

Now 5 is in its correct position.

Visual

[5, 3, 2, 4]
 ↑  ↑
Compare

[3, 5, 2, 4]
    ↑  ↑
   Compare

[3, 2, 5, 4]
       ↑  ↑
      Swap

[3, 2, 4, 5]

Time Complexity

• Best Case: O(n)
• Worst Case: O(n²)

Advantages

• Simple to understand
• Easy to implement
• In-place

Disadvantages

• Inefficient for large datasets
• Performs many comparisons and swaps

36. What is Selection Sort?

Selection sort repeatedly selects the smallest element from the unsorted part and places it at the correct position.

Key Features

• Divides array into sorted and unsorted parts
• Selects the minimum element
• Performs fewer swaps than bubble sort

Algorithm Steps

1. Assume the first unsorted element is the minimum
2. Compare it with the remaining elements
3. Find the actual minimum
4. Swap it into the correct position
5. Repeat for the remaining elements

Example

[5, 3, 2, 4]

Pass 1:

Minimum = 2

[2, 3, 5, 4]

Pass 2:

Minimum = 3

[2, 3, 5, 4]

Pass 3:

Minimum = 4

[2, 3, 4, 5]

Time Complexity

• Best Case: O(n²)
• Worst Case: O(n²)

Advantages

• Simple to implement
• Fewer swaps than bubble sort

Disadvantages

• Inefficient for large datasets
• Does not benefit much from already sorted data

37. What is Insertion Sort?

Insertion sort builds the sorted array one element at a time by inserting each element into its correct position.

Key Features

• Builds a sorted portion gradually
• Inserts each element into its correct position
• Works well for small or nearly sorted datasets

Algorithm Steps

1. Start from the second element
2. Compare it with previous elements
3. Shift larger elements to the right
4. Insert the element at the correct position
5. Repeat

Example

[5, 3, 2, 4]

Insert 3:

[3, 5, 2, 4]

Insert 2:

[2, 3, 5, 4]

Insert 4:

[2, 3, 4, 5]

Time Complexity

• Best Case: O(n)
• Worst Case: O(n²)

Advantages

• Simple to implement
• Good for small datasets
• Efficient for nearly sorted arrays
• In-place

Disadvantages

• Inefficient for large datasets
• Can require many shifts

38. What is Merge Sort?

Merge sort is a divide and conquer sorting algorithm that divides an array into smaller parts, sorts them, and then merges the sorted parts.

Key Features

• Uses divide and conquer
• Recursively divides the array
• Merges sorted subarrays
• Stable sorting algorithm

Working

1. Divide the array into two halves
2. Recursively sort each half
3. Merge the sorted halves
4. Continue until the entire array is sorted

Time Complexity

• Best Case: O(n log n)
• Worst Case: O(n log n)

Space Complexity

• O(n) extra space

Advantages

• Efficient for large datasets
• Stable
• Guaranteed O(n log n)

Disadvantages

• Requires extra memory
• Not in-place

39. What is Quick Sort?

Quick sort is a divide and conquer sorting algorithm that selects a pivot element and partitions the array around it.

Elements smaller than the pivot go to one side, while larger elements go to the other side.

Key Features

• Uses divide and conquer
• Selects a pivot
• Partitions the array
• Generally performed in-place

Algorithm Steps

1. Choose a pivot
2. Partition the array
3. Elements smaller than pivot → left
4. Elements larger than pivot → right
5. Recursively sort both sides

Example

Array: [5, 3, 2, 4]
Pivot = 5
[3, 2, 4] [5]

Sort left:
[2, 3, 4] [5]

Final:
[2, 3, 4, 5]

Time Complexity

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n²)

Worst case can occur when the pivot is poorly chosen.

Space Complexity

• O(log n) recursion stack in the typical balanced case

Advantages

• Fast in practice
• Good cache performance
• Generally in-place

Disadvantages

• Worst case can be O(n²)
• Performance depends on pivot selection

40. What is Shell Sort?

Shell sort is an improved version of insertion sort that compares elements that are far apart using a gap sequence.

Key Features

• Based on insertion sort
• Uses a gap
• Compares distant elements
• Gradually reduces the gap
• Final gap becomes 1

Algorithm Steps

1. Choose an initial gap
2. Compare elements that are gap positions apart
3. Perform insertion-sort-like operations
4. Reduce the gap
5. Repeat until gap = 1

Example

Array: [5, 3, 2, 4]

Gap = 2
   ↓
Compare elements 2 positions apart

Reduce gap
   ↓
Gap = 1

Perform final insertion sort
    ↓
[2, 3, 4, 5]

Time Complexity

• Best Case: Depends on the gap sequence
• Worst Case: O(n²)

Advantages

• Faster than insertion sort for medium-sized datasets
• Reduces shifts and swaps
• In-place

Disadvantages

• Performance depends on the gap sequence
• Not as efficient as advanced algorithms for large datasets

41. What is a Tree Data Structure?

A tree is a non-linear data structure that organizes data in a hierarchical structure using nodes and edges.

A node can have multiple child nodes.

Key Features

• Hierarchical structure
• Consists of nodes and edges
• Has a root node
• Nodes can have zero or more children
• Standard trees contain no cycles

Basic Terminology

• Root → Topmost node
• Parent → Node that has children
• Child → Node derived from another node
• Leaf Node → Node with no children
• Subtree → Tree formed from a node and its descendants

Example

• Root → A
• Children of A → B, C
• Leaf Nodes → D, E, C

Types of Trees

• Binary Tree
• Binary Search Tree
• Heap
• Trie

Applications

• File systems
• Database indexing
• Expression trees
• Searching and sorting

42. What is a Binary Tree?

A binary tree is a type of tree in which each node can have at most two children.

These are called:

• Left child
• Right child

Key Features

• Maximum two children per node
• Children are called left and right
• Hierarchical structure
• Contains no cycles

Example

• Root → A
• Left Child → B
• Right Child → C
• Leaf Nodes → D, E, C

Types of Binary Trees

• Full Binary Tree → Every node has 0 or 2 children
• Complete Binary Tree → All levels filled except possibly the last
• Perfect Binary Tree → All levels completely filled
• Balanced Binary Tree → Height is kept relatively small

Applications

• Binary Search Trees
• Heap
• Expression trees
• Searching and sorting

43. What is a Binary Search Tree (BST)?

A Binary Search Tree (BST) is a binary tree where each node follows a specific ordering property:

• Left subtree → Values smaller than the node
• Right subtree → Values greater than the node

BST Property

For a node with value X:

Example

For node 50:

• Left → Values < 50
• Right → Values > 50

Key Features

• Maximum two children
• Maintains sorted order
• Supports searching, insertion, and deletion
• Standard BSTs generally do not allow duplicate values

Time Complexity

Worst case occurs when the tree becomes skewed.

Advantages

• Efficient searching
• Maintains data in sorted order

Disadvantages

• Can become unbalanced
• Worst-case performance becomes O(n)

44. What is Tree Traversal?

Tree traversal is the process of visiting all nodes of a tree in a specific order.

Tree traversal is mainly divided into:

1. Depth First Traversal (DFS)
2. Breadth First Traversal (BFS)

Depth First Traversal

DFS explores nodes deep into the tree before backtracking.

It includes:

• Inorder → Left → Root → Right
• Preorder → Root → Left → Right
• Postorder → Left → Right → Root

Breadth First Traversal

Also called Level Order Traversal.

It visits nodes level by level and uses a queue.

Example

Applications

• Searching tree nodes
• Expression evaluation
• File system traversal
• Tree-based algorithms

45. What are the Types of Tree Traversals?

Tree traversal methods determine the order in which nodes are visited.

They are mainly classified into:

• Depth First Traversal (DFS)
• Breadth First Traversal (BFS)

1. Inorder Traversal

Left → Root → Right

In a BST, inorder traversal produces elements in sorted order.

2. Preorder Traversal

Root → Left → Right

The root is visited first.

Useful for copying trees.

3. Postorder Traversal

Left → Right → Root

The root is visited last.

Useful for deleting trees.

4. Level Order Traversal

Visits nodes level by level.

It uses a queue.

Example

• Inorder → D, B, E, A, C
• Preorder → A, B, D, E, C
• Postorder → D, E, B, C, A
• Level Order → A, B, C, D, E

Quick Memory Trick

Inorder   → L N R
Preorder  → N L R
Postorder → L R N

N = Node / Root

46. What is a Graph?

A graph is a non-linear data structure consisting of a set of vertices (nodes) and edges that connect pairs of vertices.

Graphs are commonly used to represent relationships between entities.

Key Features

• Contains vertices and edges
• Represents complex relationships
• Edges can be directed or undirected
• Graphs can be weighted or unweighted

Types of Graphs

1. Directed Graph

Edges have a direction.

A → B

2. Undirected Graph

Edges have no direction.

A — B

3. Weighted Graph

Edges have associated weights, such as cost or distance.

4. Unweighted Graph

Edges have no weights.

Example

A, B, C

Edges:

A-B, B-C, A-C

Applications

• Social networks
• Navigation systems
• Network routing
• Recommendation systems

47. What is Depth First Search (DFS)?

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along a branch before backtracking.

Key Features

• Traverses deep first
• Uses recursion or a stack
• Works with graphs and trees
• Does not necessarily find the shortest path

Algorithm Steps

1. Start from a source node
2. Mark it as visited
3. Visit an unvisited neighbor
4. Continue deeper
5. Backtrack when no unvisited neighbor remains

Example

A → B → C → D

Working Idea

Time Complexity

O(V + E)

Where:

• V = Number of vertices
• E = Number of edges

Applications

• Path finding
• Cycle detection
• Topological sorting
• Connected components

Advantages

• Simple to implement
• Can use less memory than BFS in some cases

Disadvantages

• Does not guarantee the shortest path
• Can explore deep unnecessary paths

48. What is Breadth First Search (BFS)?

Breadth First Search (BFS) is a graph traversal algorithm that visits nodes level by level.

It explores all neighbors of a node before moving to the next level.

Key Features

• Traverses level by level
• Uses a queue
• Finds the shortest path in unweighted graphs
• Works with graphs and trees

Algorithm Steps

1. Start from a source node
2. Mark it as visited
3. Enqueue the node
4. Dequeue a node
5. Enqueue its unvisited neighbors
6. Repeat until the queue becomes empty

Example

A → B → D → C

Working Idea

Time Complexity

O(V + E)

Where:

• V = Vertices
• E = Edges

Applications

• Shortest path in unweighted graphs
• Level order traversal
• Network broadcasting
• Connected components

Advantages

• Finds shortest path in unweighted graphs
• Systematic level-wise traversal

Disadvantages

• Requires more memory for the queue
• Can be less efficient than DFS in some situations

49. What is Hashing?

Hashing is a technique used to map data or keys to a fixed-size value (index) using a hash function.

It enables fast operations such as searching, insertion, and deletion.

Key Features

• Uses a hash function
• Provides fast data access
• Stores data in a hash table
• Average operation time is O(1)

Hash Function

A hash function takes a key and produces an index.

Example:

h(key) = key % table_size

Example

For:

key = 25
table_size = 10

h(25) = 25 % 10  = 5

So the key maps to index 5.

Collision

When two keys map to the same index, a collision occurs.

Collision Handling

1. Chaining

Multiple elements are stored at the same index using a list.

2. Open Addressing

Another empty slot is searched.

Advantages

• Fast search, insertion, and deletion
• Average complexity O(1)
• Efficient for large datasets

Disadvantages

• Collisions can occur
• Performance depends on the hash function
• May require extra memory

Applications

• Hash Maps
• Dictionaries
• Database indexing
• Caching
• Password storage

50. What is a Hash Table?

A hash table is a data structure that stores data in key-value pairs.

A hash function is used to calculate an index where the value should be stored.

Key Features

• Stores key-value pairs
• Uses a hash function
• Provides average O(1) access
• Efficient for searching, insertion, and deletion

How Does a Hash Table Work?

Example

Suppose:

Key = 25
Value = "Apple"

Hash function:

h(25) = 25 % 10 = 5

The value can be stored at index 5.

Index     Value
  0
  1
  2
  3
  4
  5       25 → Apple
  6
  7
  8
  9

Collision

A collision occurs when multiple keys map to the same index.

Collision Handling

• Chaining → Store multiple elements in a linked list
• Open Addressing → Find another available slot

Time Complexity

Advantages

• Very fast data retrieval
• Efficient for large datasets
• Useful for key-based access

Disadvantages

• Collisions can reduce performance
• Requires a good hash function
• May use extra memory

Applications

• Dictionaries / Maps
• Database indexing
• Caching systems
• Symbol tables in compilers