**What is Data Structure?**

Data structures are used to specify a specialized format for storing data. These structures allow better access to the data, ensure their protection and help to manage huge datasets. The common examples of data structures are **array, linked list, stack, and queue**.

**What are the types of data structure?**

**The different types of the data structure are:**

- Array
- Stack
- Linked list
- Queue
- Trees
- Graph
- Primitive data structures like int, float, pointers.
- Files

**Why we use data structure?**

**The uses of data structure are:**

- Helps to manage huge datasets by making it easier to trace and retrieve data.
- It reduces the complexity of search methods.
- Managing the data and secure it.
- They can also be used for grouping or arranging other data structures.

**What is stack in data structure?**

A stack is an abstract data type that is basically a collection of elements where the elements are added and removed by a particular order.They have a capacity that is defined beforehand.

Whenever an element is added to the stack it gets added to the top of the stack, and only the top element can be removed if an element has to be deleted. It follows a **LIFO (Last In First Out)** structure.

**What is a heap data structure?**

The heap data structure is a balanced binary tree where the root node of the tree is compared with the child nodes while arranging the tree. If the value of the root node is larger than or equal to any child node, the structure is called a **Max Heap**. If the value of the root node is lesser than or equal to any child node, the structure is called a **Min Heap**.

**Which data structure would you use to implement a heterogeneous array?**

A linked list is the data structure that can be used to implement a **heterogeneous** array.

**What is a set data structure?**

A set data structure is used for checking whether certain elements belong to a particular set of data. The set may not be in any specific order but they must not contain repeated elements. Operations like Union, Intersection and difference can be executed though sets.

**What is an asymptotic notation in data structure?**

Asymptotic notations in data structure are used for understanding the running time and overall performance of algorithms. The **asymptotic analysis** is carried out for determining the average case, best case and worst case scenario of an algorithm.

**What is Big O notation in data structure?**

The **Big O notation **is a tool for analyzing an algorithm’s execution time. This notation is the formal way to represent the upper bound of the respective algorithm’s running time. It is used to access the worst case for the total time the program will take to complete execution.

**How to calculate Big O notation in Data Structure?**

The Big O notation can be calculated by using the formula

`O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0}`

**What is a Priority Queue in Data Structure? **

A priority queue is a special type of the queue data structure that arranges the elements according to their key values. So, the element with the lowest key value is placed at the front and the element with the highest value is at the back. The element that has a lower key value has a higher priority than elements with a higher key value.

**What is an AVL tree in Data Structure? **

An **AVL** tree is a type of binary search tree that is height-balanced. This tree ensures that the numerical gap between the height of the right and the left subtree is not more than 1. The gap is known as **Balance Factor**.

The balance factor for each node is -1, 0, +1. As the tree has a balanced height, the insertion and operations can be performed with low time complexity. If the tree gets imbalanced then Rotation is operations are used to make the tree balanced again.

**What is recursion in Data Structure?**

Recursion is the process through which a function has certain instructions that allow it to call itself during program execution. In this process, a function can call itself directly or calls another function, which in turn will call the original function.

**What is Garbage Collection in Data Structure?**

**Garbage collection **is a memory management method that is used for identifying blocks of memory that are dead or unused and reallocate them for storing data. This can help to prevent memory leaks.

**This can be done through the following methods:**

- Mark and Sweep
- Copy collection
- Reference counting

**What is Hashing in Data Structure?**

**Hashing** is a process in data structure that is performed through a Hash function. In this function, data stored in a hash table is accessed through their index values.

In a **hash table** each value has a unique index. The function maps the value to be searched with the keys for faster access or retrieval.

**What is an Algorithm in Data Structure?**

An algorithm is a set of instructions that have to be executed in a specific order to obtain the desired output. The algorithm can take 0 or more inputs for performing certain operations for getting the result.

It terminates after a certain condition. In the data structure, algorithms are of different types namely **search, sort, insert, update delete**.

**How to calculate the complexity of an algorithm in data structure?**

The **algorithmic complexity** is calculated by analyzing the time taken for completion and space it consumes during its execution. If A is the algorithm and n is the size of the input provided to the program, time is calculated by counting the number of operations executed.

The maximum memory space occupied during these operations defines the memory space of the algorithm. For example, the time complexity is measured using the **Big O notation**.

**What are the various types of Algorithm in data structure?**

**The various types of algorithm in data structure are:**

- Search, sort, insert, update delete algorithm
- Recursive algorithm
- Backtracking algorithm
- Divide and conquer algorithm
- Randomized algorithm
- Brute force algorithm
- Dynamic algorithm
- Greedy algorithm

**What are Queues in data structure? **

The queue is an **abstract data type** that has is open at both ends. One end is used to insert elements into the queue, and the other end is used to remove elements. Insertion is done enqueue operation and removal is done through the dequeue operation.

It works in the **FIFO method (First In First Out)** which means that the first element to be inserted will be the first to be removed.

**Explain the difference between Linear and Non-Linear data**** structure?**

**The differences between Linear and Non-Linear** **data structure are:**

Linear data structure |
Non-Linear data structure |

Each element is associated with the next and previous one. | Each element is associated with many items. |

Can be traversed in a single run. | Cannot be traversed in a single run. |

Single levels are involved. | Multiple levels. |

Example – Array, stack, queue, etc. |
Example – Graph and Tree |