Popular

Data Science

Technology

Finance

Management

Future Tech

Internship Assurance

DevOps & Cloud Engineering

**Data structures** are one of the most essential features in computer science. The ability of data structures to provide a basic way to store anyone’s data effectively and efficiently is remarkable. They are essential for creating fast and powerful algorithms. A strong grasp and understanding of data structures are highly essential for anyone solving complex problems and optimising code performance. You can find many different types of data structures today with each having its own applications and characteristics.

In this blog, we shall cover the top data structure interview questions and their answers, so that it can help anyone to prepare thoroughly and get to know some of the most commonly asked interview questions. We’ll cover topics including arrays, linked lists, stacks, queues, heaps, hashing, trees, graphs, and tries.

Data structures are the methods for storing and organising data in a computer, reducing complex operations and hardware embedding, and allowing for efficient data modification. Without the data structures, we cannot handle large volumes of data, and data manipulation techniques like searching, sorting, and indexing. Some of the common data structures involve:

- Arrays
- Linked lists
- Stacks
- Queues
- Heap
- Hashtable
- Trees
- Graphs
- Hash tables

We can classify the data structures into two basic categories:

- Primitive
- Non-primitive

**Primitive Data Structures:** All the basic data structures are a part of primitive data structures, which include primary elements like int, char, and float.

**Non-primitive Data Structures: **This group is a bit more complicated, with arrays, linked lists, stacks, queues, trees, graphs, and hash tables falling under it. Within this complex group, we can draw a line between linear and nonlinear structures.

When all the data has to be arranged linearly, linear data structures are used. An example of linear data structures can be arrays, linked lists, queues, and stacks which organise data in a linear way. Despite being less complex and, therefore, easier to implement, linear data structures may not always be the most effective for every operation because of their simplicity.

Aspect |
File Structure |
Storage Structure |

Definition | Organisation of data within a file | Physical and logical layout of data on storage |

Focus | Data organisation within files | Data storage and retrieval from devices |

Example | File formats like CSV, XML | Storage mediums like HDD, SSD |

A postfix expression is an alternate name for the Reverse Polish Notation (RPN) and it is a way of writing mathematical expressions where operators come after their operands. As an illustration, the postfix expression for “3 + 4” becomes “3 4 +”. In computer science, postfix expressions find utility because they allow arithmetic expressions to be evaluated without using parentheses, which makes them computationally friendly to machines.

A list is a set of components of a similar kind that are put away in memory locations that are contiguous, an array allows direct access to any element by the use of an index value and thus facilitates effective data retrieval and modification operation. Because arrays allow random access based on index, it makes the operation faster and easier as well as widely usable; hence its popularity.

The time complexity for array element access is O(1). This is due to the feature of arrays which have the direct address of every element and any element can be directly accessed using its index.

In a majority of programming languages, we cannot change the size of an array after its creation. Nevertheless, there are some languages that make available dynamic resizing through data structures (e.g., lists in Python). For arrays that are fixed in size, you would have to create another array with the size you want.

Here, you can mention the looping through the array along with two variables that hold the current smallest and current largest values while running each iteration. Make sure you update the minimum and maximum values as you iterate further.

Typically, this happens when an index is being referenced from beyond the limit of valid indexes in the array, especially during any iteration or function references, causing a runtime error.

An array of arrays is what constitutes a multidimensional array. This structure enables data storage in a grid-like manner. The most common form of multidimensional array is a 2D array, which is essentially a table of rows and columns.

Elements of a 2D array can be stored in memory in two ways:

**Row-major order:**All elements of a row are stored in contiguous memory locations.**Column-major order**: All elements of a column are stored in contiguous memory locations.

A sparse array is an array in which most of the elements have a default value (usually zero). Sparse arrays are used to save memory when dealing with large datasets where many elements are empty or have a default value.

A linked list is a type of data structure where elements, referred to as nodes, are stored in a linear order. Each node consists of two components: the actual data and a pointer that indicates the location of the next node in the sequence. This design choice enables easy manipulation, such as quick removal and addition of elements due to the necessity of solely updating pointers.

Feature |
Array |
Linked List |

