Annai Violet Arts and Science College

Department of Computer Science

Data Structures and Algorithms

Sub Code : 225C4A

A data structure is a way of organizing and storing data so that it can be accessed and
modified efficiently. It is used to manage large amounts of data for processing, storage, and
retrieval.

Types of Data Structures:

1. Linear Data Structures: Array, Linked List, Stack, Queue

2. Non-Linear Data Structures: Tree, Graph, Hash Table

Diagram of Data Structures:

+----------------+
| Data Structure |
+----------------+
|
-----------------------------------
| |
+---------+ +---------+
| Linear | | Non-Linear |
+---------+ +---------+
| |
---------- ----------------
| Array | | Tree | Graph |
| List | ----------------
| Stack |
| Queue |
----------

A sparse matrix is a matrix in which most of the elements are zero. It is stored efficiently using
different representations to save memory.

Representation Methods:

1. Array Representation: Using a 2D array (inefficient).

 2. Linked List Representation: Each non-zero element is stored as a node with row index,
column index, and value.
3. Compressed Sparse Row (CSR): Stores only non-zero elements in three arrays: values,
row indices, and column indices.

Example of Sparse Matrix:

0 0 3 0
0 4 0 0
2 0 0 5

Triplet Representation:

Row | Col | Value

------------------
0 | 2 | 3
1 | 1 | 4
2 | 0 | 2
2 | 3 | 5

Complexity Definition Example

Time Measures the number of operations required Sorting an array takes O(n log
Complexity by an algorithm as a function of input size (n). n) in Merge Sort.
Space Measures the amount of memory required by A recursive function uses O(n)
Complexity an algorithm. memory due to the call stack.

A linear list is a data structure where elements are arranged in a sequential order. Examples
include arrays and linked lists.

Example of Linear List (Array):

Index: 0 1 2 3 4
Value: 10 20 30 40 50

A Singly Linked List consists of nodes where each node contains:

1. Data
2. A pointer to the next node

Operations:

1. Insertion – Adding a node at the beginning, middle, or end.

 2. Deletion – Removing a node from the list.

Diagram of a Singly Linked List:

[10 | *] → [20 | *] → [30 | *] → NULL

Define Circularly Linked List

A Circular Linked List is a linked list where the last node points back to the first node instead
of NULL.

Example Diagram:

[10 | *] → [20 | *] → [30 | *] → [10 | *] (circular)

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

Operations:

1. Push – Insert an element.

2. Pop – Remove an element.

Stack Representation:

TOP → [50]
[40]
[30]

Operations of a Stack and Its Applications

1. Push Adds an element to the top of the stack.

2. Pop Removes an element from the top of the stack.
3. Peek – Displays the top element
4. Applications: Expression evaluation, recursion, backtracking.

A queue is a linear data structure that follows FIFO (First In, First Out).

Operations of a Queue

1. Enqueue – Insert at rear.

2. Dequeue – Remove from front.
3. Peek – Get front element.
Queue Representation:

Front → [10] [20] [30] ← Rear

Main Use of a Queue

Queues are used for:

1. Task Scheduling – CPU scheduling, print spooling.

2. Data Streaming – Handling requests in real-time systems.
3. Breadth-First Search (BFS) in graph traversal.

A binary tree is a tree where each node has at most two children (left and right).

Example Binary Tree:

10
/ \
20 30
/ \
40 50

Feature Singly Linked List Doubly Linked List

Pointer One (next) Two (next, prev)
Traversal Only forward Forward & backward
Memory Uses less memory Uses more memory
Operations Insertion and deletion are slower Faster due to backward links

Representation of Arrays in Memory

Arrays are stored contiguously in memory, where the address of each element is calculated as:

Address of A[i] = Base Address + (i × size of element)

Operations on a Singly Linked List

1. Insertion
2. Deletion
3. Traversal
 4. Search

Types of Binary Tree Traversals

1. Inorder (L → R → Root)
2. Preorder (Root → L → R)
3. Postorder (L → R → Root)

Binary Tree Example

Consider the following binary tree:

A
/\
B C
/\ \
D E F

We will apply different traversal methods to this tree.

Inorder Traversal (Left → Root → Right)

 Traverse the left subtree.

 Visit the root node.
 Traverse the right subtree.

Step-by-Step Execution:

1. Traverse left subtree of A → Go to B

2. Traverse left subtree of B → Go to D
3. D has no left child → Visit D
4. Go back to B → Visit B
5. Traverse right subtree of B → Go to E
6. E has no left child → Visit E
7. Go back to A → Visit A
8. Traverse right subtree of A → Go to C
9. C has no left child → Visit C
10. Traverse right subtree of C → Go to F
11. F has no left child → Visit F

