■ DATA STRUCTURES

Complete Theory Notes

BCA II — 2025-2026

■ Arrays & Strings ■ Linked Lists

■ Stack ■ Queue

■ Binary Search Tree ■ Sorting Algorithms

■ Sparse Matrix ■ Time Complexity

 1. DATA STRUCTURE — INTRODUCTION

What is a Data Structure?

A data structure is a specialized format for organizing, storing, and processing data in a
computer so it can be used effectively. Choosing the right data structure is critical for optimizing the
performance (time and space complexity) of software systems.

Classification of Data Structures

■ LINEAR ■ NON-LINEAR

Elements arranged in one dimension (linear). Elements arranged in one-many / many-many

Sequential access. dimensions. Hierarchical.

Examples: Array, Linked List, Stack, Queue Examples: Tree, Graph, Hash Table

Data Structure Operations

■ Traversal Visit each node in a specific order. Used for printing, searching, displaying data.

■ Insertion Add new data elements to a data structure — at beginning, middle, or end.

■ Deletion Remove data elements that are no longer needed from the structure.

■ Search Find a specific element using a compare function to check equality.

■ Sort Arrange elements in a specific order using algorithms like Bubble, Merge, Quick Sort.

■ Merge Combine two data structures into one single structure.

■ Copy Create a duplicate by copying each element from original to the new structure.
 2. ARRAYS

What is an Array?
An array is a linear data structure that stores a collection of homogeneous elements (same data
type) in contiguous memory locations, allowing for efficient access using an index. Arrays are
represented as indexed buckets starting from 0.

Key Aspects of Array

■ Contiguous Memory Elements are stored in adjacent memory locations. Compiler calculates address using base addre

■ Indexing Elements identified by index ranging from 0 to n-1, where n is the size of array.

■ Static Sizing Arrays have a fixed size defined upon creation — memory is allocated statically.

Multi-Dimensional Arrays

2D Array 3D Array

Visualized as a table with m rows and n A collection of 2D arrays stacked on top of each
columns. Indexed as array[row][col]. In C, other. Indexed as array[x][m][n] where x =
rows: 0 to m-1, cols: 0 to n-1. number of 2D arrays.

Declaration: int arr[10][20]; Declaration: int arr[2][2][2];

Sparse Matrix

A matrix is called sparse when most of its elements are zero. A normal m×n matrix has m×n
values; a sparse matrix stores only non-zero elements to save space and time.

Why use Sparse Matrix?

• Storage: Fewer non-zero elements → less memory needed.

• Computing Time: Traversal only over non-zero elements → faster processing.

Representations:

1. Array Representation (2D): Uses 3 rows — Row index, Column index, Value of non-zero
element.

2. Linked List Representation: Each node has 4 fields: Row, Column, Value, and Next node
address.
 3. STRINGS

What is a String?
A string is a primitive data structure that stores a sequence of characters. It is used for storing,
manipulating, and processing text like user input, messages, labels. Internally, a string is
represented as an array of char data type.

Like arrays, strings use buckets indexed from 0 to n-1. Index always starts at 0, and each character
can be accessed via its index number.

Basic String Operations

■ Concatenation Joining two or more strings together into one.

■ Length Finding the total number of characters in a string.

✂■ Substring Extracting a portion (sub-part) from a larger string.

■ Reversing Printing or returning characters in reverse order.

■ Indexing Accessing a specific character using its position index.

■■ Deletion Removing a character at a given position by shifting remaining chars left.

■ Swapping Exchanging two string values using a temporary variable.

 4. TIME COMPLEXITY

What is Time Complexity?

When solving a problem, multiple approaches exist. Time complexity helps us evaluate and
compare these approaches based on how many steps an algorithm takes relative to the input size.

■ Best Case ■ Average Case ■ Worst Case

Occurs when first condition is Lies between best and worst. Occurs when no condition is
True immediately. Minimum Depends on True until the very last.
number of steps executed. distribution/likelihood of Maximum steps executed.
conditions.

Example: marks=95 → checks Example: marks=75 → checks Example: marks=45 → checks

1 condition → 3 steps total 3 conditions → 5 steps total all conditions → 7 steps total

Notation: Ω (Omega) Notation: Θ (Theta) Notation: O (Big-O)

 5. LINKED LIST

What is a Linked List?

A linked list is a linear data structure that stores a collection of nodes connected together via
pointers. Unlike arrays, linked list nodes are NOT stored at contiguous memory locations —
they are linked using pointers to different memory locations.

Each node has two parts:

• Data: The actual value stored in the node.

• Pointer: Memory address pointing to the next node in the list.

• The last node points to NULL, indicating end of the list.

• Linked lists can implement: Stack, Queue, Graph, Hash Maps, etc.

Types of Linked Lists

1■■ Singly Linked List 2■■ Doubly Linked List 3■■ Circular Linked List

Simplest type. Each node has More complex. Each node has Last node's pointer points back
data + one pointer (to next data + two pointers (next AND to first node. No NULL at end.
node). Traversal in one previous). Allows bidirectional Allows continuous circular
direction only. traversal. traversal.

HEAD → A → B → C → D NULL ← A ↔ B ↔ C ↔ D HEAD → A → B → C → D

→ NULL → NULL → (back to A)

Array vs Linked List — Key Difference

• Array: Contiguous memory, fixed size, fast random access via index — O(1).

• Linked List: Non-contiguous memory, dynamic size, sequential access — O(n).

• Array insertion/deletion requires shifting; Linked List only needs pointer update.
 6. STACK DATA STRUCTURE

What is a Stack?
A stack is a linear data structure that follows the LIFO (Last In First Out) principle. The last
element inserted is the first one removed. Both insertion and deletion happen from the same end
— the TOP of the stack.

Think of it like a stack of plates — you add and remove from the top!

Stack Operations

■■ PUSH Add (insert) an element at the top of the stack. O(1)

■■ POP Remove (delete) the element from the top of the stack. O(1)

■■ PEEK/TOP View the top element without removing it. O(1)

■ isEmpty Check whether the stack is empty or not. O(1)

■ Overflow Occurs when trying to PUSH into a full stack. Error

■ Underflow Occurs when trying to POP from an empty stack. Error

Applications of Stack

1. Function Calls When a function is called, its state is PUSHED onto stack. When it finishes, it is POPPED. Example

2. Recursion Stack stores a snapshot of each recursive call (local variables included). Example: For 3! — pushe

3. Expression EvaluationCompilers use stacks to evaluate postfix expressions. Example: '3 4 + 5 *' → push 3,4 → pop and a

4. Syntax Parsing IDEs check bracket matching. Every '(' or '{' is pushed; every ')' or '}' pops and checks match.

5. Memory ManagementCall Stack in RAM allocates memory for local variables automatically using LIFO. Memory is reclaim

6. Undo/Redo Operations
Text editors (Photoshop, VS Code) use stacks to track user actions for undo/redo functionality.

Stack: Advantages & Disadvantages

■ Advantages: Push/Pop in O(1) — constant time. Memory-efficient — stores only pushed

elements. LIFO order is useful for function calls, expression evaluation, backtracking.

■ Disadvantages: Only top element accessible — cannot retrieve middle elements. Stack overflow
if elements exceed capacity. Limited access pattern.
 7. POLISH NOTATIONS & CONVERSION

What are Notations?

Polish Notation is a method of expressing mathematical, logical, and algebraic equations
universally. Compilers use these notations to evaluate mathematical expressions based on their
order of operations. An arithmetic expression contains operands (numbers/variables) and
operators (symbols like +, -, *, /).

INFIX PREFIX (Polish) POSTFIX (Reverse Polish)

Operator is written between Operator is written before Operator is written after

operands. operands. operands.

Most common. Used by Also called Polish Notation. Also called Reverse Polish
humans. Hard for computers to Easy for recursive evaluation. Notation (RPN). Stack-based
parse. evaluation.

a + b + a b a b +

(3+7) (1*(2+3)) +37 *1(+23) 37+ (23+)1*

 8. QUEUE DATA STRUCTURE

What is a Queue?
A queue is a linear data structure that follows the FIFO (First In First Out) principle. The first
element inserted is the first one to be removed. Like a ticket queue outside a cinema — first person
in line gets the ticket first!

Insertion happens at the REAR and deletion happens at the FRONT.

Queue Operations

➡■ Enqueue Add an element at the REAR (end) of the queue. O(1)

■■ Dequeue Remove an element from the FRONT of the queue. O(1)

■ IsEmpty Check if the queue has no elements. O(1)

■ IsFull Check if the queue has reached maximum capacity. O(1)

■■ Peek/Front Get value of front element without removing it. O(1)

Types of Queues

Simple Queue Circular Queue Priority Queue Deque (Double

Ended)

Insertion at REAR, Last element points to Each element has a Insertion AND deletion
deletion at FRONT. first. No wasted space. priority. Higher priority from BOTH front and
Strictly follows FIFO. Better memory served first regardless rear. Does NOT follow
utilization. of order. strict FIFO.

Queue Implementation: Array vs Linked List

Array Implementation: Two types — (1) Fixed-size array with front, rear pointers and size/capacity
variables. (2) Infinite/dynamic array with only front pointer.

Linked List Implementation: Maintains a Node structure with data and next fields. Two pointers —
front (head of queue) and rear (tail of queue). Dynamic size, no overflow.

Applications of Queue

1. Customer Service Banking, airports, helplines — first come, first served (simple queue).

2. Print Spooling Multiple print jobs stored in queue, processed one by one by the printer.

3. Traffic Management Toll booths and traffic signals process vehicles in arrival order.