Storage | Contiguous memory locations | Non-contiguous memory locations |

Access | Direct access to elements via index | Sequential access via pointers |

Size | Fixed-size | Dynamic size |

Insertion | Costly, especially in the middle or beginning | Efficient, especially in the middle or beginning |

Deletion | Costly, especially in the middle or beginning | Efficient, especially in the middle or beginning |

**Singly Linked List:**Consists of node points that hold references only to the next node.**Doubly Linked List:**In a doubly linked list, each node points towards both its next and previous nodes.**Circular Linked List:**On the other hand, in a circular linked list, the last node points back to the first node, thus forming a circle structure between all nodes.**Circular Doubly Linked List:**Combining the above two concepts, we have the circular doubly linked list where each node maintains a reference to its next and previous nodes while the last node closes the loop by pointing back to the first node.

**Dynamic Size:**Linked lists have the ability to grow or reduce dynamically in size.**Efficient Insertions/Deletions:**Modifying elements is more efficient, particularly at their initiation.**Memory Utilisation:**No need to allocate memory in advance.

Any doubly-linked list is similar to a single linked list but the main difference is it has a pointer to the previous node also. Hence it allows us to traverse backward to the previous node along with a pointer to the next node for forward propagation.

**Example:**

Here, Node1 points to Node2, Node2 points to Node3 and Node1, and Node3 points to Node2.

**Choose a Linked List When:**- You need frequent insertions and deletions.
- You don’t know the size of the data in advance.

**Choose an Array When:**- You need constant-time access to elements.
- The size of the data is known and fixed.

- Dynamic size
- Efficient insertions and deletions
- Memory utilisation

**Memory Overhead:**Extra memory is required for storing pointers.**Sequential Access:**Accessing elements requires traversal from the head node, which can be slow.**Complex Operations:**More complex implementation compared to arrays.

**Insertion/Deletion:**O(1) if the position is known.**Search:**O(n), where n is the number of nodes.**Access:**O(n), for accessing elements.

One of the linear data structures that can be used in various applications, especially where stacking is required, a stack can be created. It follows the Last In, First Out (LIFO) principle, which makes the stack to add any element at the end, and that will become the first element also to be removed.

**Function Call Management:**Stacks are used to manage function calls in programming languages.**Expression Evaluation**: Stacks help in evaluating postfix and prefix expressions.**Undo Mechanisms:**In this method, we can make different applications like text editors, which use stacks to implement undo functionality.**Backtracking:**Algorithms such as depth-first search (DFS) use stacks for backtracking.**Browser History:**Stacks manage the history of visited web pages in browsers.

**Push:**It can add an element to the top of the stack.**Pop:**Removes the top element from the stack.**Peek/Top:**Retrieves the top element without removing it.**isEmpty:**Checks if the stack is empty.**isFull:**Checks if the stack is full (in the case of fixed-size stack implementations).

It is very easy to implement a stack, just by using an array and maintaining a pointer (or index) the topmost element of the insertion. All other operations can be performed prior to this pointer.

Operation |
Time Complexity |

Push | O(1) |

Pop | O(1) |

Peek | O(1) |

isEmpty | O(1) |

isFull | O(1) |

**Stack Overflow:**This occurs when you try to push an element onto a stack that is already full.**Stack Underflow:**This occurs when you try to pop an element from an empty stack.

**To evaluate a prefix expression using a stack:**

- Read the expression from right to left.
- Push operands onto the stack.
- When an operator is encountered, pop the required number of operands from the stack.
- Apply the operator to these operands.
- Push the result back onto the stack.
- Continue until the expression is fully evaluated.
- The final result will be at the top of the stack.

Internship Assurance

DevOps & Cloud Engineering

A queue holds the properties of the First In, First Out (FIFO) principle. Hence, when we define a queue, its first inserted element will be the first one to be removed. This can be used in various applications like task scheduling where the order priority matters the most.

**Task Scheduling:**Queues are used by different operating systems to manage and update different tasks and processes.**Print Queue:**Printers use queues to manage print jobs.**Customer Service:**Queues are used to manage customers waiting in line.**Data Buffering:**Queues are used in networking and communication systems for data buffering.

