Data Structure

Subject Name: Data Structures

Subject Code: BE03000081
Semester: 3 (Bachelor of Engineering – GTU)
Unit: Section 2 – LINEAR DATA STRUCTURE Array
Prepared by: Prof. RR Keshwala
Academic Year: 2025–2026

LINEAR DATA STRUCTURE Array: Representation of arrays, Applications of arrays, sparse matrix and its
representation

ARRAY – INTRODUCTION & CHARACTERISTICS

What is an Array?
• An array is a linear data structure that stores a fixed-size sequential collection of elements of
the same data type in contiguous memory locations.
• It provides a simple, efficient way to store and access multiple values using a single variable
name and index.

“”An array is a collection of elements stored at contiguous memory locations, accessible using an
index.””
Why Arrays Are Needed?
Imagine you want to store marks of 100 students:
Without arrays:
int mark1, mark2, mark3, ..., mark100;
— Tedious, error-prone, and not scalable.
With arrays:
int marks[100];
— One variable handles all 100 values with efficient access like marks[0], marks[1], etc.

Real-Life Analogy:
Think of an array as:
• A row of lockers: numbered boxes (indices) containing items (values)
• A train with coaches: each coach (element) has a fixed position and same type (e.g.,
passenger coach)

Example in C (1D array declaration):

int arr[5] = {10, 20, 30, 40, 50};
Index Value
0 10
1 20
2 30
3 40
4 50

We access elements like: arr[2] gives 30.

P a g e 1 | 19
Data Structure

Characteristics / Features of Arrays

# Characteristic Explanation
1 Fixed Size Size must be declared at creation (e.g., int arr[10])
2 Homogeneous Elements All elements must be of the same data type (int, float, etc.)
3 Contiguous Memory All elements are stored next to each other in memory
4 Random Access Any element can be accessed directly using its index (O(1)
time)
5 Indexed Access Indexing starts from 0 up to n–1 (if size is n)
6 Efficient Traversal Elements can be looped using for, while, etc.
7 Static Memory Allocation Memory is allocated at compile time (for standard arrays)
8 Ease of Use Syntax is simple and operations are easy to implement
9 Multidimensional Support Arrays can be 1D, 2D, 3D and beyond
10 Limitation in Inserting/removing elements in the middle requires shifting
Insertion/Deletion

Advantages of Arrays

No. Advantage Simple Explanation

1 Fast Access You can quickly access any element using its index (like arr[3]
gives 4th element).
2 Easy to Traverse You can use loops (like for, while) to go through all elements
easily.
3 Simple to Declare & Use Array syntax is easy and clean: int a[5] = {1,2,3,4,5};
4 Contiguous Memory All elements are stored side by side in memory, which helps in
Allocation fast processing.
5 Useful for Fixed-Size Data Arrays are good when you know the number of items in
advance.
6 Foundation of Other Arrays are used in creating stack, queue, matrices, hash tables,
Structures etc.

Disadvantages of Arrays

No. Disadvantage Simple Explanation

1 Fixed Size You have to decide the size in advance; cannot grow or shrink
after that.
2 Insertion is Difficult Adding a value in the middle requires shifting all elements to
the right.
3 Deletion is Difficult Removing an element means shifting other elements to fill the
gap.
4 Wasted or Overflowed If size is too big → waste memory. If too small → no space for
Memory more data.
5 Only Same Type Allowed You can only store one data type (like all int or all float, not
mixed).
6 No Bounds Checking in Accessing outside the array (like arr[10] if size is 5) may crash
C/C++ or cause errors.

P a g e 2 | 19
Data Structure

Real-Life Comparison Example

Imagine a train with 10 coaches (array of seats):
• Pros:
o Each coach (element) has a fixed position → easy to find
o Simple layout → efficient for search
• Cons:
o You can't add/remove coaches dynamically.
o If a coach is empty, space is still reserved (wasted memory).

Summary:

Advantages Disadvantages
Fast access via index (O(1)) Fixed size, static allocation
Easy traversal Costly insertion/deletion
Cache-friendly Wasted memory if overestimated
Foundation for other DS Poor for dynamic use cases

Syntax and Declaration of Arrays in C

This section covers how to declare, initialize, and access arrays in C, including 1D array syntax with
examples.
1. Declaration of One-Dimensional Array
General Syntax:
data_type array_name[size];

Component Meaning
data_type Type of elements (e.g., int, float)
array_name Name of the array variable
size Total number of elements in the array

Example 1: Integer Array

