Data structure Unit 1 AKTU Special Part II

After understanding the basics of data structures if you haven’t checked that , please have a look on this ***part 1*, now here we are heading the first and most fundamental linear data structure is the Array. An array is a collection of elements of the same data type, stored in contiguous memory locations**, and accessed using a common name and an index.

Arrays form the building block for many other data structures such as matrices, strings, stacks, and queues. They are widely used because they allow random access to elements (directly accessing any element using its index in constant time).

In programming, arrays are extremely useful when we need to store and process large amounts of similar data. For example: - Storing marks of students in a class. - Representing matrices in mathematical computations. - Handling tabular data in memory.

Here we are going to cover

this part of syllabus from unit 1

• Definition and types of arrays (1-D, 2-D, 3-D, and n-D).
• Representation of arrays in memory (Row Major and Column Major Order).
• Derivation of index calculation formulae.
• Applications of arrays in computer science.
• Special case: Sparse matrices and their representations.

Introduction of Array

Definition

• Array is a linear data structure where all elements are arranged sequentially
• An Array is a collection of elements of the same data type stored at contiguous memory locations and accessed using a single name with the help of an index (or subscript).
• Indexing usually starts from 0 in most programming languages (C, C++, Java, Python).
• Arrays allow random access: any element can be accessed directly using its index in O(1) time.

here you can see integer type of data allocated contiguously using index starting from 0

Types of Arrays

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

• A linear list of elements stored sequentially in memory.
• Each element is accessed using a single index.
• example

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

// int : shows the type of data going to stored in the array
// arr : it is the name of array 
// [5] can be n : it shows the size of array , we have to say how much data we want to store , we have to declare it during array declaration time
// {} : shows data stored inside the {} braces , we are continously storing one after another 

// now we can access element like this 

printf("%d", arr[2]);  // Outputs 30

Implementation of 1-D

// this is C language implementation

#include <stdio.h>

int main() {
  int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };
  matrix[0][0] = 9;
  printf("%d", matrix[0][0]);  // Now outputs 9 instead of 1

  return 0;
}

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

• An array of arrays (also called a matrix).
• Each element is accessed using two indices: row and column.
• we can say array inside array .
• example

int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };

// The first dimension represents the number of rows [2], 
// while the second dimension represents the number of columns [3].
// The values are placed in row-order, and can be visualized like this:

// we can access it to write this 

printf("%d", matrix[0][2]);  // Outputs 2

you can visualize this like above what given

Implementation of 2-D

#include <stdio.h>

int main() {
  int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };

  int i, j;
  for (i = 0; i < 2; i++) {
    for (j = 0; j < 3; j++) {
      printf("%d\n", matrix[i][j]);
    }
  }

  return 0;
}

3. Three-Dimensional Array (3-D Array)

• An array of 2-D arrays, representing data in three dimensions.
• Each element is accessed using three indices: (i, j, k).
• example

int arr[2][2][2] = {
    { {1, 2}, {3, 4} },
    { {5, 6}, {7, 8} }
};

Implementation of 3-D

#include <stdio.h>

int main() {
  // A 3D array with 2 blocks, each with 4 rows and 3 columns
  int example[2][4][3] = {
    {
      {1, 2, 3}, {4, 5, 6}, {7, 8, 9},
    },
    {
      {10, 11, 12}, {13, 14, 15}, {16, 17, 18}
    }
  };

  // Print all elements using 3 nested loops
  for (int i = 0; i < 2; i++) {
    printf("Block %d:\n", i + 1);
    for (int j = 0; j < 4; j++) {
      for (int k = 0; k < 3; k++) {
        printf("%d ", example[i][j][k]);
      }
      printf("\n");
    }
    printf("\n");
  }

  return 0;
}

4. n-Dimensional Array (n-D Array)

• Generalization of arrays into n dimensions.
• Each element is accessed using n indices.
• Used in advanced applications such as scientific computing, image processing, machine learning, and simulations.
• Example: a 4-D array may represent time-varying 3D data (x, y, z, t).

Representation of arrays in memory (Row Major and Column Major Order)

