1. Data Structure

Data Structure = Data + Structure

Data Structure means organizing data in such a way that it becomes easy to store, access, and process.

If data is properly structured, it becomes easier to search, update, and manage.

Example:

Problem (Messy Wardrobe)

Clothes are scattered everywhere.
It becomes difficult to find things.
It takes more time.

Solution (Organized Wardrobe)

Clothes are arranged properly.
Shirts in one place, pants in another place.
Things become easy to find.

Similarly, in computers we organize data in memory so that it can be processed easily and efficiently. This organized way is called Data Structure.

Definition:
A mathematical or logical model of a particular organization of data in memory is called a Data Structure.

Data Structure provides the knowledge of how data should be organized in memory so that programs become efficient and less complex.

2. Objectives of Data Structure

There are mainly two objectives of Data Structure:

1. To Identify Mathematical Model

To identify and create a useful mathematical model and operations for solving a problem.

2. Representation and Implementation

To determine the representation of the model and implement the operations to solve the problem.

Data:

Anything that gives information is called Data.

Examples

2G, 3G, 4G Internet data pack
Gmail messages
Files
Audio
Video
Student name
Student roll number

Structure

The representation or arrangement of data is called Structure.

Examples

Array
List
Graph

Data Structure

Formula:

Data Structure = Data + Structure

Definition:
Data Structure is a way to store and organize data so that it can be used efficiently.

3. types of data structures

1. Primitive Data Structure :-

• The data structure that are directly operated upon by machine level instructions are known as Primitive Data Structure.

Ex :- Integer, Float, Character, Boolean

• They have different representation on different computers.

• Integer takes:
→ 2 Bytes in 16-bit computer
→ 4 Bytes in 32-bit computer

Example:
Integer → 1, 2
Character → A

2. Non-Primitive Data Structure :-

• The data structure that are not directly operated upon by machine level instructions are known as Non-Primitive Data Structure.

Types of Non-Primitive Data Structure

(a) Linear Data Structure :-

Data elements are arranged in a sequential order.

Ex :- Array, Stack, Queue, Linked List

(b) Non-Linear Data Structure :-

Data elements are not arranged in a sequential order.

Ex :- Tree, Graph

Linear Data Structure :-

• The data structure which shows the relationship of adjacency between elements is known as Linear Data Structure.

• In this, each element has a predecessor and a successor.

Example:
Roll No. 1 → Roll No. 2 → Roll No. 3

• Elements are stored in sequential manner.

Ex :- Array, Stack, Queue, Linked List

Non-Linear Data Structure :-

• The data structure which does not show the relationship of adjacency between elements is known as Non-Linear Data Structure.

• In this, each element does not have a single predecessor and successor.

Example:
Roll No. 1
/ \
Roll No. 2 Roll No. 3

• Elements are stored in non-sequential manner.

Ex :- Tree, Graph

4. Operations on Data Structure

• The data which is stored in a data structure is processed by a set of operations.

1) Creation :-

• Creating a new data structure.

2) Insertion :-

• Adding a new data element into the data structure.

3) Deletion :-

• Removing a data element from the data structure.

4) Traversing :-

• Visiting each data element once in the data structure.

5) Sorting :-

• Arranging data in increasing or decreasing order.

6) Searching :-

• Finding the location of a data element in the data structure.

7) Merging :-

• Combining the data of two different sorted files into a single sorted file.

5. Array

Array :-

• An array can be defined as a collection of homogeneous (similar type) elements.

• Array elements are always stored in consecutive memory locations.

• Array can store multiple values which can be referenced by a single name.

Example :-

int A[30];

• Here A is the array name which can hold 30 integers.

Terminology of Array :-

1) Size :-

• The number of elements in an array is called the size / length / dimension of the array.

2) Type :-

• It represents the kind of data stored in array.

Ex :-
Integer array, Character array

3) Base Address :-

• The starting address of memory location where the first element of array is located is called base address.

4) Index / Subscript :-

• All elements in an array can be represented using subscript (index).

Ex :-
A[0], A[1], A[i]

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.

or

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

11. Address Calculation in 2D Array (Row Major Order)

When a 2D array is stored in memory, it occupies continuous memory locations.
To find the exact memory location of any element, we use a formula.

General Formula (Row Major Order)

For an array:

A [ R ] [ C ]

The address of element A[i][j] is:

Loc ( A [ i ] [ j ] ) = Base Address + Size × [ C × ( i − Lr ) + ( j − Lc ) ]

Meaning of Terms

Base Address (BA) → Starting address of array
Size → Size of each element (e.g., float = 4 bytes)
C → Total number of columns
i → Row index of element
j → Column index of element
Lr → Lower bound of row index
Lc → Lower bound of column index

Important Notes

In most languages (C/C++), indexing starts from 0
So:

Lr = 0
Lc = 0

Total columns:

