DSA Notes

DSA

Software Engineering

Software Architecture

Operating System

Big Data

Data Mining and Warehousing

TOC

Ada

CPP

DBMS

All Topics (20)

1. Data Structure
2. Objectives of Data Structure
3. types of data structures
4. Operations on Data Structure
5. Array
6. Types of Arrays
7. Memory Representation of Array
8. Address Calculation in One-Dimensional Array
9. What is a Two-Dimensional Array? (With Simple Explanation & Example)
10. Representation of 2D Array in Memory (Row Major & Column Major Order)
11. Address Calculation in 2D Array (Row Major Order)
12. Basic Operations in Array (Traversal, Insertion, Deletion)
13. Sparse Matrix
14. Why Use Sparse Matrix Instead of Simple Matrix?
15. Advantages & Disadvantages of Array.
16. Linked List
17. Difference Between Array and Linked List.
18. Types of Linked List
19. Operations on Linked List
20. Dynamic Memory Allocation (DMA) vs Array vs Linked List

6. Types of Arrays

One-Dimensional Array (1-D Array)
Two-Dimensional Array (2-D Array)
Multi-Dimensional Array

1. One-Dimensional Array (1-D Array)

A one-dimensional array uses only one subscript (index) to access elements.
It stores elements in a single row (linear form).

Example:

int a[60];
char b[20];

Explanation:

a[60] means the array can store 60 integers.
Elements are accessed like: a[0], a[1], a[2] ...

2. Two-Dimensional Array (2-D Array)

A two-dimensional array uses two subscripts (row and column).
It is like a table (matrix) with rows and columns.

Example:

int a[20][30];

Explanation:

20 = number of rows
30 = number of columns
Elements are accessed like:
a[0][0], a[0][1], a[1][0] ...

3. Multi-Dimensional Array

An array with more than two dimensions is called a multi-dimensional array.

Example:

int a[10][20][30];

Explanation:

It has 3 dimensions.
Used for complex data structures.

Key Points

Subscript (index) is used to access array elements.
1-D → One index
2-D → Two indexes
Multi-D → More than two indexes

7. Memory Representation of Array

An array stores elements in continuous (contiguous) memory locations.

Example:

int A[5] = {10, 20, 30, 40, 50};

This is an array of integer elements
Size of array = 5

Index (Subscript) and Values

Index	Value
A[0]	10
A[1]	20
A[2]	30
A[3]	40
A[4]	50

Memory Address Representation

Assume base address = 1000

Index	Value	Address
A[0]	10	1000
A[1]	20	1002
A[2]	30	1004
A[3]	40	1006
A[4]	50	1008

Important Points

Each element is stored next to each other in memory
Address increases by size of data type

For Integer:

Size = 2 bytes
So address increases by 2

For Float:

Size = 4 bytes
So address increases by 4

Formula: Total Memory Occupied

Total Memory=Size of Array×Size of Data Type

Examples

For Integer Array

int A[5];
Size of int = 2 bytes
Total memory = 5 × 2 = 10 bytes

For Float Array

float A[5];
Size of float = 4 bytes
Total memory = 5 × 4 = 20 bytes

Key Points to Remember

Array elements are stored in continuous memory
First element address = Base Address
Formula for address:

$\text{Base Address} + (i \times \text{Size of Data Type})$

8. Address Calculation in One-Dimensional Array

To find the address of any element in an array, we use a formula.

Formula

Address of A[k] = Base(A)+W×(k−LB)

Where:

Base(A) = Base address (address of first element)
W = Size of each element (in bytes)
k = Index of required element
LB = Lower Bound (starting index)

Important Values

Data Type	Size (W)
int	2 bytes
float	4 bytes
char	1 byte

Total Number of Elements Formula

$Elements=UB−LB+1\text{Total Elements} = UB - LB + 1$

UB = Upper Bound
LB = Lower Bound

Example 1

Question:

Find address of A[6]
Given:

Array: A[9]
Base Address = 1050
Data type = integer
So, W = 2 bytes
LB = 0

Solution:

$A [6] = 1050 + 2 \times (6 - 0)$

Final Answer: 1062

Example 2

Question:

Find address of M[-3]
Given:

Range = (-9 to 7)
Base Address = 1002
Data type = float
So, W = 4 bytes
LB = -9

Solution:

M [−3] = 1002 + 4 × ( −3− ( −9 ))