Although arrays may appear one-dimensional, two-dimensional, or multi-dimensional, the computer’s memory is linear (one-dimensional). Thus, a multidimensional array is always stored sequentially in memory either:

1. Row Major Order (C, C++, Java use this)
2. Column Major Order (FORTRAN, MATLAB often use this)

Let’s discuss the representation of array memory allocation using

1. Row Major Order

• In Row Major Order, the elements of the array are stored row by row in consecutive memory locations.
• All elements of the first row are stored first, then the second row, and so on.

as you can see the example here , row major order how allocates memory

2. Column Major Order

• In Column Major Order, the elements of the array are stored column by column in consecutive memory locations.
• All elements of the first column are stored first, then the second column, and so on.

this is how , column major order allocate memory

Derivation of Index Calculation Formulae

Arrays are stored in contiguous memory locations. To access any element, we must calculate its address in memory.

Let’s see the derivations

derived formula

1-D array Formula

2-D Row Major order finding address formula

2-D Column Major Order formula

3-D and N-D Array Row Major Order Formula

Applications of Arrays

Arrays are one of the most widely used data structures in both computer science and real life.

1. Applications in Computer Science

• Storing multiple values of same type (student marks, employee IDs, salaries, etc.).
• Searching and Sorting algorithms (Linear Search, Binary Search, Bubble Sort, Quick Sort).
• Implementation of other data structures: Stack, Queue, Deque, Circular Queue Matrix operations (addition, multiplication, transpose) Polynomial representation (coefficients stored in array)
• Used in Dynamic Programming (storing intermediate results).
• Used in Hashing, Graphs, and Heaps as underlying representation.
• Image Processing: Images are stored as 2-D or 3-D arrays (pixels, RGB values).

2. Real-Life Examples

• Railway reservation system → storing seat numbers as an array.
• Library system → storing list of books in an array.
• Timetable or Calendar → storing days of week and periods.
• Spreadsheets (Excel) → implemented internally as 2-D arrays.
• Gaming → chessboard (2-D array), Rubik’s cube (3-D array).

Special Case: Sparse Matrices

Definition

• A Sparse Matrix is a matrix in which most of the elements are zero.
• If the number of zero elements > non-zero elements, the matrix is called sparse.
• Direct storage wastes memory, so we use compact representations.

Why Sparse Representation?

• Saves memory (only non-zero elements are stored).
• Faster processing for certain operations (e.g., multiplication).
• Common in applications like networks, graphs, image compression.

Representations of Sparse Matrices

Sparse Matrix Representations can be done in many ways following are two common representations:

1. Array representation
2. Linked list representation

Method 1: Using Arrays

2D array is used to represent a sparse matrix in which there are three rows named as

• Row: Index of row, where non-zero element is located
• Column: Index of column, where non-zero element is located
• Value: Value of the non zero element located at index — (row,column)

as you can see here row 0 ,1 and 3 has non zero element that’s why it is including ,similar to this column

Time Complexity: O(NM), where N is the number of rows in the sparse matrix, and M is the number of columns in the sparse matrix.

Auxiliary Space: O(NM), where N is the number of rows in the sparse matrix, and M is the number of columns in the sparse matrix.

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:

• Row: Index of row, where non-zero element is located
• Column: Index of column, where non-zero element is located
• Value: Value of the non zero element located at index — (row,column)
• Next node: Address of the next node

here the linked list representation of sparse array

Time Complexity: O(N*M), where N is the number of rows in the sparse matrix, and M is the number of columns in the sparse matrix. Auxiliary Space: O(K), where K is the number of non-zero elements in the array.

Applications of Sparse Matrices

• Computer graphics & image processing (storing pixel data where most are black/white).
• Social networks (adjacency matrix of friends/followers).
• Scientific computing (finite element methods, simulations).
• Search engines (storing web links graph).

Conclusion

• Definition and types of arrays (1-D, 2-D, 3-D, and n-D) with implementations of all .
• Representation of arrays in memory (Row Major and Column Major Order).
• Derivation of index calculation formulae included all of the types 1-D , 2-D , 3-D and N-D.
• Applications of arrays in computer science and Real Life as well.
• Special case: Sparse matrices and their representations.

Thank You so Much Friends