Data Structure Answers

<Back

A1-Data-Structure

A data structure is a way of organizing the data so that the data can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers. (Source: Wiki Page)

A2-Data-Structure

• Linear: A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues
• Non-Linear: A data structure is said to be non-linear if traversal of nodes is nonlinear in nature.

Example:

• Graph
• Trees

A3-Data-Structure

• Insertion - Add a new data item in the given collection of data items.
• Deletion - Delete an existing data item from the given collection of data items.
• Traversal - Access each data item exactly once so that it can be processed.
• Searching - Find out the location of the data item if it exists in the given collection of data items.
• Sorting - Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.

A4-Data-Structure

• The size of the arrays is fixed, Linked Lists are Dynamic in size.
• Inserting and deleting a new element in an array of elements is expensive, Whereas both insertion and deletion can easily be done in Linked Lists.
• Random access is not allowed in Linked Listed.
• Extra memory space for a pointer is required with each element of the Linked list.
• Arrays have better cache locality that can make a pretty big difference in performance.

A5-Data-Structure

Stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements.

Basic operations of stack are:

• Push
• Pop
• Peek

Applications of Stack:

• Infix to Postfix Conversion using Stack
• Evaluation of Postfix Expression
• Reverse a String using Stack
• Implement two stacks in an array
• Check for balanced parentheses in an expression

A6-Data-Structure

Queue is a linear structure which follows the order is First In First Out (FIFO) to access elements.

Basic operations on queue:

• Enqueue
• Dequeue
• Front
• Rear

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added. Both Queues and Stacks can be implemented using Arrays and Linked Lists.

A7-Data-Structure

• 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
  

A8-Data-Structure

A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items – the data and a reference to the next node.

Types of Linked List:

1. Singly Linked List: In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL.

   Example:

            1->2->3->4->NULL
   

2. Doubly Linked List: Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node.

   Example:

            NULL<-1<->2<->3->NULL
   

3. Circular Linked List: Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list.

   Example:

            1->2->3->1
            [The next pointer of last node is pointing to the first]
   

A9-Data-Structure

• 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).

A10-Data-Structure

A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways:

• Method 1 (By making push operation costly)

  This method makes sure that newly entered element is always at the front of ‘q1’, so that pop operation just dequeues from ‘q1’. ‘q2’ is used to put every new element at front of ‘q1’.

  1. push(s, x) operation’s step are described below:
     • Enqueue x to q2
     • One by one dequeue everything from q1 and enqueue to q2.
     • Swap the names of q1 and q2
  2. pop(s) operation’s function are described below:
     • Dequeue an item from q1 and return it.

• Method 2 (By making pop operation costly)

  In push operation, the new element is always enqueued to q1. In pop() operation, if q2 is empty then all the elements except the last, are moved to q2. Finally the last element is dequeued from q1 and returned.

  1. push(s, x) operation:
     • Enqueue x to q1 (assuming size of q1 is unlimited).
  2. pop(s) operation:
     • One by one dequeue everything except the last element from q1 and enqueue to q2.
     • Dequeue the last item of q1, the dequeued item is result, store it.
     • Swap the names of q1 and q2
     • Return the item stored in step 2.

<Back