Arrays
Array: motivation
You want to store 5 numbers in a computer
Define 5 variables, e.g. num1, num2, ..., num5
What, if you want to store 1000 numbers?
Defining 1000 variables is not feasible!
Requires much programming effort
Any better solution?
Yes, some structured data type
o Array is one of the most common structured data types
o Saves a lot of programming effort (cf. 1000 variable
names)
What is an Array?
A collection of data elements in which
all elements are of the same data type, hence
homogeneous data
o An array of students’ marks
o An array of students’ names
o An array of objects (OOP perspective!)
elements (or their references) are stored at
contiguous/ consecutive memory locations
Array is a static data structure
An array cannot grow or shrink during program
execution – its size is fixed
The array data structure
An array is an indexed sequence of components
Typically, the array occupies sequential storage locations
The length of the array is determined when the array is
created, and cannot be changed
Each component of the array has a fixed, unique index
Indices range from a lower bound to an upper bound
Any component of the array can be inspected
or updated by using its index
This is an efficient operation: O(1) = constant time
4
Basic concepts
Array name (data)
Index/subscript (0...9)
The slots are numbered sequentially
starting at zero (Java, C++)
If there are N slots in an array, the
index will be 0 through N-1
Array length = N = 10
Array size = N x Size of an element = 40
Direct access to an element
Array variations I
The array indices may be integers – Java
The lower bound is zero – Java
In most languages, arrays are homogeneous (all
components must have the same type); in some (Lisp,
Prolog) the components may be heterogeneous (of
varying types)
6
Homogeneity
All elements in the array must have the same
data type
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 30 45 50 60 65 70 80
Index: 0 1 2 3 4
Value: 5.5 10.2 18.5 45.6 60.5
Index: 0 1 2 3 4
Value: ‘A’ 10.2 55 ‘X’ 60.5 Not an array
Array variations II
In an object-oriented language, arrays may be objects
(Java) or not objects (C++)
Arrays may carry additional information about
themselves, such as type and length (Java), or may
consist only of their components (C, C++)
8
Arrays in Java I
Array indices are integers
An array of length n has bounds 0 and n-1
Arrays are homogeneous
However, an array of an object type may contain objects
of any subtype of that object
For example, an array of Animal may contain objects of type
Cat and objects of type Dog
An array of Object may contain any type of object (but cannot
contain primitives)
9
Arrays in Java II
Arrays are objects
Arrays are allocated by new, manipulated by reference, and
garbage collected
However, the usual bracket notation a[i] is provided as
syntactic sugar
Arrays are reflective
a.length is the length of array a
a.getClass() is the type of array a
An array of integers has type [I
An array of Strings has type [Ljava.lang.String;
10
Contiguous Memory
Array elements are stored at contiguous memory
locations
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 30 45 50 60 65 70 80
No empty segment in between values (3 & 5 are
empty – not allowed)
Index: 0 1 2 3 4 5 6 7 8 9
Value: 5 10 18 45 60 65 70 80
Arrays in Java III
Here’s one way to visualize an array in Java:
myArray
class tag [I
length 4
0 17
1 23
2 948
3 3
12
Using Arrays
Array_name[index]
For example, in Java
System.out.println(data[4]) will display
0
data[3] = 99 will replace -3 with 99
Some more concepts
data[ -1 ] always illegal
data[ 10 ] illegal (10 > upper bound)
data[ 1.5 ] always illegal
data[ 0 ] always OK
data[ 9 ] OK
Q. What will be the output of?
1. data[5] + 10
2. data[3] = data[3] + 10
Subarrays
A subarray is a consecutive portion of an array
0 1 2 3 4 5 6 7 8 9
array a [I 10 1 1 2 3 5 8 13 21 34 55
subarray a[2...6]
Java provides no language support for subarrays
To use a subarray, you must keep track of (1) the array
itself, (2) the lower bound, and (3) the upper bound
Typically, these will be three parameters to a method that
does something with the subarray
15
Array as an ADT
An array is an Abstract Data Type
The array type has a set of values
The values are all the possible arrays
The array type has a set of operations that can be
applied uniformly to each of these values
The only operation is indexing
Alternatively, this can be viewed as two operations:
inspecting an indexed location
storing into an indexed location
It’s abstract because the implementation is hidden: all
access is via the defined operations
16
Subarray as an ADT
As noted earlier, to use a subarray, you must keep track of (1) the
array itself, (2) the lower bound, and (3) the upper bound
This suggests:
class Subarray<V> {
V[ ] subarray;
int lowerBound;
int upperBound;
// Constructor, some methods...
}
Advantage:
Only one object to pass around
Disadvantages:
The subarray must hold Objects, not primitives
You lose the nice array syntax
17
Array’s Dimensionality
One dimensional (just a linear list)
e.g., 5 10 18 30 45 50 60 65 70 80
Only one subscript is required to access an individual
element
Two dimensional (matrix/table)
e.g., 2 x 4 matrix (2 rows, 4 columns)
Col 0 Col 1 Col 2 Col 3
Row 0 20 25 60 40
Row 1 30 15 70 90
One Dimensional Arrays
To declare an array follow the type with (empty) []s
int[] grade; //or
int grade[]; //both declare an int array
In Java arrays are objects so must be created with the new
keyword
To create an array of ten integers:
int[] grade = new int[10];
Note that the array size has to be specified, although it can be
specified with a variable at run-time
Two-dimensional arrays I
Some languages support two-dimensional (2D) arrays:
columns
a b c d A two-dimensional array may be stored
rows e f g h in one-dimensional computer memory
i j k l in either of two ways:
logical view
row 0 row 1 row 2
row major order: a b c d e f g h i j k l
col 0 col 1 col 2 col 3
column major order: a e i b f j c g k d h l
20
Two-dimensional arrays II
In a 2D array, we generally consider the first index to be the row,
and the second to be the column: a[row, col]
columns
0 1 2 3 4
0 0,0 0,1 0,2 0,3 0,4
1 1,0 1,1 1,2 1,3 1,4
rows
2 2,0 2,1 2,2 2,3 2,4
3 3,0 3,1 3,2 3,3 3,4
In most languages we don’t need to know the implementation--
we work with this abstraction
In Java, C and C++, we do need to know the implementation
21
2D arrays in Java
Java doesn’t have “real” 2D arrays, but array elements can
themselves be arrays:
int x[][] denotes an array x of array components, each of which is
an array of integer components
We can define the above array like this:
x = new int[5][8];
and treat it as a regular 2D array
This is an array of 5 arrays
Each subarray is an array of 8 ints
However, we can do fancier things than this with arrays in
Java
22
Ragged arrays
int ragged[][] = new int[4][]; 0
0 0 1
for (int i = 0; i < 4; i++) { 1 10 11 2
ragged[i] = new int[i + 1]; 2 20 21 22 3
} 3 30 31 32 33
for (int i = 0; i < 4; i++) {
for (int j = 0; j < ragged[i].length; j++) {
ragged[i][j] = 10 * i + j;
}
}
23
Array Operations
Indexing: inspect or update an element using its index.
Performance is very fast O(1)
randomNumber = numbers[5];
numbers[20000] = 100;
Insertion: add an element at certain index
– Start: very slow O(n) because of shift
– End : very fast O(1) because no need to shift
Removal: remove an element at certain index
– Start: very slow O(n) because of shift
– End : very fast O(1) because no need to shift
Search: performance depends on algorithm
1) Linear: slow O(n) 2) binary : O(log n)
Sort: performance depends on algorithm
1) Bubble: slow O(n2) 2) Selection: slow O(n2)
3) Insertion: slow O(n2) 4)Merge : O (n log n)
Inserting an element into an array
Suppose we want to insert the value 8 into this sorted array
(while keeping the array sorted)
1 3 3 7 12 14 17 19 22 30
We can do this by shifting all the elements after the mark right by
one location
Of course, we have to discard the 30 when we do this
1 3 3 7 8 12 14 17 19 22
• Moving all those elements makes this a slow
operation (linear in the size of the array)
25
Deleting an element from an array
Deleting an element is similar--again, we have to move all
the elements after it
1 3 3 7 8 12 14 17 19 22
1 3 3 7 12 14 17 19 22 ?
Deletion is a slow operation; we don’t want to do it very often
Deletion leaves a “vacant” location at the end
How do we mark it vacant?
Every bit pattern represents a valid integer
We must keep a count of how many valid elements are in the array
26
Arrays and ArrayLists
Here are the advantages of arrays:
Very efficient, in terms of both time and space
Convenient syntax
Here is the main disadvantage:
Fixed size
27
Vectors and ArrayLists
Vector methods include the following:
public void insertElementAt(Object elem, int index)
public void removeElementAt(int index)
ArrayList methods include the following:
public void add(int index, Object elem)
public void remove(int index)
These are slow (linear time) methods
28
Conclusions
Arrays are not identical in all languages
Arrays have the following advantages:
Accessing an element by its index is very fast (constant
time)
Arrays have the following disadvantages:
All elements must be of the same type
The array size is fixed and can never be changed
Insertion into arrays and deletion from arrays is very slow
29
The End
30
