Data Structure Array - Introduction - DSA
Powered by Blogger.

Thursday, May 5, 2022

Data Structure Array - Introduction

A list of a finite number of homogenous data elements that have the same type is called an array. an array can be classified in terms of dimensions as shown below.

Data Structure Array - Introduction

Types of the array in Data Structure

  1. Linear/One-dimensional arrays
  2. Two-dimensional arrays
  3. Multi-dimensional arrays

How to access elements of the array

As we know that an array has homogeneous elements. so to access the element of the array we use the index number. each element of the array is always referred to with an index as the value of an array is always stored in memory in conjunctive locations.

Linear/One-dimensional array

A Linear array is a list of the finite number of elements of consecutive homogenous data that has the same type in a way that the element of an array can be referenced respectively by an index set consisting of n consecutive integer numbers. and the elements of the array are stored in successive memory locations in respective order.

Calculate the length of the number of data elements of an array can be obtained by the below-given formula
N = 1 + UB - LB
UB = upper bound of array
LB = lower bound of array

here n is the number of elements and if not stated about the upper and lower bound then we assume the index set of the array is the {1,2,...,n}.

Calculate element address of linear/one-dimensional array
Loc(A[K]) = base(A) + W x (K-LB)
Here
LB = lower bound of array
W = number of memory cells for a element of array
base(A) = base address of array
K = Index of current element

Two-dimensional array

A two-dimensional array is called a matrix of two-dimensional size m*n. where m is the number of rows and n is the number of columns. and the array will be represented by the memory block of m*n sequential memory locations. and the elements in the 2D array are stored in either column base order or row base order.

Row base order - In the row base order the element are stored row by row if the first n elements are stored in the first n location, then other elements are stored in the next n locations.

Column base order - In the column base order the element are stored column by column. first m elements are stored in the first m locations and other m elements are stored in other m locations.

Calculate the element address of the 2D array

If the row base order is followed by the array then the below-given formula is used to obtain the address of the element.
LOC(A[J,K]) = Base(A) + W*[n*(J-LB) + (K-LB)]

If the column base order is followed by the array then the below-given formula is used to obtain the address of the element.
LOC(A[J,K]) = Base(A) + W*[m*(K-LB)+(J-LB)]

where W is the number of the memory cells for a single element

Note - Two-dimensional array is denoted by the capital letters such as A, B, C, and elements are denoted by the corresponding lower letters with the suffixed with row and column index such as a(x,y),b(x,y).

where a is the element of the 2d array and x and y are the corresponding row and column index.

Multi-dimensional array

A multidimensional array is a matrix of size l*m*n*...*z. here the dimensions depend on the size of the matrix. for example, a three-dimensional array is the size of l*m*n. and for every multi-dimensional array, the data is stored in row base or column base order.

Find the element address of row base order.
LOC(A[l,J,K]) = Base(A) + W*[m x n x (l-LB)+n x (J-LB)+(K-LB)]

Find the element address of column base order.
LOC(A[l,J,K]) = Base(A) + W*[m x n x (l-LB)+m x (K-LB)+(J-LB)]


To use the array to store the data and also in real life we need to do some operations on it.

Operations on array

  1. Traverse
  2. Searching
  3. Insertion
  4. Deletion
  5. Merging
  6. Sorting

Traversing - Traversing means visiting each element of the array only once. we can access or visit the element by the index of the array if we have low and upper bounds. to traverse an array of size n we can use for loop to run for n time and traverse the array from the first element to the last element.

Searching - Searching is used to find the location of a given element. a search can be done with the linear or binary search approach.

Insertion - In an array Insertion is done in multiple locations like at the very first position or at the end or in the middle or at any particular position. to insert an element at any position like at the kth position then we need to first move the element that is at the kth position to the next position and then store the element at the kth position.

Deletion - As insertion-deletion is also performed on multiple locations like at first, last, middle, or from the kth position. after deletion, the size of the array is decreased by one or the size of memory that an element use.

Merging - Merging is a process of merging two or more arrays and combining all the elements and making one array.

Sorting - Sorting is a process of sorting the elements of an array in ascending or descending order.