M [−3] = 1002 + 4 × ( 6 )

M [−3] = 1002 + 24 = 1026

Final Answer: 1026

Total Number of Elements

Total Elements = 17

9. What is a Two-Dimensional Array? (With Simple Explanation & Example)

A two-dimensional array (2D array) is a type of array that stores data in the form of a table, made up of rows and columns.

That’s why it is also called a:

Matrix
Table
Grid

Definition

A two-dimensional array is a collection of elements arranged in rows and columns, where each element is identified using two indices:

First index → represents the row
Second index → represents the column

Simple Understanding

Think of it like an Excel sheet or a chessboard
Colume →
Row ↓ 0 1 2 3
0 1 2 3 4
1 5 6 7 8
2 9 10 11 12
3 13 14 15 16

Each value is accessed like this:

array [ row ] [ column ]

Example:

array[0][1] = 2
array[2][3] = 12

Syntax

int list [ 4 ] [ 4 ];

This means:

4 rows
4 columns
Total elements = 4 × 4 = 16

Formal Definition

If A is a 2D array of size m × n, then:

m = number of rows
n = number of columns

Each element is represented as:

A [ i ] [ j ]

Where:

i = row index (0 to m-1)
j = column index (0 to n-1)

Example Program

#include <stdio.h>
int main() {
int A[4][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
printf("Element at row 2, column 3: %d", A[2][3]);
return 0;
}

Output:

Element at row 2, column 3: 12

Key Points to Remember

a) A 2D array has two indices
b) Data is stored in row-column format
c) Used to represent matrices, tables, games, grids
d) Total elements = rows × columns

Real-Life Uses

Matrix calculations in mathematics
Image processing (pixels = rows × columns)
Game boards (like chess, sudoku)
Data tables (like spreadsheets)

10. Representation of 2D Array in Memory (Row Major & Column Major Order)

A two-dimensional array (2D array) is stored in memory as a linear (one-dimensional) sequence of memory locations.

Even though we write arrays in rows and columns, the computer stores them in continuous memory blocks.

A two-dimensional array is stored in memory as a linear sequence of elements. It can be represented using row major order (row-wise storage) or column major order (column-wise storage).

Basic Concept

Suppose we have an array:

int A [ m ] [ n ];

m = number of rows
n = number of columns
Total elements = m × n

These elements are stored in sequential memory locations, one after another.

Two Ways to Store 2D Arrays in Memory

There are two main techniques:

1️⃣ Row Major Order

2️⃣ Column Major Order

1. Row Major Order (Most Common)

In this method, elements are stored row by row.

✔ First row is stored completely
✔ Then second row
✔ Then third row… and so on

Example

int  A [ 3 ] [ 2 ]  = {
{ 10, 20 },
{ 30, 40 },
{ 50, 60 }
};

Memory Representation:

Address Value
1000    10 ←  A [ 0 ] [ 0 ]
1004    20 ←  A [ 0 ] [ 1 ]
1008    30 ←  A [ 1 ] [ 0 ]
1012    40 ←  A [ 1 ] [ 1 ]
1016    50 ←  A [ 2 ] [ 0 ]
1020    60 ←  A [ 2 ] [ 1 ]

Stored as:

10 → 20 → 30 → 40 → 50 → 60

Formula (Row Major Order)

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

Where:

i = row index
j = column index
n = total columns
size = size of each element (e.g., 4 bytes for int)

2. Column Major Order

In this method, elements are stored column by column.

✔ First column is stored completely
✔ Then second column
✔ Then third column…

Example

Same array :

int A [ 3 ] [ 2 ] = {
{ 10, 20 },
{ 30, 40 },
{ 50, 60 }
};

Memory Representation:

Address Value
1000    10 ← A [ 0 ] [ 0 ]
1004    30 ← A [ 1 ] [ 0 ]
1008    50 ← A [ 2 ] [ 0 ]
1012    20 ← A [ 0 ] [ 1 ]
1016    40 ← A [ 1 ] [ 1 ]
1020    60 ← A [ 2 ] [ 1 ]

Stored as:

10 → 30 → 50 → 20 → 40 → 60

Formula (Column Major Order)

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

Where:

m = total rows
i = row index
j = column index

Key Difference (Row vs Column Major)

Feature	Row Major Order	Column Major Order
Storage style	Row by row	Column by column
First stored	First row	First column
Used in	C, C++	Fortran, MATLAB

Page 2 of 4