**Enqueue:**Adding an element to the end of the queue.**Dequeue:**Removing an element from the front of the queue.**Front:**Retrieves the front element without removing it.**Rear**: Retrieves the last element without removing it.**isEmpty**: Checks if the queue is empty.**isFu**ll: Checks if the queue is full (in case of fixed-size queues).

You can mention the use of pointers to implement a linked list with the help of a queue. Maintaining pointers to the front and rear, you can perform enqueue i.e. the operation to add a node to the end (rear), and to remove a node from the beginning (front) is called dequeue.

A special kind of queue where you can define each element with a priority. Hence, the elements are dequeued with the help of their priority rather than their order in the queue and higher-priority elements are served before lower-priority ones.

A double-ended queue allows both the insertion and deletion of elements from the front and rear ends of the queue. Hence this generates a combined feature of both stacks and queues which can be used in a more flexible manner.

**Order Preservation:**Maintains the order of elements, which is essential for tasks like scheduling.**Fairness:**Ensures that each element gets processed in the order it was added.**Efficient Operations:**Enqueue and dequeue operations are efficient, typically O(1).

**Fixed Size:**In the case of array-based queues, the size is fixed and cannot be dynamically resized.**Limited Access**: Access to elements is restricted to the front and rear, making random access inefficient.**Memory Overhead:**Linked list implementation requires extra memory for pointers.

A heap is a special tree-based data structure that satisfies the heap property. In a heap, for any given node i, the value of i is either greater than or equal to (in a max heap) or less than or equal to (in a min-heap) the values of its children. This ensures that the root node is always the largest (in a max heap) or smallest (in a min-heap) element.

**Priority Queues:**Heaps are used to implement priority queues, where elements are served based on priority.**Scheduling:**Operating systems use heaps for task scheduling to manage processes.**Graph Algorithms:**Heaps are used in algorithms like Dijkstra’s and Prim’s for finding the shortest path and minimum spanning tree.**Heap Sort:**A popular sorting algorithm that uses the heap data structure.

**Priority Management**: Heaps allow for efficient retrieval of the highest or lowest priority element, which stacks cannot manage.**Dynamic Operations:**Heaps support dynamic insertion and deletion based on priority, whereas stacks follow a strict LIFO order.

**Min Heap:**The value of each node is less than or equal to the values of its children. The minimum value is at the root.**Max Heap:**The value of each node is greater than or equal to the values of its children. The maximum value is at the root.

Operation |
Time Complexity |

Insert | O(logn) |

Delete | O(logn) |

Peek | O(1) |

Feature |
Heap |
Binary Search Tree (BST) |

Order | Heap property (min or max) | Left child < parent < right child |

Structure | Complete binary tree | No specific structure requirement |

Operations | Efficient insertion/deletion at the root | Efficient search, insertion, and deletion |

Complexity | Insert/Delete: O(logn), Peek: O(1) | Insert/Delete/Search: O(logn) on average |

**In-order traversal:**Perform an in-order traversal of the BST to get a sorted list of elements.**Build a Heap:**Use the sorted list to build a heap by inserting elements one by one into an empty heap.

**Insert Elements:**Insert all elements of the second heap into the first heap one by one.**Build New Heap:**Alternatively, combine both heaps into a single list and then build a new heap from the combined list.**Efficient Merging:**Use specialised algorithms like the union of binomial heaps or Fibonacci heaps for more efficient merging.

Hashing allows us to map data of any arbitrary size to fixed-size values which are also known as hash values. The function responsible for this is called a hash function and the primary aim of hashing is to give us fast data retrieval using a hash table. The hash table provides us with highly efficient insertion and deletion operations.

**Database Indexing:**Hashing is used to quickly locate data without having to search every location in a database.**Password Storage**: Hash functions are used to store hashed passwords securely.**Caching:**Hashing helps in implementing cache mechanisms by mapping keys to cache values.**Data Deduplication:**Hashing is used to identify duplicate data efficiently.**Symbol Tables in Compilers:**Hashing helps in managing and accessing identifiers in programming languages.

