Top Data Structure Interview Questions And Answers - 2022

Interview Questions

• File Structure: Representation of data into secondary or auxiliary memory say any device such as hard disk or pen drives that stores data which remains intact until manually deleted is known as a file structure representation.
• Storage Structure: In this type, data is stored in the main memory i.e RAM, and is deleted once the function that uses this data gets completely executed.
• The difference is that storage structure has data stored in the memory of the computer system, whereas file structure has the data stored in the auxiliary memory.

• If the elements of a data structure result in a sequence or a linear list then it is called a linear data structure. Whereas, traversal of nodes happens in a non-linear fashion in non-linear data structures.
• Lists, stacks, and queues are examples of linear data structures whereas graphs and trees are the examples of non-linear data structures.

• Arrays are the collection of similar types of data stored at contiguous memory locations.
• It is the simplest data structure where the data element can be accessed randomly just by using its index number.

• Multi-dimensional arrays are those data structures that span across more than one dimension.
• This indicates that there will be more than one index variable for every point of storage. This type of data structure is primarily used in cases where data cannot be represented or stored using only one dimension. Most commonly used multidimensional arrays are 2D arrays.
  • 2D arrays emulates the tabular form structure which provides ease of holding the bulk of data that are accessed using row and column pointers.

A linked list is a data structure that has sequence of nodes where every node is connected to the next node by means of a reference pointer. The elements are not stored in adjacent memory locations. They are linked using pointers to form a chain. This forms a chain-like link for data storage.

• Each node element has two parts:
  • a data field
  • a reference (or pointer) to the next node.
• The first node in a linked list is called the head and the last node in the list has the pointer to NULL. Null in the reference field indicates that the node is the last node. When the list is empty, the head is a null reference.

Linked lists can be considered both linear and non-linear data structures. This depends upon the application that they are used for.

• When linked list is used for access strategies, it is considered as a linear data-structure. When they are used for data storage, it can be considered as a non-linear data structure.

1. Insertion and Deletion
   • Insertion and deletion process is expensive in an array as the room has to be created for the new elements and existing elements must be shifted.
   • But in a linked list, the same operation is an easier process, as we only update the address present in the next pointer of a node.
2. Dynamic Data Structure
   • Linked list is a dynamic data structure that means there is no need to give an initial size at the time of creation as it can grow and shrink at runtime by allocating and deallocating memory.
   • Whereas, the size of an array is limited as the number of items is statically stored in the main memory.
3. No wastage of memory
   • As the size of a linked list can grow or shrink based on the needs of the program, there is no memory wasted because it is allocated in runtime.
   • In arrays, if we declare an array of size 10 and store only 3 elements in it, then the space for 3 elements is wasted. Hence, chances of memory wastage is more in arrays.

• Following are the scenarios where we use linked list over array:
  • When we do not know the exact number of elements beforehand.
  • When we know that there would be large number of add or remove operations.
  • Less number of random access operations.
  • When we want to insert items anywhere in the middle of the list, such as when implementing a priority queue, linked list is more suitable.
• Below are the cases where we use arrays over the linked list:
  • When we need to index or randomly access elements more frequently.
  • When we know the number of elements in the array beforehand in order to allocate the right amount of memory.
  • When we need speed while iterating over the elements in the sequence.
  • When memory is a concern:
    • Due to the nature of arrays and linked list, it is safe to say that filled arrays use less memory than linked lists.
    • Each element in the array indicates just the data whereas each linked list node represents the data as well as one or more pointers or references to the other elements in the linked list.
• To summarize, requirements of space, time, and ease of implementation are considered while deciding which data structure has to be used over what.

• This is a complex type of a linked list wherein a node has two references:
  • One that connects to the next node in the sequence
  • Another that connects to the previous node.
• This structure allows traversal of the data elements in both directions (left to right and vice versa).
• Applications of DLL are:
  1. A music playlist with next song and previous song navigation options.
  2. The browser cache with BACK-FORWARD visited pages
  3. The undo and redo functionality on platforms such as word, paint etc, where you can reverse the node to get to the previous page.

• Stack is a linear data structure that follows LIFO (Last In First Out) approach for accessing elements.
• Push, pop, and top (or peek) are the basic operations of a stack.

• A queue is a linear data structure that follows the FIFO (First In First Out) approach for accessing elements.
• Dequeue from the queue, enqueue element to the queue, get front element of queue, and get rear element of queue are basic operations that can be performed.

• Some of the applications of queue are:
  1. CPU Task scheduling
  2. BFS algorithm to find shortest distance between two nodes in a graph.
  3. Website request processing
  4. Used as buffers in applications like MP3 media player, CD player, etc.
  5. Managing an Input stream

• In a stack, the item that is most recently added is removed first whereas in queue, the item least recently added is removed first.

• A variable is stored in memory based on the amount of memory that is needed. Following are the steps followed to store a variable:
  • The required amount of memory is assigned first.
  • Then, it is stored based on the data structure being used.
    • Using concepts like dynamic allocation ensures high efficiency and that the storage units can be accessed based on requirements in real time.