An array is a list of a finite number of homogenous data elements (i.e. data elements of the same type)

Arrays can be classified as

• One – dimensional array or linear array that requires only one index to access an individual element of the array.
• Two – dimensional arrays require two indices to access an individual element of the array. It is also called a matrix.
• Multi-dimensional arrays for which we need two or more indices.

An array is a collection of homogeneous elements.

1. We can access every element by an index number.
2. Each element is referred to with an index and the name of the array generally the index value starts with zero or one.
3. The array is stored in memory in conjunctive locations.

An array is a list of a finite number of elements of consecutive homogenous data elements of the same type) such that

1. The element of the array are referenced respectively by an index set consisting of n consecutive integer numbers
2. The elements of the array are stored respectively in successive memory locations.

The number n of elements is called the length or size of the array. If not explicitly stated, we will assume the index set consists of the integers 1,2… n. In general, the length or the number of data elements of the array can be obtained from the index set by the formula

LB is the Lower bound

UB is the upper bound

Loc (A [K]) = base (A) + W x (K – LB)

where

base(A) = is the base address of the array.

W = no. of the memory cell for a single element.

K = index of the current element.

LB = Lower Bound

Let A be a two – dimensional matrix of size m’n. Through a is pictured as a rectangular pattern with m row and n column. The array will be represented in memory by a block of m’n sequential memory location. However, the element can be stored in two different ways

1. COLUMN MAJOR ORDER: -The element is stored column by column i.e. the m elements of the first column are stored in the first m location, and elements of the second column are stored in the next m location and soon.
2. ROW MAJOR ORDER: -The element is stored row by row i.e. the n elements of the first row are stored in the first n location, and elements of the second row are stored in the next n location and soon.

where w=no, of the memory cell for a single element.

An m’n matrix is two – dimensional. Whose m, n elements are arranged in m row and n column. A matrix is denoted by capital letters such as A, B, C.. and its element are denoted by corresponding lower letters suffixed with row and column index such as a (j, k), b (j, k)……

Let A be a three-dimensional matrix of size I’m’n. The element can be stored in two different ways

The address LOC (A [I, J, K]) of the array can be obtained by this formula:

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

Traverse: -Traversing is the process of visiting each element of the array exactly once. As the elements can be accessed directly only we have to vary an index from lower bound to upper bound in the step of one to access individual elements in order For an array of size n, the loop executes n times so the traversal operation on linear arrays is O (n) operation.

Let ARR is a linear array with lower bound LB and upper bound UB. This algorithm traverses ARR applying an operation PROCESS to each element of LA.

Insertion: -To Insert an element at position k first we have to move elements starting from the kth position down by one position in order to accommodate the element at the kth position. The best possible case occurs when the item is inserted at the last position. In this case, no element is moved down. The worst case occurs when the element is to be inserted at the first position. In this case, all the elements are moved down. Therefore loop executes n time. Thus the complexity of the insertion operation is O (n) i.e. linear time.

Here ARR is the Linear array with N elements and POS is a positive integer such that POS < = N. This procedure inserts an element ITEM at position POS in array ARR of size N.

Deletion: Deletion refers to the operation of removing an element from an existing list of elements. After deletion, the linear array’s size is decreased by one factor. Like the insertion operation, deleting an element from the end of the linear array can be done very easily, However, to delete an element from any other location, the elements are to be moved upward: in order to fill up the location vacated by the removed element

Here ARR is the Linear array with N elements and PS is a positive integer such that POS < = N. This procedure removes an element ITEM from position POS in array ARR of size N.

Search Operations: -Searching is the process of finding the location of a given element in the linear array search is said to be successful if the given element is found i.e. the element does exist in the array, otherwise unsuccessful.

There are two approaches to the search operation

1. Linear search
2. Binary search

Linear Search: – Given no information about the array the only way to search for a given element item is to compare items with each element one by one. This method, which traverses a sequence to locate an item is called linear search or sequential search. In the best possible case, the item may occur in the first position. In this case, the search operation terminates in success with just one comparison. However, the worst case occurs when either the item is present at the last position or missing from the array. Thus in the worst case, the linear search is O (n) operations.

Here DATA is the Linear array with N elements and ITEM is a given item of information. This procedure finds the locations LOC of ITEM in A or sets LOC: 0 if the search is unsuccessful.

Binary Search: – This search is fast than linear search but it can be used only when the array is sorted. In this search we first find the mid of the array, if the value is found at the mid position then the search ends otherwise the number is searched in the left half or right half. This process is continued till the item is not found. In each iteration or in each recursive call, the search is reduced to one-half of the array. Therefore, for n elements in the array, there will be logan iterations or recursive calls. Thus the complexity of the binary search is O (log2n). This complexity will be the same irrespective of the position of the element, even if it is not present in the array.

Here DATA is the Linear array with N elements and ITEM is a given item of information. This procedure finds the locations LOC of ITEM in A or sets LOC: = 0 if the search is unsuccessful.

Merge Operation: – Merging is the process of combining the elements of two similar structures (linear arrays) into a single structure. Suppose that two arrays are sorted then our aim is to combine them in such a way that the combined array is also in the sorted order.

[This procedure merges two sorted arrays ARR1 and ARR2 into ARR3 of size N1, N2 and N1 + N2 respectively.]

1. Sorting Techniques in Data Structures
2. Stack in Data Structures
3. Queue in Data Structures
4. Operations on Stack
5. Matrix in Programming
6. Polish Notation in Data Structures