Continue from Array : Part-one
INSERT
Insertion refers to insert a new element at given index.To insert a new element We can shift elements from given index to last index one position forward and then update value at given index.Here we will Break the process into two parts
- Shifting
- Update
Shifting:
Example-4-> Consider following Array with size of ten elements in which five elements already added we will represent it with N = 5, now let’s insert new element 100 at index 2.
Notice that we need to insert new element at index 2 so shifting index must be greater than or equal to 2 but less than N.i.e. 2<=shifting Index<N ,starting from last index and it will increase number of elements in Array by one. Let’s take a variable shiftingIndex and set it to last index.
i.e shiftingIndex = N -1 = 4.
now perform following two operations until required condition is true.
- Array [ shiftingIndex + 1 ] = Array [ shiftingIndex ]
- shiftingIndex = shiftingIndex – 1
- At shiftingIndex = 4
- Array [ shiftingIndex + 1 ] = Array [ shiftingIndex ] = Array [ 5 ] = Array [ 4 ]
- shiftingIndex = shiftingIndex – 1 = 3
- At shiftingIndex = 3
- Array [ shiftingIndex + 1 ] = Array [ shiftingIndex ] = Array [ 4 ] = Array [ 3 ]
- shiftingIndex = shiftingIndex – 1 = 2
- At shiftingIndex = 2
- Array [ shiftingIndex + 1 ] = Array [ shiftingIndex ] = Array[ 3 ] = Array [ 2 ]
- shiftingIndex = shiftingIndex – 1 = 1
- Now required condition 2<=shifting Index<N becomes false and we stop here further shifting.
Update
Now perform update operation at given index with new value
i.e set Array[2] = 100 , so finally array will look like
Algorithm
- T = total elements in array
- N = number of elements already added.
- index = where new value to be inserted.
- shiftingIndex = index of element currently considering for shifting.
- newValue = value to be inserted.
- Set shiftingIndex = N-1.
- while ( shiftingIndex >=index ) repeat step 8 to 9.
- Array [ shiftingIndex + 1 ] = Array [ shiftingIndex ].
- shiftingIndex = shiftingIndex – 1.
- Array [index ] = newValue.
- N = N + 1
- Exit.
DELETE
Delete operation removes element from array at given index. So to delete an element from array we can shift elements from next to given index to last index one position backward and then remove reference of last element.
Example-5-> Consider Array
Let’s delete item 45 at index 1.Shift all elements from index 2 to 4 one position backward. Keep reference of current shifting which satisfy the condition 1<= Index<N-1. and perform following two operations at each step.
- Array [ index ] = Array [ index + 1 ]
- index = index + 1
- At index = 1
- Array [ 1 ] = Array [ 2 ]
- index = index + 1 = 2
- At index = 2
- Array [ 2 ] = Array [ 3 ]
- index = index + 1 = 3
- At index = 3
- Array [ 3 ] = Array [ 4 ]
- index = index + 1 = 4
- At index = 4 , required condition false thus we set memory reference in index = 4 null ( indication item not exits ). and decrease number of elements from array set N = N – 1.
- Array [ 4 ] = null
- N = N – 1
Algorithm
- N = number of elements in array
- index = position of element to be deleted.
- while ( index < N – 1 ) repeat step 4 to 5.
- Array [ index ] = Array [ index + 1 ].
- index = index + 1
- Array [ index ] = null.
- N = N – 1.
- Exit.
SEARCH
Searching has many applications like to check an element exist or not in a collection, find the place of element in a collection etc.
Here we will see how to get position on an element if it exist in collection otherwise we will set it to -1 or ‘not found’ something like that to indicate absence of element.
Example-6-> Consider Array
Let’s find the position of element 2 which exits at index 3.Compare each element from starting until we not find an element which is equal to element to be searched,if find such element we simply return current index otherwise return -1. perform following three operation, at initially index = 0.
- temp = Array [ index ]
- compare temp and given element
- index = index + 1
- At index = 0
- temp = Array [ 0 ] = 78
- now 78 not equal to 2
- index = index + 1 = 1
- At index = 1
- temp = Array [ 1 ] = 65
- now 65 not equal to 2
- index = index + 1 = 2
- At index = 2
- temp = Array [ 2 ] = 65
- now 65 not equal to 2
- index = index + 1 = 3
- At index = 3
- temp = Array [ 3 ] = 2
- now 2 equal to 2, so we return index 3 and exit.
Algorithm
- N = number of elements in array.
- element = element to be searched.
- temp = element at current observing index
- Set index = 0
- while ( index < N ) repeat step 5 to 9
- temp = Array [ index ].
- if temp == element.
- return index.
- index = index + 1.
- return -1
- Exit.