int numbers[5];
• This declares an array named numbers which can hold 5 integers.
• Elements: numbers[0], numbers[1], ..., numbers[4]
Example 2: Float Array
float marks[3];
• Declares a float array with 3 elements: marks[0], marks[1], marks[2]

P a g e 3 | 19
Data Structure

2. Initialization of Array
Arrays can be initialized during or after declaration.
Method 1: Declaration + Initialization
int a[4] = {10, 20, 30, 40};
• Stores 10 in a[0], 20 in a[1], and so on.

Method 2: Partial Initialization

int b[5] = {5, 10};
• b[0] = 5, b[1] = 10, and remaining b[2] to b[4] are auto-filled with 0.

Method 3: Without Size (Compiler Counts Automatically)

int c[] = {2, 4, 6, 8};
• Compiler sets the size to 4 automatically.

Method 4: Assigning Values Later

int d[3];
d[0] = 100;
d[1] = 200;
d[2] = 300;

3. Accessing Array Elements

Array elements are accessed using indices starting from 0.
Example:
int num[3] = {10, 20, 30};

printf("%d", num[1]); // Output: 20

Important Notes:
• Index starts at 0, ends at size – 1.
• Accessing an index outside range causes undefined behavior.
• Array name (like arr) is a constant pointer to the first element &arr[0].

Example: Full Program for Declaration + Access

#include <stdio.h>
int main() {
int arr[5] = {2, 4, 6, 8, 10};

for (int i = 0; i < 5; i++) {

printf("arr[%d] = %d\n", i, arr[i]);

P a g e 4 | 19
Data Structure

}
return 0;
}
Summary Table
Declaration Style Example
Fixed size + values int a[4] = {1, 2, 3, 4};
Partial initialization int a[4] = {1, 2}; → rest = 0
Size auto-detected int a[] = {1, 2, 3};
Element-wise assignment a[0] = 5; a[1] = 10;

Memory Representation of One-Dimensional (1D) Arrays

Understanding how arrays are stored in memory helps students grasp how indexing, access time, and
pointer arithmetic work. This is essential for algorithm design, performance optimization, and
interview readiness.

How Is an Array Stored in Memory?

In a 1D array, all elements are stored in contiguous memory locations, meaning one after another,
without gaps.
Each element is stored at a memory address calculated using the base address and index.

Memory Address Calculation Formula

For any element arr[i] in a 1D array:
Address of arr[i] = Base address + (i × size of data type)
• i = index (starts from 0)
• size = number of bytes used by the data type (e.g., 4 bytes for int on most systems)

Example
int arr[4] = {10, 20, 30, 40};
Assume:
• int size = 4 bytes
• Base address = 1000

Index Value Memory Address

0 10 1000
1 20 1000 + (1 × 4) = 1004
2 30 1000 + (2 × 4) = 1008
3 40 1000 + (3 × 4) = 1012

P a g e 5 | 19
Data Structure

Code to Print Addresses

#include <stdio.h>
int main() {
int arr[4] = {10, 20, 30, 40};

for (int i = 0; i < 4; i++) {

printf("arr[%d] = %d, Address = %p\n", i, arr[i], &arr[i]);
}
return 0;
}
Output shows how addresses increase by 4 (for int) with each index.

Operations on 1D Arrays
Arrays support a wide range of operations essential for manipulating data. First, let’s look at the
summary table, and then we’ll explain each one in detail with examples and C programs.

Summary Table: Operations on 1D Arrays

Operation Description Time Complexity (Avg.

Case)
Access (Fetch) Get value at a specific index O(1)
Traversal Visit each element (e.g., display all elements) O(n)
Insertion Add element at beginning / middle / end O(n) (due to shifting)
Deletion Remove an element at a specific index or by value O(n)
Update Change the value at a particular index O(1)
Search Find a value by checking each element one by one O(n)
(Linear)
Search Find a value using divide & conquer (only for sorted O(log n)
(Binary) arrays)
Sort (Bubble) Sort elements by comparing and swapping O(n²)
repeatedly
Sort Insert elements into their correct position one-by- O(n²)
(Insertion) one
Sort Select smallest/largest and put in correct place O(n²)
(Selection)

1. Accessing (Fetching) Elements

Retrieve the value stored at a specific index.
C Code Example:
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50};
printf("Element at index 2: %d\n", arr[2]); // Output: 30
return 0;
}
Time Complexity: O(1)
Access is direct and does not depend on array size.
P a g e 6 | 19
Data Structure

