# Data Structure Interview Questions in Java

## Data Structure Interview Questions in JAVA

**“Data Structure Interview Questions in Java”**

Data Structure is again one of the toughest and important subjects for the interview. So you have to prepare well for this subject if you want to clear the interview. Here you will get the most important data structure interview questions in JAVA.

**This will help you in preparing for the interview. A data structure is a particular way of organizing data on a computer so that it can be used effectively. If you want to know more about data structure, you can through the button below.**

## What is Data Structures?

**Data Structure** is a way to store and organize **data** so that it can be used efficiently. Our **Data Structure** tutorial includes all topics of **Data Structure** such as Array, Pointer, **Structure**, Linked List, Stack, Queue, Graph, Searching, Sorting, Programs, etc.

The data structures provided by the Java utility package are very powerful and perform a wide range of functions. These data structures consist of the following interface and classes −

- Enumeration
- BitSet
- Vector
- Stack
- Dictionary
- Hashtable
- Properties

**Read more about Data structure Interview Questions in Java:**

## Data Structure Interview Questions in JAVA

#### 1. What is a Stack?

Solution:- Stack is an ordered list in which, insertion and deletion can be performed only at one end that is called the top. It is a recursive data structure having pointer to its top element. The stack is sometimes called as Last-In-First-Out (LIFO) list i.e. the element which is inserted first in the stack will be deleted last from the stack.

#### 2. How do you find middle element of linked list in one pass?

Solution :- In order to find middle element of linked list in one pass, one needs to maintain two-pointer. One of these pointers will increment at each node while other will increment after two nodes at a time, thus by having this type of arrangement, when the first pointer reaches the end of the linked list, the second pointer will point to a middle element of the linked list.

#### 3. What are linear and non-linear types of data Structures? Also, How is an Array different from Linked List?

Solution:-

**Linear:**A data structure is called as linear if its elements form a sequence or a linear list such as Array, Linked List, Stacks, and Queues.**Non-Linear:**A data structure is called as non-linear if traversal of nodes is of nonlinear nature such as Graphs and Trees.

Difference between array and linked list are the following: –

- The size of the arrays is fixed always, Linked Lists size is not fixed.
- Insert and delete in an array is an expensive process, whereas the same can be easily done in Linked Lists.
- Accessing an element randomly is not possible in case of Linked Listed, but possible in an array.
- Extra memory space for a pointer is needed with each element of the Linked list, arrays don’t have pointers.
- Arrays have better cache locality mechanism that can make a big difference in performance.

#### 4.What is a postfix expression?

Solution:- An expression in which operators follow the operands is known as postfix expression. The main benefit of this form is that there is no need to group sub-expressions in parentheses or to consider operator precedence.

The expression “a + b” will be represented as “ab+” in postfix notation.

#### 5. **What are Infix, prefix, Postfix notations?**

Solution:-

**Infix notation:**X**+**Y – Operators are written in-between their operands. This is the usual way we write expressions. An expression such as**A * ( B + C ) / D****Postfix notation (also known as “Reverse Polish notation”):**X Y**+**Operators are written after their operands. The infix expression given above is equivalent to**A B C + * D/****Prefix notation (also known as “Polish notation”):**+ X Y Operators are written before their operands. The expressions given above are equivalent to

/ * A + B C D

#### 6.What is a multidimensional array?

Solution:- The multidimensional array can be defined as the array of arrays in which, the data is stored in tabular form consists of rows and columns. 2D arrays are created to implement a relational database lookalike data structure. It provides ease of holding the bulk of data at once which can be passed to any number of functions wherever required.

#### 7. Calculate the address of a random element present in a 2D array, given base address as BA.

Solution:- **Row-Major Order:** If array is declared as a[m][n] where m is the number of rows while n is the number of columns, then address of an element a[i][j] of the array stored in row major order is calculated as,

**Address(a[i][j]) = B. A. + (i * n + j) * size **

**Column-Major Order:** If array is declared as a[m][n] where m is the number of rows while n is the number of columns, then address of an element a[i][j] of the array stored in column major order is calculated as

**Address(a[i][j]) = ((j*m)+i)*Size + BA**.

#### 8.**Which data structures are used for BFS and DFS of a graph?**

Solution:-

- Queue is used for BFS
- Stack is used for DFS. DFS can also be implemented using recursion (Note that recursion also uses function call stack).

#### 9.Write the JAVA program to insert a node in circular singly list at the beginning.?

Solution:-

public class InsertAtStart { //Represents the node of list. public class Node{ int data; Node next; public Node(int data) { this.data = data; } } //Declaring head and tail pointer as null. public Node head = null; public Node tail = null; //This function will add the new node at the end of the list. public void addAtStart(int data){ //Create new node Node newNode = new Node(data); //Checks if the list is empty. if(head == null) { //If list is empty, both head and tail would point to new node. head = newNode; tail = newNode; newNode.next = head; } else { //Store data into temporary node Node temp = head; //New node will point to temp as next node newNode.next = temp; //New node will be the head node head = newNode; //Since, it is circular linked list tail will point to head. tail.next = head; } } //Displays all the nodes in the list public void display() { Node current = head; if(head == null) { System.out.println("List is empty"); } else { System.out.println("Adding nodes to the start of the list: "); do{ //Prints each node by incrementing pointer. System.out.print(" "+ current.data); current = current.next; }while(current != head); System.out.println(); } } public static void main(String[] args) { InsertAtStart cl = new InsertAtStart(); //Adding 1 to the list cl.addAtStart(1); cl.display(); //Adding 2 to the list cl.addAtStart(2); cl.display(); //Adding 3 to the list cl.addAtStart(3); cl.display(); //Adding 4 to the list cl.addAtStart(4); cl.display(); } }

#### 10.Define the tree data structure.

Solution:- The Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root. The nodes other than the root node are partitioned into the nonempty sets where each one of them is to be called sub-tree.

#### 11.How can AVL Tree be useful in all the operations as compared to Binary search tree?

Solution:- AVL tree controls the height of the binary search tree by not letting it be skewed. The time taken for all operations in a binary search tree of height h is O(h). However, it can be extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting this height to log n, AVL tree imposes an upper bound on each operation to be O(log n) where n is the number of nodes.

#### 12.How to know if a linked list has a loop?

Solution:- If two pointers are maintained, and one of them is incremented after processing two nodes and other after processing every node, it is likely that we find a situation where both the pointers are pointed to the same node.

This happens only if a linked list consists of a loop or cycle.

#### 13.Differentiate among cycle, path, and circuit?

Solution:-

**Path:**A Path is the sequence of adjacent vertices connected by the edges with no restrictions.**Cycle:**A Cycle can be defined as the closed path where the initial vertex is identical to the end vertex. Any vertex in the path can not be visited twice**Circuit:**A Circuit can be defined as the closed path where the intial vertex is identical to the end vertex. Any vertex may be repeated

#### 14.**Write a Java program to sort an array using the Bubble Sort algorithm?**

Solution:-

package test;

import java.util.Arrays;

public class BubbleSort {

public static void main(String args[]) {

int[] unsorted = {32, 39,21, 45, 23, 3};

bubbleSort(unsorted);

int[] test = { 5, 3, 2, 1};

bubbleSort(test);

}

public static void bubbleSort(int[] unsorted){

System.out.println("unsorted array before sorting : " + Arrays.toString(unsorted));

for(int i=0; i

for(int j= 1; j

if(unsorted[j-1] > unsorted[j]){

int temp = unsorted[j];

unsorted[j] = unsorted[j-1];

unsorted[j-1] = temp;

}

}

System.out.printf("unsorted array after %d pass %s: %n", i+1, Arrays.toString(unsorted));

}

}

}

#### 15. What are the advantages of Binary search over linear search?

Solution:- There are relatively less number of comparisons in binary search than that in linear search. In average case, linear search takes O(n) time to search a list of n elements while Binary search takes O(log n) time to search a list of n elements.

#### 16. How to reverse String in Java language?

Solution:- There are many ways available to reverse Sting in Java or other programming languages, one could do so by using built-in functions such as reverse() from StringBuffer class.

#### 17. What do you understand by a Linked List and What are its different types?

Solution:-

A linked list can be regarded as a linear data structure, where each element is a considered as a separate object or entity in itself. Each element within a list consists of two items – the data and the reference to the next node.

Types of Linked List:

**Singly Linked List**: In a singly linked list, every node stores two information. One is the address of the next node and other is data. the last node has NULL.**Doubly Linked List**: In a doubly linked list, there are two references to each node, reference to next node and to the previous node.**Circular Linked List**: In circular linked list all nodes are connected to each other and hence no NULL at the end. A circular linked list can be singly circular or doubly circular.

#### 18. What do you understand by Stack and where can it be used?

Solution:- This is the most popular Data Structure Java Interview Questions asked in an interview. A stack can be understood as a linear data structure which uses the order LIFO (Last In First Out) or FILO (First In Last Out) for accessing its elements. Basic operations on a stack are: Push, Pop and Peek

Applications of Stack are following:

- Infix to Postfix Conversion can be done using Stack.
- Evaluation of Postfix Expression is also possible.
- Reverse a String using Stack can be done.
- Implement two stacks in an array is also a nice use case.
- Check for balanced parentheses in an expression is done using stacks.

Login/Signup to comment