Data Structures and Algorithm_Arrays -1

Arrays

The basics of one of the most basic data structures

What is an array?

It is a finite, ordered collection of homogeneous data elements. The elements are always stored continously (successive memory locations) in memory.

Example of an array

Array index are used to refer each element in the array.

Base is the first element in the array. An array also has an upper bound and lower bound , Upper bound in the largest index and Lower bound the smallest .

The Length of an array is given as = ( Upper bound — Lower bound + 1)

As these elements are stored in successive memory locations, we can find the position of any elements if we know the base address and the space occupied by each element or W — the number of words per memory cell(this is in general same for all the elements — like 2bytes).

LOC — refers to location

LOC[K] = LOC[Base] + W( K — Lower bound)

Processes in an Array

A ) Traversing — Accessing or processing each element in the array exactly once

Algorithm

1. Set K = LB (Lower Bound)
2. For K ≤ UB , repeat steps 3 and 4
3. PROCESS A[K]
4. K = K +1
5. Exit

B) Inserting in Array — Adding another element in an array.

Yes, this writer wrote separate blogs for all these topics but forgot to write one which introduces all of them properly, so will be posting the links of all of them after their title

Insertion is discussed in detail in the below linked blog

Insertion in an array

C) Deletion in array — Involves removing an element from array.

Similar link below

Deletion from an Array

D) Merging — Joining two arrays together

Merging Two Arrays

TWO DIMENSIONAL ARRAYS

All caps and bold , yes that’s how important this concept is.

Arrays where elements are referred by two subscripts , Egs A[2][3]. Here, Two dimensional array m x n , contains m * n elements.

(Two dimensional arrays are very similar to the mathematical concepts of matrices)

There are two ways of representing 2D arrays

1. Row Major or Row by Row

1. Column Major or Column by Column

An example —

This converts a 2D array into 1D which helps in storage in memory.

(A simple trick to identify if a 2D array is row major or column major is to look at the ordered pairs

(1,1) (1,2)(1,3)(2,1)(2,2)(2,3) etc — This is row major storage ( The first row elements are stored first then the second and so on. — Here column index changes in ascending order while row index remains same)

The computer remembers the base address and figures out the location of all the others through usage of these formulas (for a 2D matrix of M X N — M rows, N columns and W is element size.)

1. If Row Major — LOC [J,K] = Base(A) + W[ M( J-1) + (K-1)] — Used in Fortran and Matlab
2. If Column Major — LOC [J,K] = Base(A) + W[ N( K-1) + (J-1)] — In C programming language

We can use arrays to Solve linear equations in algebra

Algorithm for Solving Algebra