■ Data Structures — Theory Definitions

Mumbai University · FE Sem II · NEP 2020 · Subject Code 10523

MODULE I — Introduction to Data Structures

Q: What is a Data Structure?

A data structure is a way of organizing and storing data in a computer so that it can be accessed and modified
efficiently. It defines both the data and the operations that can be performed on it.

✏■ Example: Array, Linked List, Stack, Queue, Tree

Q: What is an Abstract Data Type (ADT)?

An ADT defines the logical structure of data and the operations that can be performed on it, WITHOUT
specifying how those operations are implemented. It supports data hiding and encapsulation — you know
WHAT it does, not HOW.

✏■ Example: Stack ADT allows push, pop, peek, isEmpty — but doesn't say if it uses array or linked list internally.

Q: What are Linear vs Non-Linear Data Structures?

Linear: Every element is attached to its previous and next element in a sequence. Data is arranged in a single
level. Non-Linear: Elements are arranged in a hierarchical/multi-level order — not in a sequence.

✏■ Example: Linear → Array, Stack, Queue, Linked List | Non-Linear → Tree, Graph

Q: What are Static vs Dynamic Data Structures?

Static: Size is fixed at the time of declaration. Memory is allocated at compile time. Dynamic: Size grows or
shrinks at runtime. Memory is allocated/freed as needed.

✏■ Example: Static → Array (int arr[5]) | Dynamic → Linked List (nodes created using malloc)

Q: What are Primitive vs Non-Primitive Data Structures?

Primitive: Predefined by the system/language. These are basic data types. Non-Primitive: Derived or
user-defined. Built using primitive types.

✏■ Example: Primitive → int, float, char | Non-Primitive → Array, Struct, Linked List

Q: What are Homogeneous vs Non-Homogeneous Structures?

Homogeneous: All elements have the same data type. Non-Homogeneous: Elements can have different data
types.

✏■ Example: Homogeneous → Array (all int) | Non-Homogeneous → Structure/Union (int + char + float)

Q: What are Operations on Data Structures?

The basic operations that can be performed on any data structure are: • Traversal — visiting every element •
Insertion — adding a new element • Deletion — removing an element • Searching — finding an element •
Sorting — arranging in order • Merging — combining two structures
MODULE II — Stack

Q: What is a Stack?
A Stack is a linear, non-primitive data structure where insertion and deletion happen only from one end called
the TOP. It follows the LIFO (Last In First Out) principle — the last element inserted is the first one to be
removed.

✏■ Example: Like a stack of plates — you add/remove from the top only.

Q: What is Stack as an ADT?

Stack as ADT means it defines what operations are allowed (push, pop, peek, isEmpty, isFull, size, display)
without specifying whether it uses an array or linked list internally. The user only needs to know WHAT it does.

Q: What are the Applications of Stack?

1. Expression Parsing — converting/evaluating infix, postfix, prefix expressions 2. Function Calls — OS uses a
stack to track function calls (call stack) 3. Undo Feature — editors use stack to undo operations 4. Syntax
Checking by Compiler — checking balanced parentheses {}, [], () 5. String Reversal — push all characters,
then pop them

✏■ Example: cost() → area() → radius() → stored in call stack order

Q: What is Stack Overflow and Underflow?

Overflow: Trying to PUSH into a full stack (Top == N-1 for array). Underflow: Trying to POP from an empty
stack (Top == -1).

Q: What is a Two-Way (Multiple) Stack?

Two stacks sharing a single array. Stack 1 starts from index 0 (grows right), Stack 2 starts from the last index
(grows left). This leads to better memory utilization, efficient space management, and reduces unused
memory blocks.

✏■ Example: → [10 | 20 | 30 | _ | _ | 60 | 11 | 10] ← Stack1 and Stack2 share same array

MODULE III — Queue

Q: What is a Queue?
A Queue is a linear data structure that follows the FIFO (First In First Out) principle. Elements are inserted
from the REAR end and deleted from the FRONT end. Think of it like a real-life queue/line at a counter.

✏■ Example: People standing in a line — first person in is first to be served.