C = Uc − Lc + 1

Total rows:

R = Ur − Lr + 1

Solved Example (Step-by-Step)

Question

Find the address of B[6][8]
Given:

Array: B[11][13]
Base Address = 1000
Type = float (size = 4 bytes)
Storage = Row Major Order

Step 1: Identify Values

i = 6
j = 8
BA = 1000
Size = 4 bytes
Rows (R) = 11
Columns (C) = 13

Since indexing starts from 0:

Lr = 0
Lc = 0

Step 2: Apply Formula

Loc( B [ 6 ] [ 8 ] ) = 1000 + 4 × [13 × (6 − 0) + (8 − 0)]

Step 3: Solve Inside Bracket

= 1000 + 4 × [13 × 6 + 8]
= 1000 + 4 × [78 + 8]
= 1000 + 4 × 86

Step 4: Final Calculation

= 1000 + 344
= 1344

Final Answer

Address of B [ 6 ] [ 8 ] = 1344

12. Basic Operations in Array (Traversal, Insertion, Deletion)

Arrays support three main basic operations:

1. Traversal
2. Insertion
3. Deletion

1. Traversing a Linear Array

Definition

Traversing means accessing each element of an array exactly once to perform some operation like printing, searching, or counting.

Example Array

A = [5, 7, 2, 4]
Index: 0 1 2 3

Lower Bound (LB) = 0
Upper Bound (UB) = 3

Algorithm (Traversal)

Procedure Traverse(A, LB, UB)
Step 1: Set K = LB
Step 2: Repeat while (K ≤ UB)
           Print A[K]
           K = K + 1
Step 3: Exi

Working

K = 0 → print 5
K = 1 → print 7
K = 2 → print 2
K = 3 → print 4
K = 4 → stop

2. Insertion in Array

Definition

Insertion means adding a new element at a specific position in the array.

Important Condition

Before insertion, check Overflow:

If (n + 1 > size) → Overflow

Types of Insertion

At beginning
At middle
At end (easy)

Example

A = [A, B, C, D]
Insert X at position 2

After shifting:

A = [A, B, X, C, D]

Algorithm (Insertion)

Procedure Insert(A, n, size, loc, item)

Step 1: If (n + 1 > size)
             Print "Overflow"
                     Exit
Step 2:  For K = n−1 down to loc
             A[K+1] = A[K]
Step 3: A[loc] = item
Step 4: n = n + 1
Step 5: Exit

Key Point

Elements are shifted right side to create space.

3. Deletion in Array

Definition

Deletion means removing an element from a specific position in the array.

Important Condition

Before deletion, check Underflow:

If (n == 0) → Underflow

Example

A = [A, B, C, D]
Delete element at position 1

After shifting:

A = [A, C, D]

Algorithm (Deletion)

Procedure Delete(A, n, loc)

Step 1: If (n == 0)
             Print "Underflow"
               Exit
Step 2: Data = A[loc]
Step 3: For K = loc to n−2
              A[K] = A[K+1]
Step 4: n = n − 1
Step 5: Print "Deleted element =", Data
Step 6: Exit

Key Point

Elements are shifted left side after deletion.

so,

Traversal accesses all elements, insertion adds a new element by shifting elements right, and deletion removes an element by shifting elements left.

Topics

Data Structure = Data + Structure

Example:

1. To Identify Mathematical Model

2. Representation and Implementation

Data:

Examples

Structure

Examples

Data Structure

1. Primitive Data Structure :-

2. Non-Primitive Data Structure :-

Types of Non-Primitive Data Structure

(a) Linear Data Structure :-

(b) Non-Linear Data Structure :-

Linear Data Structure :-

Non-Linear Data Structure :-

1) Creation :-

2) Insertion :-

3) Deletion :-

4) Traversing :-

5) Sorting :-

6) Searching :-

7) Merging :-

Array :-

Example :-

Terminology of Array :-

1) Size :-

2) Type :-

3) Base Address :-

4) Index / Subscript :-

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

Example:

Explanation:

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

Example:

Explanation:

3. Multi-Dimensional Array

Example:

Explanation:

Key Points

Example:

Index (Subscript) and Values

Memory Address Representation

Important Points

For Integer:

For Float:

Formula: Total Memory Occupied

Examples

For Integer Array

For Float Array

Key Points to Remember

Formula

Where:

Important Values

Total Number of Elements Formula

Example 1

Question:

Solution:

Final Answer: 1062

Example 2

Question:

Solution:

Final Answer: 1026

Total Number of Elements

Total Elements = 17

Definition

Simple Understanding

Syntax

Formal Definition

Example Program

Key Points to Remember

Real-Life Uses

Basic Concept

Two Ways to Store 2D Arrays in Memory

1️⃣ Row Major Order

2️⃣ Column Major Order

1. Row Major Order (Most Common)

Example

Memory Representation: