notes_stuff

This repo is snapshots of differencet book to have them accessible in nicely organized manner.

View on GitHub

Introduction to Getting Started with Array Data Structure

**Array** is a collection of items of the same variable type that are stored at contiguous memory locations. It is one of the most popular and simple data structure used in programming. In this article, we have decided to provide a complete guide for Arrays, which will help you to tackle any problem based on Arrays.

Array-data-structure-2

Table of Content

**Array** is a linear data structure that stores a collection of items of same data type in contiguous memory locations. Each item in an array is indexed starting with 0. We can directly access an array element by using its index value.

Basic terminologies of Array:

Memory representation of Array:

In an array, all the elements are stored in contiguous memory locations. So, if we initialize an array

Memory-Representation-of-Array-(1)

Declaration of Array:

Arrays can be declared in various ways in different languages. For better illustration, below are some language-specific array declarations:

// This array will store integer type element
int arr[5];      
// This array will store char type element
char arr[10];   
// This array will store float type element
float arr[20];

Initialization of Array:

Arrays can be initialized in different ways in different languages. Below are some language-specific array initializations:

int arr[] = { 1, 2, 3, 4, 5 };
char arr[5] = { 'a', 'b', 'c', 'd', 'e' };
float arr[10] = { 1.4, 2.0, 24, 5.0, 0.0 };

Importance of Array:

Assume there is a class of five students and if we have to keep records of their marks in examination then, we can do this by declaring five variables individual and keeping track of records but what if the number of students becomes very large, it would be challenging to manipulate and maintain the data.

What it means is that, we can use normal variables (v1, v2, v3, ..) when we have a small number of objects. But if we want to store a large number of instances, it becomes difficult to manage them with normal variables. **The idea of an array is to represent many instances in one variable**.

Importance-of-Array

Types of Arrays:

Arrays can be classified in two ways:

Types-of-Arrays

Types of Arrays on the basis of Memory Allocation:

**1. Static Arrays:**

In this type of array, memory is allocated at compile time having a fixed size of it. We cannot alter or update the size of this array. This type of memory allocation is also known as **static** or **compile-time** memory allocation. Here only a fixed size (i,e. the size that is mentioned in square brackets **[]**) of memory will be allocated for storage. In case, we don’t know the size of the array then if we declare a larger size and store a lesser number of elements will result in a wastage of memory or or we declare a lesser size than the number of elements then we won’t get enough memory to store all the elements. In such cases, static memory allocation is not preferred.

//Static Integer Array
int arr[5] = {1, 2, 3, 4, 5};

**2. Dynamic Arrays:**

In this type of array, memory is allocated at run time but not having a fixed size. Suppose, a user wants to declare any random size of an array, then we will not use astatic array, instead of that a dynamic array is used. This type of memory allocation is also known as **dynamic** or **run-time** memory allocation. It is used to specify the size of it during the run time of any program.

// Dynamic Integer Array
int* arr = new int[5];

Types of Arrays on the basis of Dimensions:

**1. One-dimensional Array(1-D Array):** You can imagine a 1d array as a row, where elements are stored one after another.

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

**2. Multi-dimensional Array:** A multi-dimensional array is an array with more than one dimension. We can use multidimensional array to store complex data in the form of tables, etc. We can have 2-D arrays, 3-D arrays, 4-D arrays and so on.

Two-Dimensional-Array(2-D-Array-or-Matrix)

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

Operations on Array**:**

1. Array Traversal:

Array traversal involves visiting all the elements of the array once. Below is the implementation of Array traversal in different Languages:

int arr[] = { 1, 2, 3, 4, 5 };
int len = sizeof(arr) / sizeof(arr[0]);
// Traversing over arr[]
for (int i = 0; i < len; i++) {
    cout << arr[i] << " ";

2. Insertion in Array:

We can insert one or multiple elements at any position in the array. Below is the implementation of Insertion in Array in different languages:

// Function to insert element
// at a specific position
void insertElement(int arr[], int n, int x, int pos)
{
    // shift elements to the right
    // which are on the right side of pos
    for (int i = n - 1; i >= pos; i--)
        arr[i + 1] = arr[i];
 
    arr[pos] = x;
}

Deletion in Array:

We can delete an element at any index in an array. Below is the implementation of Deletion of element in an array:

// To search a key to be deleted
int findElement(int arr[], int n, int key);

// Function to delete an element
int deleteElement(int arr[], int n, int key)
{
    // Find position of element to be deleted
    int pos = findElement(arr, n, key);

    if (pos == -1) {
        cout << "Element not found";
        return n;
    }

    // Deleting element
    int i;
    for (i = pos; i < n - 1; i++)
        arr[i] = arr[i + 1];

    return n - 1;
}

// Function to implement search operation
int findElement(int arr[], int n, int key)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == key)
            return i;
    // Return -1 if key is not found
    return -1;
}


#include <iostream>
using namespace std;

int main() {

    cout << "GFG!";
    return 0;
}

Searching in Array:

We can traverse over an array and search for an element. Below is the implementation of Deletion of element in an array:

// Function to implement search operation
int findElement(int arr[], int n, int key)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == key)
            return i;
 
    // If the key is not found
    return -1;
}

Complexity Analysis of Operations on Array:

Time Complexity:

Operation Best Case Average Case Worst Case
**Traversal** Ω(N) θ(N) O(N)
**Insertion** Ω(1) θ(N) O(N)
**Deletion** Ω(1) θ(N) O(N)
**Searching** Ω(1) θ(N) O(N)

Space Complexity:

Operation Best Case Average Case Worst Case
**Traversal** Ω(1) θ(1) O(1)
**Insertion** Ω(1) θ(N) O(N)
**Deletion** Ω(1) θ(N) O(N)
**Searching** Ω(1) θ(1) O(1)

[**Advantages of Array](https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-array-data-structure/#:~:text=Advantages%20of%20array%20data%20structure%3A):**

[**Disadvantages of Array](https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-array-data-structure/#:~:text=Disadvantages%20of%20array%20data%20structure):**

[**Applications of Array](https://www.geeksforgeeks.org/applications-advantages-and-disadvantages-of-array-data-structure/#:~:text=Applications%20of%20Array%20Data%20Structure):**

Frequently Asked Questions (FAQs) on Arrays:

**1. What is an array in data structure with example?**

An array is a collection of items of the same data type stored at contiguous memory locations. Ex. int arr[5] = {1,2,3,4,5};

2. Why array is a data structure?

Arrays store elements of the same type, they are classified as homogeneous data structures. They can store numbers, strings, characters, boolean values (true and false), objects, and so on.

3. What data structure is an array?

 An array is a **linear data structure** that stores similar elements in contiguous memory locations.

4. What are the types of arrays?

There are majorly two types of arrays:

5. How is data stored in an array?

An array is a collection of items of the same data type stored at contiguous memory locations or says the elements are stored one after another in memory. An array uses an index system starting at **0** and going to **(n-1), where **n** is its size.

6. Difference between array and structure?

The structure can contain variables of different types but an array only contains variables of the same type. 

7. What are the limitations of an array?

An array is a collection of items of the same data type. That means, in an integer array only integer values can be stored, while in a float array only floating values and character array can have only characters. Thus, no array can have values of two data types.

8. What are the advantages of an array?

There are multiple advantages of array data structure and some of them are:

9. What is the purpose of using arrays?

An array is used when several variables of the same type need to be used, and it can be defined as a sequence of objects of the same type.  

10. What is a multidimensional array?

A multi-dimensional array can be termed as an array of arrays that stores homogeneous data in tabular form. Data in Multidimensional Arrays are stored in row-major order. 

Conclusion

After the discussion, we concluded that arrays are a simple method of accessing elements of the same type by grouping them and we can find the elements efficiently by their indexes and can perform different operations using them. Thus, they are more efficient when it comes to memory allocation and should be used in all modern programming languages. So, this becomes a favorite topic for the perspective of the interview and most of the companies generally asked about the problems on the array. For all these reasons, we must have a good knowledge of it.

**Related articles:**

Previous

What is Array?

Next

Applications, Advantages and Disadvantages of Array

Row Major Order and Column Major Order ======================================

When it comes to organizing and accessing elements in a multi-dimensional array, two prevalent methods are **Row Major Order** and **Column Major Order**. These approaches define how elements are stored in memory and impact the efficiency of data access in computing.

Table of Content

Let us discuss them in detail one by one.

**Row Major Order**

Row major ordering assigns successive elements, moving across the rows and then down the next row, to successive memory locations. In simple language, the elements of an array are stored in a Row-Wise fashion.
To find the address of the element using row-major order uses the following formula:

**Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))**

I = Row Subset of an element whose address to be found, 
J = Column Subset of an element whose address to be found, 
B = Base address, 
W = Storage size of one element store in an array(in byte), 
LR = Lower Limit of row/start row index of the matrix(If not given assume it as zero), 
LC = Lower Limit of column/start column index of the matrix(If not given assume it as zero), 
N = Number of column given in the matrix.

**How to find address using Row Major Order?**

Given an array, **arr[1………10][1………15] with base value 100 and the size of each element is 1 Byte in memory. Find the address of arr[8][6]** with the help of row-major order.

**Solution:**

**Given:**
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1 
Lower Limit of column/start column index of matrix = 1
Number of column given in the matrix N = Upper Bound – Lower Bound + 1
                                                                            = 15 – 1 + 1
                                                                            = 15

**Formula:**
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC)) 