4. OS Scheduling CPU scheduling uses queues. Round-robin scheduling uses circular queues.
5. Data Buffers Network routers queue data packets before transmitting to destination.
 9. BINARY SEARCH TREE (BST)

What is a Binary Search Tree?

A Binary Search Tree (BST) is a hierarchical data structure that organizes data for efficient
searching, insertion, and deletion. It is a binary tree where each node has at most two children
and satisfies a specific ordering property.

BST Properties

■ Left Subtree All values in left subtree are STRICTLY LESS THAN the node's value.

■ Right Subtree All values in right subtree are STRICTLY GREATER THAN the node's value.

■ Node Structure Each node has: Data + Left Child pointer + Right Child pointer.

■ No Duplicates BST does NOT allow duplicate values. Each value must be unique.

■ Recursive Each subtree of a BST is itself a valid BST (recursive definition).

■ Efficiency Search, insert, delete operations are fast — O(log n) for balanced trees.

BST Traversal Methods

In-Order Left→Root→Right Pre-Order Root→Left→Right Post-Order

Left→Right→Root

Visit: Left subtree → Root node Visit: Root node → Left subtree Visit: Left subtree → Right
→ Right subtree. Gives nodes → Right subtree. Used for tree subtree → Root node. Used for
in ASCENDING ORDER for a copying and prefix expression. tree deletion and postfix
BST. expression.

Algorithm: 1. Algorithm: 1. Visit root Algorithm: 1.

Recursively traverse 2. Recursively traverse Recursively traverse
left 2. Visit root 3. left 3. Recursively left 2. Recursively
Recursively traverse traverse right traverse right 3. Visit
right root

■ ADVANTAGES ■ DISADVANTAGES

• Efficient O(log n) for balanced trees • Natural • Unbalanced tree degrades to O(n) • Complex
sorting via in-order traversal • Dynamic — can self-balancing logic needed • Extra memory for
grow/shrink • Hierarchical data organization • pointers • Recursive traversal may cause stack
Memory efficient for sparse datasets overflow • Deletion of nodes with 2 children is
complex
 10. SORTING ALGORITHMS

What is Sorting?
A sorting algorithm arranges elements of an array/list in a specific order (ascending or
descending). The efficiency of a sorting algorithm is determined by its Time Complexity and Space
Complexity.

Time Complexity Notations: Big-O O(worst), Omega Ω(best), Theta Θ(average)

Space Complexity: Total memory used — includes auxiliary memory + input size.

Sorting Complexity Comparison Table

Best Case Average Worst Case Space

Algorithm Stable?
Ω(n) Case Θ(n) O(n) Complexity

Bubble Sort O(n) O(n²) O(n²) O(1) ■ Yes

Selection Sort O(n²) O(n²) O(n²) O(1) ■ No

Insertion Sort O(n) O(n²) O(n²) O(1) ■ Yes

Merge Sort O(nlogn) O(nlogn) O(nlogn) O(n) ■ Yes

Quick Sort O(nlogn) O(nlogn) O(n²) O(logn) ■ No

Sorting Algorithms — Brief Description

■ Bubble Sort Repeatedly compares adjacent elements and swaps them if out of order. After each pass, the large

■ Selection Sort Finds the minimum element from unsorted portion and places it at the beginning. Divides array into

■ Insertion Sort Builds the sorted array one element at a time by inserting each element into its correct position. Eff

■ Merge Sort Divide and conquer algorithm. Divides array into halves, recursively sorts each half, then merges th

■ Quick Sort Divide and conquer. Picks a 'pivot' element and partitions array around it. Best average performanc
 ■ QUICK REVISION — KEY CONCEPTS
Topic Key Principle Important Points

Contiguous memory, fixed size, O(1) access, index

Array Index-based access
starts at 0

Dynamic size, non-contiguous, insertion/deletion

Linked List Pointer-based connection
easy

Stack LIFO — Last In First Out Push/Pop at TOP only, O(1) operations

Queue FIFO — First In First Out Enqueue at REAR, Dequeue at FRONT

BST Left < Root < Right O(log n) for balanced, in-order gives sorted output

Sparse Matrix Mostly zero elements Store only non-zero values using array or linked list

Operator between
Infix a+b — human readable, hard for computers
operands

Operator before
Prefix +ab — Polish Notation, recursive evaluation
operands

Postfix Operator after operands ab+ — Reverse Polish, stack-based evaluation

Time O(1) Constant time Stack push/pop, array index access

Time O(n) Linear time Array traversal, linked list search

Time O(logn) Logarithmic time BST search (balanced), binary search

Time O(n²) Quadratic time Bubble/Selection/Insertion sort worst case

Time O(nlogn) Linearithmic time Merge sort, Quick sort average case

■ Data Structures Theory Notes | BCA II | 2025-2026 ■ Best of Luck for Your Exams! ■