Final Inorder Traversal Output:

D→B→E→A→C→F
Inorder Traversal Diagram
A
/\
(B) C
/\ \
(D) (E) (F)

Traversal Order: D → B → E → A → C → F

Preorder Traversal (Root → Left → Right)

 Visit the root node.

 Traverse the left subtree.
 Traverse the right subtree.

Step-by-Step Execution:

1. Visit A
2. Traverse left subtree of A → Go to B
3. Visit B
4. Traverse left subtree of B → Go to D
5. Visit D
6. Go back to B → Traverse right subtree → Go to E
7. Visit E
8. Go back to A → Traverse right subtree → Go to C
9. Visit C
10. Traverse right subtree of C → Go to F
11. Visit F

Final Preorder Traversal Output:

A→B→D→E→C→F
Preorder Traversal Diagram
(A)
/ \
(B) (C)
/ \ \
(D) (E) (F)

Traversal Order: A → B → D → E → C → F

Postorder Traversal (Left → Right → Root)

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

Step-by-Step Execution:

1. Traverse left subtree of A → Go to B

2. Traverse left subtree of B → Go to D
3. D has no children → Visit D
4. Go back to B → Traverse right subtree → Go to E
5. E has no children → Visit E
6. Go back to B → Visit B
7. Go back to A → Traverse right subtree → Go to C
8. Traverse right subtree of C → Go to F
9. F has no children → Visit F
10. Go back to C → Visit C
11. Go back to A → Visit A

Final Postorder Traversal Output:

D→E→B→F→C→A
Postorder Traversal Diagram
A
/\
B C
/\ \
(D) (E) (F)

Traversal Order: D → E → B → F → C → A

Infix to Postfix Conversion

 Infix Notation: Operators are placed between operands. Example: A + B

 Postfix Notation: Operators are placed after operands. Example: A B +
 Prefix Notation: Operators are placed before operands. Example: + A B

Infix notation requires operator precedence and parentheses to determine the order of
evaluation.

Postfix notation eliminates the need for parentheses, making it easier for computers to
evaluate expressions using stacks.
To convert an infix expression to postfix, use a stack to store operators while maintaining
precedence.

Algorithm Steps:

1. Scan the infix expression from left to right.

2. If the character is an operand (A-Z or 0-9), add it to the postfix expression.
3. *If the character is an operator (+, -, , /, ^):
o Pop from the stack all operators of higher or equal precedence and append them
to the postfix expression.
o Push the current operator onto the stack.
4. If the character is an opening parenthesis (, push it onto the stack.
5. If the character is a closing parenthesis ):
o Pop from the stack and append to the postfix expression until an opening
parenthesis ( is found.
o Remove the ( from the stack but do not add it to the output.
6. After scanning the entire expression, pop all remaining operators from the stack
and append them to the postfix expression.

Operator Precedence and Associativity

Operator Precedence Associativity

^ (Exponentiation) 3 Right to Left

* / (Multiplication, Division) 2 Left to Right

+ - (Addition, Subtraction) 1 Left to Right

Converting Infix to Postfix

Given Infix Expression:

A+B*C
Step-by-step Execution Using Stack
Step Symbol Stack (Operators) Postfix Expression

1 A (operand) - A

2 + (operator) + A

3 B (operand) + AB
Step Symbol Stack (Operators) Postfix Expression

4 * (operator) +, * (higher precedence) A B

5 C (operand) +, * ABC

6 End of expression Pop * ABC*

7 End of expression Pop + ABC*+

Final Postfix Expression:

ABC*+

Advantages of Postfix Notation

✅ No Parentheses Needed – Operator precedence is inherently maintained.

✅ Efficient Evaluation – Uses a stack, which simplifies execution.
✅ Easier for Computers – No need for complex parsing rules.

10. Conclusion

 Converting Infix to Postfix is essential in compilers and expression evaluation.

 The stack helps maintain operator precedence and associativity.
 Postfix notation makes expression evaluation faster and efficient.

Would you like a step-by-step animation or more examples? 😊

Differences Between Linear and Circular Queue

Feature Linear Queue Circular Queue

Overflow Occurs when rear reaches the end No overflow (wrap-around)
Memory Wastes space Efficient memory usage

AVL Tree and Balancing Mechanism

An AVL tree is a self-balancing binary search tree where the height difference (balance factor)
is at most 1.
Balancing is done using Rotations:

1. LL Rotation
2. RR Rotation
3. LR Rotation
4. RL Rotation

Applications of Linked Lists

1. Dynamic Memory Allocation

2. Undo/Redo operations
3. Graph Representation