Q: What is ADT for Queue?

Queue ADT defines operations: Enqueue (insert at rear), Dequeue (remove from front), Peek/Front (see front
element), isEmpty, isFull — without specifying internal implementation.

Q: What is a Circular Queue?

 A circular queue treats the array as circular — when the rear reaches the last index, it wraps around to index 0
(if space is available). This eliminates the FALSE OVERFLOW problem found in linear queues. Overflow
condition: (rear + 1) % max == front (truly full) Formula used: rear = (rear + 1) % max

✏■ Example: Linear queue wastes space at front after dequeue. Circular queue reuses those freed slots.

Q: What is the Advantage of Circular Queue over Linear Queue?

In a linear (array-based) queue, after several enqueue/dequeue operations, the front pointer moves forward
and the space before it is WASTED even if the queue isn't full — this is called the False Overflow Problem.
Circular queue solves this by wrapping around and reusing freed slots.

Q: What is a Priority Queue?

A Priority Queue is a queue where each element has a priority. Elements with higher priority are served before
elements with lower priority, regardless of their order of arrival. Equal priority → FIFO order.

✏■ Example: Hospital emergency room — critical patients treated first regardless of arrival time.

Q: What is a Double Ended Queue (DEque)?

A Deque (Double Ended Queue) allows insertion and deletion from BOTH ends (front and rear). There are two
types: • Input Restricted Deque — insertion only at rear, deletion from both ends • Output Restricted Deque —
deletion only at front, insertion at both ends

✏■ Example: Like a deck of cards where you can add/remove from either end.

MODULE IV — Linked List

Q: What is a Linked List?

A Linked List is a linear data structure where each element (called a NODE) stores data AND a
pointer/address to the next node. Unlike arrays, nodes are NOT stored in contiguous memory locations —
they are scattered in memory and linked logically via pointers. Node Structure: struct Node { int data; struct
Node *next; };

✏■ Example: [10 | 1112] → [20 | 1012] → [30 | NULL] (data | address of next)

Q: Differentiate between Array and Linked List:

Parameter Array Linked List

Memory Contiguous (fixed block) Non-contiguous (dynamic via malloc)

Size Fixed at declaration Grows/shrinks at runtime

Access Direct (index-based), O(1) Sequential traversal, O(n)

Insertion/Deletion Slow — entire array shifts Fast — only 2 pointers change

Memory Overhead Stores only data Extra pointer per node

Q: What are the Types of Linked Lists?

 1. Singly Linked List — each node has data + pointer to NEXT node. Traversal only in forward direction. Last
node points to NULL. 2. Doubly Linked List — each node has data + pointer to NEXT + pointer to PREVIOUS.
Traversal in both directions. Prev of first and next of last = NULL. 3. Circular Linked List — last node's 'next'
points back to the FIRST node instead of NULL. Can be singly or doubly circular.

✏■ Example: Singly: [10|→] [20|→] [30|NULL] | Doubly: [NULL|10|→] ←[20|→] ←[30|NULL]

MODULE V — Trees & Binary Search Tree

Q: What is a Tree?
A Tree is a non-linear, hierarchical data structure with nodes connected by edges. One node is called the
ROOT and all other nodes are reachable from it. There are no cycles.

✏■ Example: File system of a computer — root folder, sub-folders, files.

Q: What are Tree Terminologies?

Term Meaning

Root Topmost node, has no parent

Leaf Node with NO children (degree = 0)

Height Longest path from root to a leaf

Level Level of root = 0; each step down adds 1

Degree Number of children of a node

Subtree A node and all its descendants

Edge Link/connection between two nodes

Q: What are the Types of Binary Trees?

1. Full Binary Tree — every node has EXACTLY 0 or 2 children. 2. Complete Binary Tree — all levels are
completely filled EXCEPT possibly the last level, which is filled from left to right. 3. Perfect Binary Tree — ALL
levels are completely filled. All leaves are at the same level. 4. Skewed Binary Tree — all nodes have only left
child (left-skewed) OR only right child (right-skewed). 5. Binary Search Tree (BST) — left subtree < root < right
subtree.