**Solution:**
Address of A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1))
                                   = 100 + 1 * ((7) * 15 + (5))
                                  = 100 + 1 * (110)
Address of A[I][J] = 210

**Column Major Order**

If elements of an array are stored in a column-major fashion means moving across the column and then to the next column then it’s in column-major order. To find the address of the element using column-major order use the following formula:

**Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))**

I = Row Subset of an element whose address to be found, 
J = Column Subset of an element whose address to be found, 
B = Base address, 
W = Storage size of one element store in any array(in byte), 
LR = Lower Limit of row/start row index of matrix(If not given assume it as zero), 
LC = Lower Limit of column/start column index of matrix(If not given assume it as zero), 
M = Number of rows given in the matrix.

**How to find address using Column Major Order?**

Given an array **arr[1………10][1………15] with a base value of 100 and the size of each element is 1 Byte** in memory find the address of arr[8][6] with the help of column-major order.

**Solution:**

**Given:**
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of Rows given in the matrix M = Upper Bound – Lower Bound + 1
                                                                            = 10 – 1 + 1
                                                                           = 10

**Formula: used**
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
Address of A[8][6] = 100 + 1 * ((6 – 1) * 10 + (8 – 1))
                                  = 100 + 1 * ((5) * 10 + (7))
                                 = 100 + 1 * (57)
Address of A[I][J] = 157

From the above examples, it can be observed that for the same position two different address locations are obtained that’s because in row-major order movement is done across the rows and then down to the next row, and in column-major order, first move down to the first column and then next column. So both the answers are right.

**Row Major Order vs Column Major Order**

**Aspect** **Row Major Order** **Column Major Order**
**Memory Organization** Elements are stored row by row in contiguous locations. Elements are stored column by column in contiguous locations.
**Memory Layout Example** For a 2D array A[m][n]: [A[0][0], A[0][1], …, A[m-1][n-1]] For the same array: [A[0][0], A[1][0], …, A[m-1][n-1]]
**Traversal Direction** Moves through the entire row before progressing to the next row. Moves through the entire column before progressing to the next column.
**Access Efficiency** Efficient for row-wise access, less efficient for column-wise access. Efficient for column-wise access, less efficient for row-wise access.
**Common Use Cases** Commonly used in languages like C and C++. Commonly used in languages like Fortran.
**Applications** Suitable for row-wise operations, e.g., image processing. Suitable for column-wise operations, e.g., matrix multiplication.

So it’s all based on the position of the element whose address is to be found for some cases the same answers is also obtained with row-major order and column-major order and for some cases, different answers are obtained.

Next

Performance analysis of Row major and Column major order of iterating arrays in C