Data Structures and
Algorithms (Arrays)
Jose Rizal University, Mandaluyong City, Philippines
References:
• Data Structures and Algorithms in JAVA
Goodrich and Tamassia (2004) John Wiley &
Sons, Inc.
• Data Structures & Algorithm Analysis
in C Mark Allan Weiss. (1993) Benjamin
Cummings Publishing Company,
Inc./Jemma, Inc., Philippines
2
First, a look at primitive
data types
The primitive or built-in variable types in Java are shown below:
3
Questions
• How important are these primitive data
types in developing our programs?
• What limitations regarding the use of
primitive data types can you imagine?
4
Introducing Arrays
Arrays are a very useful data structure provided by Java and other
programming languages.
– An array is a variable compose of a finite, ordered set of homogeneous
elements, i.e. elements of the same data type
– Individual elements of this sequence can be uniformly
referenced/updated/ etc. since it consumes a consecutive set of
memory locations
– is a set of pairs - index and a value 0
– forms 1
2
• one-dimensional array
3
• n-dimensional array
4
5
Question:
Based on the definition above, how can arrays address the limitations
of using primitive data types ?
5
Creating Arrays
• Arrays in Java are handled as objects (hence allocated
on heap)
• 2 data types
– base type or component type
– index type
• All data types (primitive and user-defined objects) can
be put into arrays
• To create an array, use the new keyword
• Java has special syntax for array type declaration:
int[] a = new int[5];
– int[] indicates a is array of integer variables
– int[5] indicates a will have 5 elements
• Each cells in the array are assigned default values (0 /
null / etc.) when array created
6
Array Indexing
• Java provides a special syntax for uniformly accessing cells in an
array
– Assume previous declaration of a:
• int[] a = new int[5];
– This in effect creates five int variables “named”:
• a[0] a[1] a[2] a[3] a[4]
– To modify contents of cell #2 to 6:
• a[2] = 6;
• This access mechanism is called array indexing
• 2 basic operations
– extraction and storing
• In Java, the same as with C and C++, array cells are indexed
beginning at 0 and going up to n-1 (n is number of cells)
• Beware of index numbers that exceed the array structure.
• Also, beware of starting the indexing at 0!
7
Example
If we use the following codes:
int[] arr1 = new int[5];
arr1[2] = 6;
Which cell in arr1 would contain the value
6?
8
Cell Index numbers
0 1 2 3 4
9
Handling arrays using
loops
Loops Are Useful for Processing Arrays
• Loop counter can be used to iterate
through index values
• Each iteration of loop thus processes a
different array element
10
Examples of handling
arrays
int i;
int[] arr1 = new int[5];
arr1[2] = 6;
for (i=0; i<5; i++)
{
arr1[i] = i * 10;
}
11
Exercise Questions
• In the above coding, how would you change
the size of the array to accommodate 10
integer values instead of 5?
• What would happen if:
– instead of i++, i– was used in the for loop
statement?
– if instead of i=0, i=1 was used?
– If instead of i<5, i<=5 was used?
• How would you describe the process of
assigning values into each cell in the array
without using a for loop?
12
If an array is declared to be A[n], then:
n = number of elements
If an array is declared to be A[n][m], then:
n*m = number of elements
If given n-dimensional array declaration,
A[b][c][d][e]..[n] = ∏b,c,..n
13
• To determine the ith element of a single-dimension
array: A[i] = α + (i) * esize
where:
α - base or starting address
i - element
esize - element size in bytes
• 2-dimensional arrays:
A[i][j] = α + [(i) * (UB2) + (j)] * esize
where: UB2 = upper bound of the 2nd dimension.
14
• 3-dimensional arrays:
A[i][j][k] = α + [(i) * (UB2) *(UB3) + (j)*(UB3)
+ (k)] * esize
where: UB2 = upper bound of the 2nd dimension;
UB3 = upper bound of the 3rd dimension
esize = element size in bytes
Typical esize: integer - 4 bytes
char - 1 byte
float - 4 bytes
15
Examples
1. Given A[10][3][3][6], α = 2000, esize=4
bytes:
a. find the formula to represent an
element in a 4-dimensional array.
b. find the total number of elements
c. find the address of A[2][2][0][4]
16
Examples
2. Given X[8][3][6][2][3],α = 3000, esize = 3
bytes
a. find the total number of elements
b. find the address of X[0][2][5][1][2]
17
Examples
3. Consider the following declaration:
class Myclass {
int A;
char [] B = new char[10];
float C;
char D;
}
Myclass class1 = new matrix [121][4][5];
matrix A1;
A. Compute the address of element A1[120][3][3] given that the
base address is 2000.
B. Assume that we do not the size of Myclass in number of bytes
but we know that the address of A1[20][2][3] is 2160. Give the
size of Myclass in bytes. Assume the base address is 2000.
18