2. Traversal (Looping Through Array)

Visit every element in the array (e.g., for printing or summing).
C Code Example:
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50};

printf("Array elements:\n");
for (int i = 0; i < 5; i++) {
printf("arr[%d] = %d\n", i, arr[i]);
}
return 0;
}
Time Complexity: O(n)
Each element is visited once.

3. Input + Traversal Example

This example shows how to take input values into a 1D array and then traverse (print) all the
elements.
C Code Example:
#include <stdio.h>
int main() {
int arr[100], n;

// Input: Get array size

printf("Enter the number of elements: ");
scanf("%d", &n);

// Input: Get array elements from user

printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
printf("Element [%d]: ", i);
scanf("%d", &arr[i]);
}
// Output: Traverse and print array elements
printf("\nArray elements are:\n");
for (int i = 0; i < n; i++) {
printf("arr[%d] = %d\n", i, arr[i]);
}
return 0;
}
Time Complexity:
• Input: O(n) – one scan per element
• Output (Traversal): O(n)

P a g e 7 | 19
Data Structure

Insertion in 1D Array – Algorithm Steps

To insert a new element into an existing array at the beginning, specific position (middle), or end.

Step-by-Step Algorithm:
1. Start
2. Declare an array arr[ ] and variables n (number of elements), val (value to insert), and pos
(position to insert).
3. Input n (number of elements in the array).
4. Input n elements into the array.
5. Ask the user for insertion type:
o 1 for beginning
o 2 for middle
o 3 for end
6. Input the value to be inserted (val).
7. If inserting at beginning:
o Shift all elements from end to start by one position.
o Place val at arr[0].
8. If inserting at middle (position pos):
o Ensure pos is in range (0 to n).
o Shift elements from end to pos by one position.
o Insert val at arr[pos].
9. If inserting at end:
o Place val at arr[n].
10. Increment n to reflect new size.
11. Display the updated array.
12. End

Full C Program: Insertion at Beginning, Middle, and End

#include <stdio.h>

int main() {
int arr[100], n, val, pos, choice;

// Step 1: Input initial array size

printf("Enter number of elements (max 100): ");
scanf("%d", &n);

// Step 2: Input array elements

printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
printf("Element [%d]: ", i);
scanf("%d", &arr[i]);
}

// Step 3: Menu for insertion type

printf("\nChoose insertion type:\n");
printf("1. Insert at Beginning\n");

P a g e 8 | 19
Data Structure

printf("2. Insert at Middle (specific position)\n");

printf("3. Insert at End\n");
printf("Enter your choice (1/2/3): ");
scanf("%d", &choice);

// Step 4: Input value to insert

printf("Enter the value to insert: ");
scanf("%d", &val);

// Step 5: Perform insertion based on choice

if (choice == 1) {
// Insert at beginning
for (int i = n; i > 0; i--) {
arr[i] = arr[i - 1];
}
arr[0] = val;
n++;
} else if (choice == 2) {
// Insert at middle
printf("Enter position (0 to %d): ", n);
scanf("%d", &pos);
if (pos < 0 || pos > n) {
printf("Invalid position!\n");
return 1;
}
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = val;
n++;
} else if (choice == 3) {
// Insert at end
arr[n] = val;
n++;
} else {
printf("Invalid choice!\n");
return 1;
}

// Step 6: Print the updated array

printf("\nArray after insertion:\n");
for (int i = 0; i < n; i++) {
printf("arr[%d] = %d\n", i, arr[i]);
}

return 0;
}

P a g e 9 | 19
Data Structure

Deletion in 1D Array – Algorithm Steps

To remove an element from an array at a specific position (beginning, middle, or end) and shift the
remaining elements accordingly.

Step-by-Step Algorithm:
1. Start
2. Declare an array arr[ ], size n, and variable pos for the position to delete.
3. Input the number of elements n and read n array elements.
4. Ask user for deletion type:
o 1 = Beginning
o 2 = Specific position (Middle)
o 3 = End
5. If deleting from beginning:
o Shift all elements left by one starting from index 1.
6. If deleting from a middle position (position pos):
o Check if pos is in valid range (0 to n-1).
o Shift elements left from pos+1 onward.
7. If deleting from end:
o Just reduce n by 1 (no shifting needed).
8. Decrement n (array size reduces).
9. Display the updated array.
10. End

Full C Program: Deletion from Beginning, Middle, and End

