## Friday, 1 November 2013

### Linear  Arrays

A linear array is a list of a finite number of n homogeneous data elements ( that is data elements of the same type) such that
The elements are of the arrays are referenced respectively by an index set consisting of n consecutive numbers
The elements of the arrays are stored respectively in successive memory locations .
The number n of elements is called the length or size of the array.
The index set consists of the integer 1, 2, … n
Length or the number of data elements of the array can be obtained from the index set by
Length = UB – LB + 1 where UB is the largest index called the upper bound and LB is the smallest index called the lower bound of the arrays .

Element of an array A may be denoted by
Subscript notation A1, A2, , …. , An
Parenthesis notation A(1), A(2), …. , A(n)
Bracket notation A, A, ….. , A[n]
The number K in A[K] is called subscript or an index and A[K] is called a subscripted variable

Related post :Data Structure vs Storage Structure

### Representation of Linear Array in Memory

Let LA be a linear array in the memory of the computer
LOC(LA[K]) = address of the element LA[K] of the array LA
The element of LA are stored in the successive memory cells

Computer does not need to keep  track of the address of every element of LA, but need to track only the address of the first element of the array denoted by Base(LA) called the base address of LA
LOC(LA[K]) = Base(LA) + w(K – lower bound) where w is the number of words per memory cell of the array LA [w is aka size of the data type] .

#### Example 1  :

Each element of the array occupy 1 byte

LOC(LA[K]) = Base(LA) + w(K – lower bound)
LOC(LA) = 200 + 1(6 – 1)  = 205

### Example 2:

Each element of the array occupy 2 byte
LOC(LA[K]) = Base(LA) + w(K – lower bound)

LOC(LA) = 200 + 2(16 – 1) =230

### Representation of Linear Array in Memory

Given any value of K, time to calculate LOC(LA[K]) is same
Given any subscript K one can access and locate  the content of  LA[K] without scanning any other element of LA
A collection A of data element is said to be index if any element of A called Ak can be located and processed in time that  is independent of K

### Traversing Linear Arrays

Traversing is accessing and processing (aka visiting ) each element of the data structure exactly ones

1.Repeat for K = Lower Bound to Upper Bound
Apply PROCESS to LA[K]
[End of Loop]
2.  Exit

## Insertion  in array

Beginning
Middle
End
DEMO 1
Insert  Ford at the  End  of Array

DEMO 2
Insert  Ford as the  3rd Element  of Array
Note :Insertion is not Possible without loss of data if the array is FULL

## Deletion in array

Deletion: Removing an element
Beginning
Middle
End
DEMO 1
Deletion of Wagner  at the  End  of Array

DEMO 2
Deletion of  Davis  from the  Array
No data item can be deleted from an empty  array

### Insertion Algorithm

INSERT (LA, N , K , ITEM)
[LA is a linear array with N elements and K is a positive integers such that K ≤ N. This algorithm insert an element ITEM into the Kth position in LA ]
1.   [Initialize Counter] Set J := N
2.   Repeat Steps 3 and 4 while J ≥ K
3.   [Move the Jth element downward ] Set LA[J + 1]   := LA[J]
4.   [Decrease Counter] Set J := J -1
5   [Insert Element] Set LA[K] := ITEM
6.   [Reset N] Set N := N +1;
7.   Exit

#### Deletion  Algorithm

DELETE (LA, N , K , ITEM)
[LA is a linear array with N elements and K is a positive integers such that K ≤ N. This algorithm deletes Kth element from  LA ]
1.   Set ITEM := LA[K]
2.   Repeat for J = K to N -1:
[Move the J + 1st element upward] Set LA[J]   := LA[J + 1]
3.   [Reset the number N of elements] Set N := N - 1;
4.   Exit