When we look into the hash function, it enables the input as a key and further returns a fixed-sized string of bytes. Therefore, the output will be a number, typically called as a hash value or hash code. Distributing hash values uniformly across the whole hash table to minimise collisions is a highly essential feature of good hash functions.

**For example:**

This simple hash function maps a key to an index in the hash table by taking the modulus with the table size.

A collision occurs when two different keys hash to the same index in a hash table. Since each index can hold only one entry, special techniques are needed to handle collisions to maintain the efficiency of the hash table.

The load factor of a hash table is a measure of how full the hash table is. It is calculated as:

An increased load factor implies more items, probably resulting in more collisions; conversely, a decreased load factor indicates fewer entries which might lead to more empty space. An often-used threshold for adjusting the size of the hash table is setting the load factor to 0.75.

A tree is a hierarchical data structure. It consists of nodes with one node as the root from which zero or more child nodes stem. Every child node can have its own children, thus forming a structure that looks like a tree because every child node can have its own children as well; indeed, this does represent a tree-like structure. Trees find their application to represent hierarchical relationships and are an essential data structure in computer science.

**File Systems:**Used to organise files and directories.**Databases:**Utilised in indexing and managing hierarchical data.**Network Routing:**Helps in routing data through network hierarchies.**XML/HTML Parsing:**This can be used to parse and manipulate XML/HTML documents.**AI and Machine Learning:**Although much research work is going on in AI and ML, the decision trees can help in making decisions based on various inputs when combined with the features of the ML model.

**Insertion:**Adding a node to the tree.**Deletion:**Removing a node from the tree.**Traversa**l: Visiting all nodes in a specific order (e.g., in-order, pre-order, post-order).**Searching:**Finding a node in the tree.**Updating**: Modifying the value of a node.

**Binary Tree:**Each node has at most two children.**Binary Search Tree (BST):**A binary tree with the left child less than the parent and the right child greater. This is just a plain binary search tree.**AVL Tree:**A self-balancing binary search tree – simple but efficient.**Red-Black Tree:**An alternative self-balancing binary search tree, slightly different from an AVL with colour properties.**B-Tree:**A generalisation of a binary search tree with multiple children per node.**B+ Tree:**An extension of B-trees with all values stored in leaf nodes.**Trie:**A tree used for efficient retrieval of keys in a dataset of strings.**Heap:**A specialised tree-based data structure that satisfies the heap property.

When you define a binary tree, each node must have at most two children which is referred to as the left and the right child elements. There are many big advantages of binary trees in expression parsing, search algorithms, hierarchical and applications like data representation.

Similar to a normal binary tree, a binary search tree consists of a value greater than all other nodes in the left subtree of any node in the BST. Hence it is a kind of sorted tree that improves the addition, lookup, and deletion operations tremendously.

Feature |
B-Tree |
B+ Tree |

Structure | Internal nodes and leaves store keys. | Internal nodes store keys, leaves store actual values. |

Leaf Nodes | Not linked | Linked for sequential access |

Search Time | O(log n) | O(log n) for internal nodes, O(n) for sequential access |

Use Case | Databases, file systems | Databases, and file systems where range queries are common |

**Linked Representation:**Each node contains data and pointers to its children.**Array Representation**: Here, the nodes are stored in an array, with the parent-child relationship defined by indices.

**Advantages:**

- Hierarchical data representation.
- Efficient search, insert, and delete operations in balanced trees.
- Flexible and scalable.

**Disadvantages:**

- It can become unbalanced, leading to inefficient operations.
- It is more complex to implement and maintain compared to linear data structures.

**Hierarchical Data:**Commonly used when data has a hierarchical relationship, such as organisational structures or file systems.**Efficient Search**: When balanced trees are required for fast search, insertion, and deletion operations.**Dynamic Data**: When the size of the dataset is dynamic, frequent insertions and deletions are needed.

**AVL Trees:**Maintain balance by ensuring the height difference between the left and right subtrees of any node is at most one. Rotations are performed to maintain balance after insertions and deletions.**Red-Black Trees:**Maintain balance by ensuring properties like every node is either red or black, the root is black, and red nodes cannot have red children. Rotations and colour changes are performed to maintain balance.