Q: What is a Binary Search Tree (BST)?

A BST is a binary tree where for every node N: • All values in the LEFT subtree are LESS THAN N's value • All
values in the RIGHT subtree are GREATER THAN N's value This property holds recursively for every node.
Rule: Left < Root < Right

✏■ Example: Insert 50, 40, 60, 70 → 40 goes left of 50, 60 goes right, 70 goes right of 60.

Q: What are Tree Traversals?

Traversal Order Use

Inorder Left → Root → Right Gives sorted output for BST

Preorder Root → Left → Right Copy a tree, prefix expressions

Postorder Left → Right → Root Delete a tree, postfix expressions

✏■ Example: For tree with root 50, left subtree {20,30,40}, right subtree {60,70,80}: Inorder: 20,30,40,50,60,70,80 |
Preorder: 50,30,20,40,70,60,80 | Postorder: 20,40,30,60,80,70,50

MODULE VI — Applications of Data Structures

Q: What is Infix, Prefix and Postfix Notation?

Infix: Operator is BETWEEN the operands. This is normal human notation. Prefix: Operator comes BEFORE
the operands. Also called Polish Notation. Postfix: Operator comes AFTER the operands. Also called Reverse
Polish Notation (RPN).

✏■ Example: Infix: A + B | Prefix: + A B | Postfix: A B + Infix: (A+B)*C | Prefix: *+ABC | Postfix: AB+C*

Q: What is an Expression Tree?

An Expression Tree is a binary tree used to represent arithmetic expressions. Operators are stored at internal
nodes and operands (numbers/variables) are stored at leaf nodes. • Inorder traversal gives INFIX expression •
Preorder traversal gives PREFIX expression • Postorder traversal gives POSTFIX expression Building rule:
Operator → pop from stack, Operand → push to stack.

✏■ Example: Expression: (a+b)/c → root is '/', left child is '+' (with leaves a,b), right child is 'c'

Q: What is Huffman Encoding?

Huffman Encoding is a lossless data compression technique where frequently used characters get shorter
binary codes and rarely used characters get longer codes. Algorithm: 1. Create a leaf node for each symbol
and add to a priority queue (min-heap by frequency) 2. While queue has more than 1 node: remove 2 nodes
with lowest frequency, create a parent node with frequency = sum of both, insert back 3. Remaining node =
root of Huffman tree 4. Assign codes: left edge = 0, right edge = 1. Code = path from root to leaf.

✏■ Example: A=20, B=12, C=33, D=25, E=40 → E (highest freq) gets shortest code; B (lowest) gets longest code.

Q: What is a Parentheses Checker (Balanced Parenthesis)?

A stack-based application to check if brackets in an expression are balanced. Rule: push opening brackets ({,
[, (); pop when closing bracket is found and check if they match. If stack is empty at end → BALANCED, else
→ UNBALANCED.

✏■ Example: {()[]{}} → push {, push (, ), pop (, push [, ], pop [, push {, }, pop { → Stack empty → Balanced

Q: What is String Reversal using Stack?

A simple stack application: 1. Push each character of the string onto the stack 2. Pop characters one by one
and append to a new string 3. The result is the reversed string Works because stack is LIFO — last character
pushed (last char of string) is popped first.

✏■ Example: String: 'abcde' → Push: a,b,c,d,e → Pop: e,d,c,b,a → Reversed: 'edcba'

■ Quick Revision — Key Points to Remember

Concept Key Point

Stack LIFO | Top | Push/Pop | Overflow (Top=N-1) | Underflow (Top=-1)

Queue FIFO | Front (delete) + Rear (insert) | Circular fixes false overflow

Linked List Node = data + pointer | Dynamic size | Sequential access only

BST Left < Root < Right | Inorder gives sorted sequence

ADT Defines WHAT not HOW | Encapsulation | Data hiding

Huffman High freq = short code | Low freq = long code | Lossless compression

Traversals Inorder=LNR | Preorder=NLR | Postorder=LRN

Made from your own notes ■ | Good luck for your exam! ■