#include <stdio.h>
int main() {
int arr[100], n, pos, choice;

// Step 1: Input initial array size

printf("Enter number of elements (max 100): ");
scanf("%d", &n);

// Step 2: Input array elements

printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
printf("Element [%d]: ", i);
scanf("%d", &arr[i]);
}

// Step 3: Menu for deletion type

printf("\nChoose deletion type:\n");
printf("1. Delete from Beginning\n");
printf("2. Delete from Middle (specific position)\n");
printf("3. Delete from End\n");
printf("Enter your choice (1/2/3): ");
scanf("%d", &choice);

P a g e 10 | 19
Data Structure

// Step 4: Perform deletion based on choice

if (choice == 1) {
// Delete from beginning
for (int i = 0; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
n--;
} else if (choice == 2) {
// Delete from middle (specific position)
printf("Enter position to delete (0 to %d): ", n - 1);
scanf("%d", &pos);
if (pos < 0 || pos >= n) {
printf("Invalid position!\n");
return 1;
}
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
n--;
} else if (choice == 3) {
// Delete from end
n--;
} else {
printf("Invalid choice!\n");
return 1;
}

// Step 5: Print the updated array

printf("\nArray after deletion:\n");
for (int i = 0; i < n; i++) {
printf("arr[%d] = %d\n", i, arr[i]);
}

return 0;
}

Time Complexity:
• Beginning or Middle: O(n) due to shifting
• End: O(1)

5. Update Operation in 1D Array

Modify or change the value at a given index.

C Program for Update Operation:

#include <stdio.h>

P a g e 11 | 19
Data Structure

int main() {
int arr[100], n, pos, newVal;

// Input array
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
printf("arr[%d]: ", i);
scanf("%d", &arr[i]);
}

// Input position and new value

printf("\nEnter the index to update (0 to %d): ", n - 1);
scanf("%d", &pos);
if (pos < 0 || pos >= n) {
printf("Invalid index!\n");
return 1;
}

printf("Enter new value: ");

scanf("%d", &newVal);
arr[pos] = newVal;

// Output updated array

printf("\nUpdated array:\n");
for (int i = 0; i < n; i++) {
printf("arr[%d] = %d\n", i, arr[i]);
}

return 0;
}
Time Complexity: O(1)

6. Linear Search in 1D Array

Find the index of a given element by checking each one sequentially.
Algorithm Steps:
1. Start
2. Declare array arr[ ], size n, value key to search.
3. Input n and the array elements.
4. Input key to search.
5. Traverse array:
o If arr[i] == key, return index.
6. If not found, inform the user.
7. End

C Program for Linear Search:

P a g e 12 | 19
Data Structure

c
CopyEdit
#include <stdio.h>

int main() {
int arr[100], n, key, found = 0;

// Input array
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
printf("arr[%d]: ", i);
scanf("%d", &arr[i]);
}

// Input key to search

printf("\nEnter value to search: ");
scanf("%d", &key);

// Perform linear search

for (int i = 0; i < n; i++) {
if (arr[i] == key) {
printf("Element found at index %d\n", i);
found = 1;
break;
}
}

if (!found) {
printf("Element not found in the array.\n");
}

return 0;
}
Time Complexity: O(n)

7. Reverse Operation on 1D Array

To reverse the order of elements in a 1D array, i.e., the first becomes last, second becomes second-
last, and so on.

Algorithm Steps:
1. Start
2. Declare array arr[ ], size n, and loop counters i and j.
3. Input n and array elements.
4. Initialize two pointers:

P a g e 13 | 19
Data Structure

oi = 0 (start)
oj = n - 1 (end)
5. While i < j:
o Swap arr[i] and arr[j]
o Increment i, decrement j
6. Print the reversed array.
7. End

C Program to Reverse a 1D Array:

#include <stdio.h>
int main() {
int arr[100], n, temp;

// Input array
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
printf("arr[%d]: ", i);
scanf("%d", &arr[i]);
}

// Reverse the array in-place

for (int i = 0, j = n - 1; i < j; i++, j--) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

// Output reversed array

printf("\nReversed array:\n");
for (int i = 0; i < n; i++) {
printf("arr[%d] = %d\n", i, arr[i]);
}

return 0;
}
Time Complexity: O(n/2) = O(n)

Bubble Sorting:
1. Compare adjacent elements.
2. Swap them if they are in the wrong order.
3. Repeat for all elements until the entire array is sorted.
After each pass, the largest element is "bubbled" to its correct position at the end.

Example:
#include <stdio.h>

P a g e 14 | 19
Data Structure

