‫بسم هللا الرحمن الرحيم‬

King Abdulaziz University

Faculty of Computing and information Technology
Computer Science Department

CPCS-204 Data Structures I

3- Arrays

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 1
 Motivation
• What is the purpose of an array?
• To store 5 numbers in a program
• Define 5 variables:
int num1, num2, num3, num4, num5;

• But what if you want to store 1000 numbers?

int num1, num2,..., num998, num999, num1000; !!!

• What is the solution?

• DS!
• Specifically, an array!

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 2
 Array
• Is a DS; One of the most common DSs
• Collection of homogeneous data elements
• Static: cannot grow or shrink during program execution – the
size is fixed
• Homogeneity: all elements must have same data type
• Contiguous: elements are stored in contiguous memory locations
• Direct access to an element
• Index reference is used to access it directly
CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 3
 Basic Concepts
• Name
• Index/subscript
• Cells are numbered sequentially starting at 0
• If n cells in an array, index: 0 through n-1
• Array length: number of elements (n)
• Array size = n x Size of an element
• Direct access to an element

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 4
 Using Arrays
data
• In Java
9
• Array_name[index]
4
• Examples: 30
• System.out.println(data[1]); 124
• Display 4
23
• data[4] = 56;
-5
• Replace 23 with 56
42
• Questions: what will be the output of: 5
• data[5] + 10; 0
• data[3] = data[3] + 10; 20

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 5
 Using Arrays: More Concepts
data
• Examples:
9
• data[-1]
4
• data[10]
30
• data[1.5]
124
• data[0]
23
• data[9]
-5
42
5
0
20

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 6
 Using Arrays: More Concepts
data
• Examples:
9
• data[-1] always illegal
4
• data[10]
30
• data[1.5]
124
• data[0]
23
• data[9]
-5
42
5
0
20

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 7
 Using Arrays: More Concepts
data
• Examples:
9
• data[-1] always illegal
4
• data[10] illegal (10 > upper bound)
30
• data[1.5]
124
• data[0]
23
• data[9]
-5
42
5
0
20

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 8
 Using Arrays: More Concepts
data
• Examples:
9
• data[-1] always illegal
4
• data[10] illegal (10 > upper bound)
30
• data[1.5] always illegal
124
• data[0]
23
• data[9]
-5
42
5
0
20

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 9
 Using Arrays: More Concepts
data
• Examples:
9
• data[-1] always illegal
4
• data[10] illegal (10 > upper bound)
30
• data[1.5] always illegal
124
• data[0] always ok
23
• data[9]
-5
42
5
0
20

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 10
 Using Arrays: More Concepts
data
• Examples:
9
• data[-1] always illegal
4
• data[10] illegal (10 > upper bound)
30
• data[1.5] always illegal
124
• data[0] always ok
23
• data[9] ok
-5
42
5
0
20

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 11
 Array Dimensionality
• One dimensional (just a linear list)
• Example:

5 22 60 43 34 56 97 12 32 40

• Only one subscript is required to access an individual element

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 12
 Array Dimensionality
• Two dimensional (matrix or table)
• Example: 3×5 matrix (3 rows, 5 columns)

15 22 60 1 34

80 42 0 31 4

53 22 6 7 64

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 13
 Array Dimensionality
• Two indices/subscripts are required to reference a given cell
• row, column

• First element: G[0][0]

• What is
• G[1][3] ?
• G[4][2] ? 15 22 60 1 34

80 42 0 31 4

53 22 6 7 64

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 14
 Array Declaration
• Declare an array as follows:
int[] grades;
• This simply makes an array variable (grades)
• But it does NOT specify where that variable refers to

• We can also declare the following:

int[] grades = new int[10];
• Array variable grades refers to an array of ten integers
• By default, numeric elements are initialized to zero

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 15
 Memory and Initialization
• When array is created, memory is reserved for its contents
• Can also specify values for array instead of using new operator
• Example:
int[] grade = {95, 93, 88}; //array of 3 integers

• To find the length of an array, use the length method

int numGrades = grade.length();

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 16
 Arrays’ Properties
• Are objects
• Created dynamically, at run time
• Array type variable holds a reference to the array object
• Array’s length is set when created, and it cannot be changed
• Can be duplicated with
• Object.clone() method

• An ArrayIndexOutOfBoundsException is thrown if index

exceeds array length
CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 17
 Array Processing in JAVA
• Class java.util.Arrays provides many built-in methods for
sorting and searching
• Method Arrays.sort(array_name)
• sort an array
• Method Arrays.binarySearch(array_name, target)
• search through a sorted array
• Method Arrays.equals(array1, array2)
• check if two arrays are equal (same values are at each index position)

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 18
Array Processing in JAVA

44 77 55 22 99 88 33 66
22 33 44 55 66 77 88 99
Arrays.binarySearch(a, 44): 2
a(2); 44
Arrays.binarySearch(a, 45): -1
0 0 0 0 0 0 0 0
55 55 55 55 55 55 55 55
Arrays.equals(a,b): false

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 19
 Array Operations: Accessing
• Indexing an element using its index
• Performance: very fast
• Can access an index immediately without searching
• studArr[200] = 25;
immediately access array spot 200 of studArr

public static void access(double[] a, int index) {

a[index] = a[index] + a[index] * 0.20;
System.out.println (“Updated value “ + a[index]);
}

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 20
 Array Operations: Traversing
• Display all contents of an array
• All elements will be displayed
• Every element will be displayed exactly once

public static void display(int[] a) {

for (int i=0; i<a.length; i++)
System.out.println (a[i]);
}

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 21
 Array Operations: Insertion
• Add an element at a certain index
• At the beginning
• Very slow operation!
• Why?
– Shift ALL other elements over by one position
• At the end
• FAST!
• Why?
– No shift

5 22 60 43 34 56

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 22
 Array Operations: Removal
• Remove an element at a certain index
• At beginning of array
• Very slow!
• Why?
– Shift ALL elements one position backwards
• At the end of an array
• Very fast
• Why?
– No shift

5 22 60 43 34 56

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 23
 Array Operations: Merging
• Combining data of two or more arrays into one

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 24
 Array Operations: Searching
• Through the array
• Depends on the algorithm
• Some algorithms are faster than others
• Linear search
• Binary search

CPCS204, Data Structures I, Updated by Pr. Abdullah Basuhail, CS, FCIT, KAU, 1442H-2021G 25