Post-order traversal visits nodes in the following order:

- Traverse the left subtree.
- Traverse the right subtree.
- Visit the root node.

A graph is a data structure that consists of a set of nodes (or vertices) and a set of edges connecting these nodes. Graphs are used to represent pairwise relationships between objects. Graphs can be directed or undirected, weighted or unweighted.

**Social Networks:**Representing relationships between users.**Navigation Systems:**Finding the shortest path between locations.**Internet:**Representing the web, where pages are nodes and hyperlinks are edges.**Transport Networks:**Managing routes and connections in public transportation systems.**Dependency Management**: Managing dependencies in software projects.

**Undirected Graph**: Edges have no direction. If there is an edge between node A and node B, it can be traversed in both directions.**Directed Graph (Digraph):**Edges have a direction. If there is a directed edge from node A to node B, it can only be traversed from A to B.**Weighted Graph:**Edges have weights representing costs, distances, or capacities.**Unweighted Graph:**Edges have no weights.**Connected Graph:**There is a path between any two nodes.**Disconnected Graph**: Not all nodes are connected.**Cyclic Graph:**Contains at least one cycle.**Acyclic Graph:**Does not contain any cycles.

Operation |
Time Complexity (Adjacency List) |
Time Complexity (Adjacency Matrix) |
Space Complexity (Adjacency List) |
Space Complexity (Adjacency Matrix) |

Add Vertex | O(1) | O(V^2) | O(V + E) | O(V^2) |

Add Edge | O(1) | O(1) | O(V + E) | O(V^2) |

Remove Vertex | O(V + E) | O(V^2) | O(V + E) | O(V^2) |

Remove Edge | O(V) | O(1) | O(V + E) | O(V^2) |

Check if Edge Exists | O(V) | O(1) | O(V + E) | O(V^2) |

Dijkstra’s Algorithm is used to find the shortest path from a source node to all other nodes in a weighted graph.

**It works by:**

- Initialising the distance to the source node as 0 and all other nodes as infinity.
- Using a priority queue to select the node with the smallest distance.
- Updating the distances of adjacent nodes.
- Repeating until all nodes are processed.

**Applications:**

**Navigation Systems:**Finding the shortest route.**Network Routing**: Optimising data packet paths.**Geographical Maps**: Planning the shortest travel route.

A trie, also known as a prefix tree, is a tree-like data structure used to store a dynamic set of strings. It is particularly efficient for searching for words or prefixes in a dictionary. Each node in a trie represents a character of a string, and a path from the root to a leaf represents a complete string. Tries are used to handle sequences of characters, making them ideal for problems involving string processing.

**Autocomplete Systems:**Tries are used in search engines and text editors to provide autocomplete suggestions. As the user types, the trie can quickly retrieve all words that start with the given prefix.**Spell Checkers:**Tries can be used to implement spell checkers by storing a dictionary of correct words. The trie can then be used to suggest corrections for misspelt words.**IP Routing:**In networking, tries are used for IP routing, where each node represents a bit in an IP address. This allows efficient lookup of routing tables.**Text Search:**Tries data structure can be utilised when tasked with searching for word or pattern occurrences within substantial text data.**Dictionary Implementation:**They find their application as an effective method for implementing dictionaries; in tries, every node is associated with a character while words are represented by paths through the structure.

In conclusion, comprehending data structures is highly crucial and stands as the necessity for resolving complicated problems productively. Every data structure, from arrays and linked lists to trees and graphs, possesses distinctive features and uses. Acquiring proficiency in these ideas can greatly upgrade your ability to resolve problems, and is also necessary for any data science interview preparation.

The blog you just read has the major points and responses to various data structures, which has a good basis for further interview preparation or practical work. When you grasp these topics, you are ready to meet many tasks that programmers need to handle in any organisation, and you can come up with new optimised solutions.

Book a free counselling session

Get a personalized career roadmap

Get tailored program recommendations

Explore industry trends and job opportunities

Programs tailored for your success

Popular

Data Science

Technology

Finance

Management

Future Tech

Upskill with expert articles

View all

Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved