### Array

Array is a collection which can hold a fixed number of items and these items should be of the same type.Items in the array stored in adjacent memory location a such a way that position of any item in array can be calculated by math formula.We will refer any item of array as Element and position of element as Index.Memory address of first element in array is called Base Address which is a reference point to find out absolute address for other elements in array.

Position of first element in array in at zero index.

 Element 19 34 54 92 12 99 345 34 98 154 Index 0 1 2 3 4 5 6 7 8 9 Memory Address 2000 2004 2008 2012 2016 2020 2024 2028 2032 2036

Above table is an example of array which has ten elements and we are assuming that base address is 2000 and size of each element is 4.We can easily see that

1. Index range is 0 to N-1 if number of elements are N.
2. ith element address is 2000 + 4*i. e.i (baseAddress) + (element size)*i

Operations on Array –

1. Traverse – Fetch/print all elements of array.
2. Insertion – Insert an element at index i.
3. Deletion – Delete an element at index i.
4. Update – Update an element at index i with new element.

Traverse operation

Traversing means doing something with elements of array for example we will simply print each element of array so we need to iterate through array using index and getting element at each index and printing it.

Assume Array Arr of size N. Traverse can be performed in following steps –

1. Index = 0
2. Repeat step 3 – 4 For Index 0 to N – 1.
3. Set Element E = Arr [ index ]
4. Print E.
5. End.

Example

 Element 13 15 34 Index 0 1 2
1. Index = 0
1. E = Arr [ 0 ]  = 13
2. Print 13.
2. Index = 1
1. E = Arr [ 1 ] = 15
2. Print 15.
3. Index = 2
1. E = Arr [ 2 ] = 34
2. Print 34.

Insertion Operation

In insertion operation we need to insert a new Element at given position.To perform insertion first step is all the elements from given position should be shifted to the next position.

Let’s consider

N = Size of array

Item = new element to be inserted.

itemPos = position of new item.

Insertion operation can be performed in following steps

1. Set N = N + 1
2. Set index = N – 1
3. Repeat step 4 and 5 until index > itemPos.
4. Arr [ index ] = Arr [ index – 1 ]
5. Index = index – 1
6. Arr [ itemPos ] = item
7. End.

Example

 Element 13 15 34 Index 0 1 2

Consider item = 12 and itemPos = 1

• N = N + 1 = 3 + 1 = 4
• Index  = N – 1 = 4 – 1 = 3
• Arr [ index ] = Arr [ index – 1]
• Arr [ 3 ] = Arr [ 2 ]
• Index = 2
 Element 13 15 34 34 Index 0 1 2 3
• Arr [ index ] = Arr [ index – 1]
• Arr [ 2 ] = Arr [ 1 ]
• Index = 1
 Element 13 15 15 34 Index 0 1 2 3

• At this point index is equal to itemPos, so no more shifts.
• Arr [ itemPos ] = item
• Arr [ 1 ] = 12
 Element 13 12 15 34 Index 0 1 2 3

Delete Operation

Delete operation removes Element from array at given index.

Let’s consider N = Size of array and itemPos = position of deleting item.

Delete operation can be performed in following steps

1. Index = itemPos
2. Repeat step 3 and 4 until index < N – 1
3. Arr [ index ] = Arr [ index + 1 ]
4. Index = index + 1
5. N = N – 1
6. End.

Example

 Element 13 12 15 34 Index 0 1 2 3

Consider itemPos = 1

• Index = 1
• Arr [ index ] = Arr [ index + 1 ]
• Arr [ 1 ] = Arr [ 2 ]
• Index = 2
 Element 13 15 15 34 Index 0 1 2 3
• Arr [ index ] = Arr [ index + 1 ]
• Arr [ 2 ] = Arr [ 3 ]
• Index = 3
 Element 13 15 34 34 Index 0 1 2 3
• N = N – 1 = 3 and last item is removed from memory.
 Element 13 15 34 Index 0 1 2

N = 3

Update operation

Update operation will update new Element at index.

Let’s consider N = Size of array and , Item = new element to be updated and itemPos = position of new item updated.

Update operation can be performed in following steps.

1. Arr [ itemPos ] = item
2. End

Example

 Element 13 15 34 Index 0 1 2

Consider item = 14 and itemPos = 1

• Arr [ itemPos ] = item
• Arr [ 1 ] = 14
 Element 13 14 34 Index 0 1 2