int main() {
int arr[100], n, temp;

// Input
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Bubble Sort
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}

// Output
printf("Sorted array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
Time Complexity:
• Best Case: O(n) (if optimized)
• Worst/Average: O(n²)

2D Arrays – Introduction & Basics

What is a 2D Array?
A 2D array is a collection of elements arranged in rows and columns, forming a matrix-like structure.
It's essentially an “array of arrays”.
• Think of it like a table:
int marks[3][4]; // 3 rows × 4 columns

P a g e 15 | 19
Data Structure

Syntax of Declaration
data_type array_name[rows][columns];
Examples:
int a[3][4]; // 3 rows, 4 columns
float temperature[7][2]; // 7 days, 2 times/day
char name[5][10]; // 5 strings, each of length 10

Initialization of 2D Arrays
Method 1: Static Initialization
int a[2][3] = {
{1, 2, 3},
{4, 5, 6}
};
OR
int a[2][3] = {1, 2, 3, 4, 5, 6}; // Fills row-wise

Method 2: Partial Initialization

int b[2][3] = {{1}, {4, 5}}; // Remaining elements will be 0

Accessing Elements
a[0][0] = 5;
printf("%d", a[1][2]); // Access row 1, column 2
Access is always done using two indices: a[i][j]

Input/Output using Loops

Input Example:
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
scanf("%d", &a[i][j]);
}
}
P a g e 16 | 19
Data Structure

Output Example:
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
printf("%d ", a[i][j]);
}
printf("\n");
}

Key Points:
• Indexing starts from 0: a[0][0]
• Must specify both dimensions at declaration
• Cannot dynamically change dimensions at runtime in static arrays
• C stores 2D arrays in row-major order

.
Applications of 2D Arrays
2D arrays are extensively used in both academic problems and real-world applications due to their
structured format. Here’s a summary:

Summary Table: Real-Life Applications of 2D Arrays

Area / Domain Example Use Case

Matrix Operations Matrix addition, subtraction, multiplication, transpose, inverse,
determinant
Tabular Data Storage Marksheet (students × subjects), product tables, employee salary sheets
Games Chess board (8×8), Sudoku (9×9), Tic-Tac-Toe (3×3)
Image Processing Grayscale images → 2D matrix of pixels (intensity), color images → 3D
arrays
Graph Representation Adjacency matrix (for representing edges between nodes in a graph)
Weather / Sensor Days × Hours temperature readings, IoT data from multiple sensors
Data
Text Processing Storing multiple strings as char arrays: char name[10][20];
Sparse Matrix Efficient storage of large matrices with many zeros in scientific computing
Formats

Step 3: Storage Representation of 2D Arrays

Why It Matters:
In C, even a 2D array is stored in linear memory (RAM). Understanding how 2D arrays are stored
internally helps in:
• Calculating addresses manually
• Optimizing memory access
• Solving pointer-based problems

P a g e 17 | 19
Data Structure

1. Row-Major vs Column-Major Order

Order Description
Row-Major Elements are stored row by row (C, C++, Python use this)
Column-Major Elements are stored column by column (used in Fortran, MATLAB)

Example: 2D Array
int a[2][3] = {
{10, 20, 30},
{40, 50, 60}
};
Visual Layout:
Row 0 → 10 20 30
Row 1 → 40 50 60
In Row-Major memory:
Memory layout: [10] [20] [30] [40] [50] [60]
Indexes: a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2]

2. Address Calculation Formula

Let:
• B = base address
• W = word size (in bytes)
• a[i][j] = element at i-th row and j-th column
• ncols = total number of columns
•
Row-Major Order (used in C):
Address(a[i][j]) = B + W × (i × ncols + j)
Column-Major Order:
Address(a[i][j]) = B + W × (j × nrows + i)

Example Calculation
Given:
int a[3][4]; // 3 rows, 4 columns
int size = 4; // size of int = 4 bytes
Base address = 1000
Find Address of a[2][3]
Row-Major:
Address = 1000 + 4 × (2 × 4 + 3)
= 1000 + 4 × (8 + 3)
= 1000 + 4 × 11
= 1000 + 44
= 1044
Column-Major:
Address = 1000 + 4 × (3 × 3 + 2)
= 1000 + 4 × 11
= 1044

P a g e 18 | 19
Data Structure

General Formula Summary

Order Formula Used In
Row-Major Base + W × (i × cols + j) C, C++
Column-Major Base + W × (j × rows + i) Fortran

P a g e 19 | 19