## An Overview of Data Structure

A data structure is a user preferred, specialized format to organize, manage and store data for quick and efficient access and modification. Every data structure is designed to assemble and hold data to suit a specific purpose and preferably work with various algorithms. It renders multiple data elements regarding relationships and serves as the basis for Abstract Data Types. Implementing a data structure requires creating a set of procedure that produces as well as manipulate instances of that structure. A vast variety of **Algorithm Interview Questions** are also available on our website.

Data Structures are used to organize the data in the memory of the computer in a very systematic manner to reduce the complexities of the task performed by the processor. As a result the performance of the computer or server increases

We have written **Data Structure Interview Questions** and answers that will help you in becoming a good programmer.

### Development History

- Some Data structures like Queue already existed from the time of batch processing.
- Stack was proposed in 1946 in the computer design of Alan M. Turing.
- Linked Lists were developed by Allen Newell, Cliff Shaw and Herbert A. Simon at RAND Corporation in the year 1955-1956
- Binary Tree was invented by Rudolf Bayer, Edward M. McCreight.

You must read in-depth about this if you are preparing for **Data Structure Interview Questions Java**.

#### Development History

- With the help of Data structures, the desired data can be searched in a concise period from the vast amount of stored data like about data having an inventory of about 2 million items
- Multiple requests can be handled using the data structures like at a time processing the application of the thousands of user on the web browser.
- You can access the data from anywhere at any point in time.
- Data Structures helps in designing efficient algorithms.

You must read in-depth about this if you are preparing for **Algorithm Interview Questions and Answers**.

### Data Structure Interview Questions and answers

*Looking for a new job? Do not miss to read our Data Structure Interview Questions and answers. Whether you are a fresher or an experienced, these questions and answers that can help you to crack your interview.*

- What is data structures & also explain its types?
- What are the uses of data structures?
- How many types of operations can be performed on data structures?
- Explain the difference between file structure and storage structure?
- Explain the difference between array and linked list?
- What is Stack and explain it's basic operations?
- What is Queue and how it is different from stack?
- What do you mean by Infix prefix and postfix notations?
- What do you mean by FIFO and LIFO?
- Explain the difference between PUSH and POP?
- Please write its postfix form of the expression: (A + B) * (C - D)
- What do you mean by linked list also explain its types?
- What do you mean by binary trees?
- Whay do you mean by binary search tree?
- Please write basic algorithm for searching a binary search tree.
- What do you mean by graph?
- What do you mean by AVL tree?
- What is BFS and DFS used in graph?
- Explain the differences between B tree and B+ tree?
- What is tree traversal and how we can do it?
- What do you mean by Fibonacci search?
- What is Huffman’s algorithm? Explain

Data Structures is a format for the organizing, retrieving and storing the data in a memory of the computer.

#### Types of Data Structures

Data structure are of two types:-

- Primitive Data Structures
- Non-Primitive Data Structures

##### Primitive Data Structure are of four types:-

- Integer
- Float
- Characters
- Pointers

##### Non-Primitive Data Structure are of three kinds:-

- Array
- Lists
- Files

###### Lists are of two kinds:-

**Linear**:- Stacks, Queues**Non-Linear**:-Trees, Graphs

Data Structure supports in correctly organizing the data in a computer memory due to which the data is quickly provided to the processor for the required calculations and this result in the overall increase in the performance of both computer and program. Using the data structure, it is easy to locate and retrieve the massive amount of data.

##### Six types of operations are performed on data structures:-

**1. Insertion:** Insertion means adding a new record or data element to the data structure.

**2. Deletion:** Deletion means deleting the existing record or the data element from the data structure if the component is present.

**3. Searching:** Searching means searching the location of the particular data element in a data structure.

**4. Traversal:** Traversal means accessing each data element in the data structure only once so that the data elements can be processed.

**5. Sorting:** Sorting means arranging data elements of a data structure in a specified order like if the data elements are numerical then in the Ascending or Descending order and if Alphanumeric then in the Dictionary order.

**6. Merging: **Merging means Combining the data elements of two similar data structures to form a new data structure which is of the same type.

*This information was frequently asked during Data Structure Interview Questions for Freshers.*

**Storage Structure**:-The memory that is allocated to a variable or a constant is stored in the main memory of the computer that is RAM which gets deleted as soon as the function ends. This representation of allocating the memory is called Storage Structure

**File Structure**:-If you write the data in a file and save that file in the hard disk or any other external device like Pen Drive then the data will remain intact till it is deleted manually by the user. This representation of saving the file in an auxiliary or secondary memory is called File Structure

S.no | ARRAYS | LINKED LIST |
---|---|---|

1. | An array is a collection of the elements of a similar data type. | Linked List is an ordered collection of the elements of the same type and all the elements, with the help of pointer, are connected. |

2. | The array supports the Random Access. Here the elements can be accessed directly using their index, like arr[2] for the 3rd element, arr[1] for the 2nd element, arr[0] for the 1st element, etc. | Linked List supports the Sequential Access. Here to access any element or node in a linked list, we have to sequentially traverse the complete linked list to reach to that element. |

3. | In an array, elements are stored consecutively in the memory. | In a linked list, the new elements can be stored anywhere in the memory. |

**Stack **comes under one of the types of Data Structure which is Linear Lists in which the data elements are stored sequentially. In Linear lists, the insertions and deletions of the data elements are easier.

**Stack **follow a "**LIFO**" rule which means 'Last In First Out' for storing and retrieving the data, i.e., Last data pushed into the stack will come out first.

There are two primary functions of Stack: **Push() & Pop()** for inserting and removing the data elements from the stack respectively.

**A Queue in the data structure is a linear structure which follows a particular order in which all operations to be performed. The order is First In First Out (FIFO) used in Queue.**

S.no | Stack | Queue |
---|---|---|

1. | Stack has only one end for inserting and deleting the data elements | The queue has two terms, one for enqueuing the data and other for dequeuing the data elements. |

2. | There are no variants in Stack | In queue, there are variants like a circular queue, priority queue, double ended queue |

3. | Stack uses only one pointer for its one end. | Queue used 2 pointers for its two ends Rear and Front |

3. | Operations performed are Push() and Pop() | Operations performed are enqueue() and dequeue() |

Infix, Prefix, and Postfix are the there ways of writing the expressions.

S.no | Infix notation | Prefix notation | Postfix notation |
---|---|---|---|

1. | Infix notation is written as X + Y.The usual method of writing any mathematical expression is Infix notation. In this notation, the operators are written between their operands. | Prefix notation is written as +XY.The operator comes before the operands. The evaluation of the prefix notation is from Left to Right | Postfix notation is written as XY+.in this notation the operator enters after the operand. The review of the prefix notation is from Left to Right. |

**LIFO**:- LIFO stands for Last In First Out. In this method, the last data element entered will come out first.

**FIFO**:-FIFO stands for First in First Out. In this method, the data element entered first will come out first

S.no | Push | Pop |
---|---|---|

1. | Push function is used for inserting the element into the stack | The pop function is used for taking the component out from top of the stack |

(A+B)*(C-D)

STEP 1:-(AB+)*(CD-)

STEP 2:-AB+CD-*

**The answer is AB+CD-***

*Reading our vast question bank will make it easy for you to crack the Data Structure Interview Questions.*

Linked List is an ordered collection of the elements of the same type and all the elements, with the help of this pointer, are connected.

**There are three types of Linked List.**

- Singly Linked List
- Doubly Linked List
- Circular Linked List

**A Binary Tree comes under one of the types of data structure Non-Linear Lists. In this list, the data elements are not stored sequentially.**

In a binary tree, the nodes are connected in a particular way which makes the search operation of the data very easy. Both the nodes have one or two child nodes, creating the branches of the tree. The child nodes on the left are called the left nodes and on the right are called the right nodes, and the top node is called the Root Node. The number of levels in the binary tree is called the height of the tree.

**BST or Binary Search Tree** is a node-based data structure in which every node will have two child nodes. Further, each child node must have a leaf or root of another binary search tree. This data structure is base for highly efficient searching and sorting algorithm and can be utilized to construct abstract data structures including multisets, sets, and associative arrays.

It’s a non-linear data structure which consists of nodes and edges. The edges are referred to as arcs and lines that connect any two nodes in the graph, whereas the nodes here also referred to as vertices.

It’s a self-balanced binary search tree and first data structure to be invented. Here the heights of the two child subtrees of any node only differ by at most one. If the difference stands for more than one, rebalancing is done to restore the property.

**BFS and DFS **are two algorithms of the graph data structure. DFS algorithm traverses the graph in a way that it tries to go far from the root node. Its implementation uses the stack. Compared to this, the BFS algorithm traverses the graph as close as possible to the root node.

The principal difference between a B tree and a B+ tree will be, in a B Tree is capable of saving both keys and data in the leaf and internal nodes, whereas the B+ can only store data in the leaf nodes.

This is a form of graph travelers and refers to a whole process of visiting each node in a tree data structure for check and update. The inorder traversals share nodes in nondecreasing order; the preorder traversals are used to create a copy of the tree and get prefix expression on of an expression tree, whereas the postorder traversal is required to delete a tree.

It’s a set of numbers which starts either from a zero or a one and then followed by a one, then proceed based on the rule that each number is equal to the sum of the preceding two numbers.

It’s a method used to build an extended binary tree with a minimum weighted path length from a given weight set. It’s a lossless data compression algorithm.