Pointer, Pointer Array
• Let DATA be any array
• A variable P is called a pointer if P points to an
element in DATA i.e if P contains the address of
an element in DATA.
e.g. int *p=&DATA[1];
• An array PTR is called a pointer array if each
element of PTR is a pointer
int *PTR[5];
ptr[1] =&DATA[1];
ptr[2] =&DATA[2];
31
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
indexed if any element of A called Ak can
be located and processed in time that is
independent of K
32
Traversing Linear Arrays
• Traversing is accessing and processing
each element of the data structure exactly
once.
Linear Array
•••
33
Traversing Linear Arrays
• Traversing is accessing and processing
each element of the data structure exactly
once.
Linear Array
•••
34
Traversing Linear Arrays
• Traversing is accessing and processing
each element of the data structure exactly
once.
Linear Array
•••
35
Traversing Linear Arrays
• Traversing is accessing and processing
each element of the data structure exactly
once.
Linear Array
•••
36
Traversing Linear Arrays
• Traversing is accessing and processing
each element of the data structure exactly
once.
Linear Array
•••
37
Traversing Linear Arrays
• Traversing is accessing and processing
each element of the data structure exactly
once.
Linear Array
•••
1. Repeat for K = LB to UB for( i=0;i<size;i++)
Apply PROCESS to LA[K] cout<<LA[i];
[End of Loop] #printf(“%d”,LA[i]);
2. Exit
38
Inserting and Deleting
• Insertion: Adding an element
– Beginning
– Middle
– End
• Deletion: Removing an element
– Beginning
– Middle
– End
39
Insertion
1 Ahmed 1 Ahmed
2 Mustafa 2 Mustafa
3 Ibrahim 3 Ibrahim
4 Awais 4 Awais
5 Imran 5 Imran
6 6 Ali
7 7
8 8
Insert a name at the End of Array
40
Insertion
1 Ahmed 1 Ahmed 1 Ahmed 1 Ahmed
2 Mustafa 2 Mustafa 2 Mustafa 2 Mustafa
3 Ibrahim 3 Ibrahim 3 Ibrahim 3 Mohsin
4 Awais 4 Awais 4 4 Ibrahim
5 Imran 5 5 Awais 5 Awais
6 6 Imran 6 Imran 6 Imran
7 7 7 7
8 8 8 8
Insert “Mohsin” as the 3rd Element of Array
Insertion is not Possible without loss of
data if the array is FULL
41
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 inserts 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
42
Deletion
1 Ahmed 1 Ahmed
2 Mustafa 2 Mustafa
3 Mohsin 3 Mohsin
4 Ibrahim 4 Ibrahim
5 Awais 5 Awais
6 Imran 6 Imran
7 Kamran 7
8 8
Deletion of name at the End of Array
43
Deletion
1 Ahmed 1 Ahmed 1 Ahmed 1 Ahmed
2 Mustafa 2 2 Mohsin 2 Mohsin
3 Mohsin 3 Mohsin 3 3 Ibrahim
4 Ibrahim 4 Ibrahim 4 Ibrahim 4 Awais
5 Awais 5 Awais 5 Awais 5
6 Imran 6 Imran 6 Imran 6 Imran
7 Kamran 7 Kamran 7 Kamran 7 Kamran
8 8 8 8
Deletion of record of “Mustafa” from the Array
44
Deletion
1 Ahmed
2 Mohsin
3 Ibrahim
4 Awais
5 Imran
6 Kamran
7
8
No data item can be deleted from an empty
array
45
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+1 to N:
[Move the Jth element upward] Set LA[J-1]:= LA[J]
3. [Reset the number N of elements] Set N := N - 1;
4. Exit
46
Linear Search
Algorithm linear_search (LA, K)
for each item in the list
if match item == value
return the item's location
end if
end for
end Algorithm
47
