ARRAY
Array is a container which can hold fix number of items and these items
should be of same type.
Most of the data structure make use of array to implement their
algorithms.
Following are important terms to understand the concepts of Array.
Element − Each item stored in an array is called an element.
Index − Each location of an element in an array has a numerical index which is
used
Arrays tobe
can identify the element.
classified as :
one-dimensional array
two-dimensional array
multidimensional array.
One-dimensional Array: It has only one row of elements. It is stored in ascending
storage location.
Two-dimensional Array: It consists of multiple rows and columns of data elements. It is
also called as a matrix.
Multidimensional Array: Multidimensional arrays can be defined as array of arrays.
Multidimensional arrays are not bounded to two indices or two dimensions. They can
include as many indices as required.
Limitations:
Arrays are of fixed size.
Data elements are stored in contiguous memory locations which may
not be always available.
Insertion and deletion of elements can be problematic because of
shifting of elements from their positions.
However, these limitations can be solved by using linked lists.
Applications:
Storing list of data elements belonging to same data type
Auxiliary storage for other data structures
Storage of binary tree elements of fixed count
Storage of matrices
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
4
Linear
Arrays
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 5
Linear
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[1], A[2], ….. ,
A[n]
The number K in A[K] is called
subscript or an index and A[K] is
called a subscripted variable
6
Representation of Linear Array in Memory
100
0
100
1
100
2
100
3
100 :
4
100 Computer Memory
5
7
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
8
Representation of Linear Array in Memory
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]
9
Example 1
200 LA[1]
Find the address for LA[6] 201 LA[2]
Each element of the array
202 LA[3]
occupy 1 byte
203 LA[4]
204 LA[5]
205 LA[6]
206 LA[7]
207 LA[8]
LOC(LA[K]) = Base(LA) + w(K – lower :
bound)
LOC(LA[6]) = 200 + 1(6 – 1) = 205 10
Example 2
200
Find the address for LA[16] LA[1]
201
Each element of the array
202
occupy 2 byte LA[2]
203
204
LA[3]
205
206
LA[4]
207
LOC(LA[K]) = Base(LA) + w(K – lower :
bound)
LOC(LA[16]) = 200 + 2(16 – 1) = 230 11
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
12
Basic Operations
Following are the basic operations supported by an array.
Traverse − print all the array elements one by one.
Insertion − add an element at given index.
Deletion − delete an element at given index.
Search − search an element using given index or by value.
Update − update an element at given index.
In C, when an array is initialized with size, then it assigns defaults
values to its elements in following order.
Data Type Default Value
bool false
char 0
Int 0
float 0.0
double 0.0f
void
wchar_t 0
Traversing Linear Arrays
Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones
Linear Array
•••
15
Traversing Linear Arrays
Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones
Linear Array
•••
16
Traversing Linear Arrays
Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones
Linear Array
•••
17
Traversing Linear Arrays
Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones
Linear Array
•••
18
Traversing Linear Arrays
Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones
Linear Array
•••
19
Traversing Linear Arrays
Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones
Linear Array
•••
20
Traversing Linear Arrays
Traversing is accessing and processing (aka visiting ) each element of
the data structure exactly ones
Linear Array
•••
1. Repeat for K = LB to UB
Apply PROCESS to LA[K]
[End of Loop] 21
2. Exit
Inserting and Deleting
Insertion: Adding an
element
Beginning
Middle
End
Deletion: Removing an
element
Beginning
Middle
End
22
Insertion Operation
Insert operation is to insert one or INSERT (LA, N , K , ITEM)
more data elements into an array.
[LA is a linear array with N
Based on the requirement, new elements and K is a positive
element can be added at the
beginning, end or any given index of integers such that K ≤ N. This
array. algorithm insert an element
Here, we see a practical ITEM into the Kth position in
implementation of insertion LA ]
operation, where we add data at the
end of the array − Algorithm
Let Array is a linear unordered array 1. [Initialize Counter] Set J := N
of MAX elements
2. Repeat Steps 3 and 4 while J ≥ K
Result
3. [Move the Jth element downward ]
Let LA is a Linear Array unordered Set LA[J + 1] := LA[J]
with N elements and K is a positive
integer such that K<=N. 4. [Decrease Counter] Set J := J -1
Below is the algorithm where ITEM is 5 [Insert Element] Set LA[K] := ITEM
inserted into the K th position of LA
6. [Reset N] Set N := N +1;
−
7. Exit
Deletion Operation
Deletion refers to removing DELETE (LA, N , K , ITEM) [LA is
an existing element from
the array and re-organizing a linear array with N elements
all elements of an
and K is a positive integers such
array. that K ≤ N. This algorithm deletes
Algorithm Consider LA is a Kth element from LA ]
linear array with N elements 1. Set ITEM := LA[K]
and K is a positive integer
such that K<=N. 2. Repeat for J = K to N -1:
Below is the algorithm to [Move the J + 1st
delete an element available
at the K th position of LA.
element upward] Set LA[J]
:= LA[J + 1]
3. [Reset the number N of elements]
Set N := N - 1;
4. Exit
Search Operation
You can perform a Start
search for array 2. Set J=0
element based on its
3. Repeat steps 4 and 5
value or its index.
while J < N
Algorithm
4. IF LA[J] is equal ITEM
Consider LA is a linear THEN GOTO STEP 6
array with N elements
5. Set J = J +1
and K is a positive
integer such that 6. PRINT J, ITEM
K<=N. 7. Stop
Below is the algorithm
to find an element with
a value of ITEM using
sequential search.
