Chapter 8 (Arrays) - Java Software Solutions

What exactly is an array?

A programming tool that allows you to store many values in a single variable.

So instead of writing:

int height1 = 65;

int height2 = 70;

…. and so on

You can just write, which is functionally equivalent:
int [ ] height = new int [ 10 ];

How do arrays store numbers?

Arrays store numbers as values in boxes lined up in order. Each box has a # called an index (or subscript).

We say that boxes of arrays are in contiguous order (which just means one after the other).

Why are arrays useful?

They allow you to quickly go through values using for loops.

Do we use indexing for arrays?

yes, arrays begin counting their boxes at 0.

How can you write a declaration for an array of heights of type int?

int[] height = new int[11];
// the number in the square brackets represents the NUMBER OF SLOTS; so not the range of values
// the new keyword represents the actual instantiation of an array object

How can you get or set an Array Value?

// By using the name of the array + its index value
// gets the value at index 8 in the array called height

height[8];

height[8] = 72;

Can arrays be used in expressions?

Yes, here is an example:

average = (height[0] + height[1] + height[2]/3);

What would a statement like this do if you knew that max was the maximum size of the array?

System.out.println(height[MAX/2]);

It would give you exactly half of the array.

How can you use a random generator in place of an index to generate random indices for an array?

Random sofiasrand = new Random();
int[] height = new int[11];
myvalue = height[sofiasrand.NextInt(11)]
// will generate a random number from 0 to 10 that will be used as an index value

How are arrays stored in memory? Why is this important?

They are stored contiguously, which means one element after the other.

It makes it easy for computers to calculate where the next position is using the formula:

address of element = start address + (index * size of each element);

SR 8.3 Based on the array shown in Figure 8.1


 each of the following?
 a. 
height[1]
 b. 
height[2] + height[5]
 c. 
height[2 + 5]
 d. the value stored at index 8
 e. the fourth value
 f. 
height.length

a) 61

b) 70 + 69 = 139

c) 73

d) 79

e) 74

f) 11 (not the index, the actual length of the list)

What do you need to do before you can use an array?

You must first:

• Declare the reference to the array

• Instantiate the array with new, or with an initializer list, which allocates memory for the elements.

Give an example of an instantiation and declaration of an array:

int[] nums = new int[10];
// instantiation + declaration 

TRUE OR FALSE:

Once you create an array, the size cannot change

TRUE

What are some of the key differences between Arrays and ArrayLists?

Arrays are fixed at creation and cannot be changed; On the other hand, ArrayLists are dynamic and can change according to the number of values you add or remove.

Arrays also have no direct way of removing elements from it like ArrayLists have; ArrayLists have methods like .remove() to do so.

ArrayLists are also part of the java.util package, while Arrays are part of the java language themselves.

Also, ArrayLists cannot hold any primitive values directly, they can only hold primitive types that are in Wrappers: Integer, Boolean, Character… and so on. ArrayLists can only hold objects. On the other hand, Arrays can hold BOTH primitive values and objects. 

In Arrays, all elements have to be of the same type, you cannot have different types in the same Array, ArrayLists can technically store a mix of different objects all in the same list.

Are you allowed to use an array after declaring it?

No, you cannot use an array right after declaring it. You must instantiate it first.

What would be the output of the following code:

public static void main(Stringp] args) {
final int LIMIT = 15, MULTIPLE = 10;
int[] list = new int[LIMIT];
for(int index = 0; index < list[LIMIT]; index++)
list[index] = index * MULTIPLE;

list[5] = 999;
for(int value: list)
System.out.println(value);
}
}

public static void main(Stringp] args) {
final int LIMIT = 15, MULTIPLE = 10;

// the maximum length of this list is 15
int[] list = new int[LIMIT];

for(int index = 0; index < list[LIMIT]; index++)
// ex. output:
// list[0] = 0 * 10 = 0
// list[1] = 1 * 10 = 10
// list[2] = 2 * 10 = 20
// list[3]..and so on until index 14
list[index] = index * MULTIPLE;

// the fifth element is changed to 999
list[5] = 999;
// loops through each element in the list, storing its value in the variable value as it goes through
for(int value: list) 
System.out.println(value);
}
}

// OUTPUT:
// 0 10 20 30 40 999 50 60 70 80 90 100 110 120 130 140

The two main types of for loops are?

Regular For Loops (aka Index Based Loops)

And Iterator Enhanced Loops (aka For Each Loops)

Is this an operator in java?

[]

Yes, this is in fact an operator in java, and it has the highest priority/precedence out of all other operators (so it is evaluated first, always).

What is Bounds Checking?

Bounds checking is the process that java automatically carries out whenever you enter an index; It does this to verify that the index you entered is valid, which means:

• It must be greater than 0

• It must be < array.length

What would the following give you:

int[] sofiasarray = new int[25];
sofiasarray[24];
sofiasarray[25];
sofiasarray[];

int[] sofiasarray = new int[25];
sofiasarray[24]; // the correct value at index 24
sofiasarray[25]; // IndexOutOfBoundsException
sofiasarray[]; // IndexOutOfBoundsException

What do we use to figure out the length of a list? Give an example of how to do it:

// we use .length, a built in constant

int[] sofia = new int[11];
sofia.length;
// unlike the method .length() which only works on strings, this is a built in constant for arrays specifically.

What would be the output of the following program:

import java.util.Scanner;
public static void main(String[] args) {
Scanner sofiasscanner = new Scanner(System.in);

double[] numbers = new double[3];

System.out.println("The size of the array is:" + numbers.length);

for(int index=0; index < numbers.length; index++) {

System.out.println("Enter number:" + (index+1));

numbers[index] = sofiasscanner.nextDouble();
}

for(int index = numbers.length-1; index >=0; index--) {

System.out.println(numbers[index]);
}
}
}

import java.util.Scanner;
public static void main(String[] args) {
Scanner sofiasscanner = new Scanner(System.in);

// creates an array of numbers with a length of 10
double[] numbers = new double[3];

// prints out 10
System.out.println("The size of the array is:" + numbers.length);

for(int index=0; index < numbers.length; index++) {

System.out.println("Enter number:" + (index+1));


numbers[index] = sofiasscanner.nextDouble();
}

System.out.println("The nums in reverse:");

for(int index = numbers.length-1; index >=0; index--) {

System.out.println(numbers[index]);

// SAMPLE OUTPUT:
// Enter Number 1: 
// ex. 3
// numbers[0] = 3
// Enter Number 2:
// ex. 4
// numbers[1] = 4
// Enter Number 3:
// ex. 5 
// numbers[2] = 5 (the for loop assigns the values in the brackets)
// index = numbers.length-1
// index = 3-1
// index = 2
// System.out.println(numbers[2])
// prints 5
// System.out.println(numbers[1])
// prints 4
// System.out.println(numbers[0])
// prints 3
}
}
}

What are the two different ways of declaring an array?

//The regular way:
int[] sofiasnums;
OR
// the alternate array syntax:
int a[],b;

What are the two different ways of adding values to an array?

double[] nums = new nums[10];
nums[0] = 5;
nums[1] = 7;
nums[2] = 13;

// OR ALTERNATIVELY USING INITIALIZER LISTS:
double[] nums = {5, 7, 13}

What do initializer lists allow you to do?

They allow you to assign values directly after declaring an array using { }.

This means that you can use them to instantiate an array object instead of using the new operator. However, initializer lists can only be used at the moment of declaration.

Are arrays objects?

Yes, an array itself is an object.

Can you pass arrays as parameters? What happens when you do this? Explain using the following example:

public static void changeFirst(int[] arr) {
    arr[0] = 999;
}
public static void main(String[] args) {
int[] numbers = {1,2,3};
changeFirst(numbers);
System.out.println(numbers[0]);
}

public static void changeFirst(int[] arr) {
    arr[0] = 999;
}
public static void main(String[] args) {
int[] numbers = {1,2,3};
changeFirst(numbers);
System.out.println(numbers[0]);
}

// here, when we pass numbers into changeFirst, arr becomes an alias of numbers
// and therefore changing arr also permanently changes our numbers array
// therefore the output will be 999
// remember the example from earlier with passing objects into methods; whenever you do this, the method permanently changes the value of the original object and makes them aliases of one another, so that they point to the same object reference

Do arrays hold elements directly?

No, they do not.

Arrays are objects, which means they don’t actually hold raw primitive values, even if it looks like it. The only thing they can store are references to where that value lives in the array’s memory (object references).

How can we reassign the values of this pre-existing array?

int[] array = {1,2,3,4,5};

int[] array = {1,2,3,4,5};
array = new int[] {7,9,11,12}
// at first, array pointed to the object {1,2,3,4,5} in memory
// then we made it point to {7,9,11,12}
// so the original {1,2,3,4,5} still exist in memory, but there's no longer a variable pointing to it, which means its eligible for garbage collection

// OR ALTERNATIVELY:

int[] array = {1,2,3,4,5};
int[] sofiasarray = {7,9,11,12};
array = sofiasarray;

// here, we make array point to the same place in memory as sofiasarray; so now array = {7,9,11,12}, and the {1,2,3,4,5} is now ready for garbage collection

Describe what happens here:

public static void reassign(int[] arr) {
arr = new int[] {10,20,30};
}

public static void main(String[] args) {
int[] numbers = {1,2,3,4,5};
reassign(numbers);
System.out.println(numbers[0]);
}

public static void reassign(int[] arr) { //when we first passed in numbers as a parameter, we made arr and numbers point to the same location in memory, which was {1,2,3,4,5} 

// but then we changed the value of arr to {10,20,30}, making it point to a brand new array object and removing its alias. So this only changed the value of arr, and not numbers.
arr = new int[] {10,20,30};

}

public static void main(String[] args) {
int[] numbers = {1,2,3,4,5};
reassign(numbers);
// we pass in numbers into reassign

System.out.println(numbers[0]);
}
// OUTPUT IS STILL 1

In general, if we reassign an array in a method, it only changes….

the local reference, and the caller’s reference remains untouched.

If we were to do something like this to two arrays that are aliases of one another, what effect would this have:

arr[0] = 999

It would directly alter the contents of the actual/original array that we passed in as a parameter into that method.

Explain the logic behind reassigning arrays using a sticky note analogy:

Your variable, for example: int[] sofiasarray = new int[10]; is a sticky note that points to the row of boxes in memory

If you pass the array over to someone else(like through a method), you’re giving someone a copy of that sticky note

If they change what’s inside the boxes, than you’ll see it too.

But if they decide to throw away the sticky note and get a brand new one instead, it won’t impact you in the slightest, and your sticky note will still point to the original boxes (reassignment, but not always true)

SR 8.5 Describe the process of creating an array. When is memory allocated for the array?

Arrays are created with the new keyword or through initializer lists. Memory is allocated as soon as you use the new keyword or as soon as you use the initializer list.

So again, it’s only when you INSTANTIATE an array that memory space is actually allocated for it:

// memory space is only allocated when you initialize a list
int[] sofiasnums = new int[5];

int[] sofiasnums = {1,2,3,4,5};

// not when you just declare it:
int[] sofiasnums;

SR 8.6 Write an array declaration to represent the ages of all 100 children attending a summer camp

int[] ages = new int[100];

SR 8.7 Write an array declaration to represent the counts of how many times each face appeared when a standard six sided die is rolled

int[] counts = new int[6];

SR 8.8 Explain the concept of array bounds checking. What happens when a Java array is indexed with an invalid value?

Array bounds checking is an automatic process carried out by java whenever you enter an index for an array. Java always verifies to make sure that the value you entered is greater than 0 but is one less than the length of the array. Otherwise, it will through an ArrayIndexOutOfBoundsException.

SR 8.10 Write code that increments (by one) each element of an array of integers named values

int[] values = new int[10];
for(int i=0; i<values.length; i++) {
    values[i]++; 
}

//note something like the below solution is wrong:

for(int value: values) { 
    values[value]++;
}

// the reason why is because value represents the actual numeric value in that index of the array; it does not represent the index number. So if your list is 1,2,3,4,5, then value will store each number in the list: 1, 2, 3, and then 4, and 5, it doesn't store the indices 0 1 2 3 4... and so on.
// so what you actually end up incrementing is something totally different

What would be the output of the following code?

int[] values = new int[3];


for(int value: values) {
    values[value]++;
}

Well, since we haven’t initialized any of the values in our array, by default, the list is empty,

int[] values = new int[3];
// so we have a list of {0,0,0}

for(int value: values) {
    values[value]++;
// when we use a for each loop, value IS THE ELEMENT ITSELF, not the index

// so here in our loop, we just have: 
// FIRST ITERATION:
// values[0]++
// which means increment the value at index 0 to be 1
// so now values[0] = 1

// SECOND ITERATION:
// values[0]++
// which means increment the value at index 0
// since values[0] = 1
// we increment 1, which gives us 2

// THIRD ITERATION:
// values[0]++;
// well, now values[0] = 2
// so 2++ = 3
// {3, 0, 0} is our final array
}

// so definitely do not use this 

SR 8.10 Write code that increments (by one) each element of an array of integers named values.

public static void main(String[] args) {
    int[] values = {1,2,3,4,5};
    for(int i=0; i < values.length; i++) {
    values[i]++;
   }
}
// in a regular for loop, i represents the index

// When this code runs:
// ITERATION ONE:
// values[0] = 1+1 = 2
// values[1] = 2 + 1 = 3
// and so on.

Can arrays hold user-defined objects? Give an example of how you could have an array of grades that stored both the percentage and the letter grade. Use an initializer list.

Grade[] sofiasgrades = {
    new Grade("A", 95),
    new Grade("A-", 90),
    new Grade("B+", 87),
    new Grade("B", 85),
}

Create a constructor for a custom class called DVDCollection. Create a class called DVD collection that declares but does not instantiate an array of DVDs called “collection”. The constructor should instantiate this array, and give it space for 100 items.

public class DVDCollection {
    DVD[] collection;

public DVDCOLLECTION() {
    collection = new DVD[100];
}
}

Initialize an array of DVD called temp. Make the length of this list double the size of the collections list.

DVD[] temp = new DVD[collection.length * 2]

Loop through your array of DVDs called temp, and assign each of the values in the temp array to each of the values in the collection array.

for(int i=0; i< collection.length; i++) {
    temp[i] = collection[i];
}

Instantiate an array of type Grade that can hold 6 values. Add grade objects to this array containing char letter grades and percentage ints. Do this without initializer lists.

Grade[] grades = new Grade[6];
grades[0] = new Grade('A', 86);
grades[1] = new Grade('B', 75);
grades[2] = new Grade('C', 60);

Suppose team is an array of strings meant to hold the names of 3 players on the volleyball team: Claire, Sofia, Emily. Write an array declaration for the team with and without using initializer lists.

String[] team = new String[3];
team[0] = "Claire";
team[1] = "Sofia";
team[2] = "Emily";

String[] team = {"Claire", "Sofia", "Emily"};

Assume book is a class whose objects represent books. Assume a constructor of the book class accepts two params: the name of the book and the number of pages.

Write a declaration for a variable named library that is an array of 10 books.

Then write a new statement that sets the first book in the library to “Starship" which is 208 pages long.

public class Book {
    public Book(String name, int pages) {
}

Book[] library = new Book[10];
library[0] = new Book("Starship", 208);

Describe the main method, how is it an array?

public static void main(String[] args)

It’s literally an array of strings called “args”

How would you get the value at index 0 of the main method, and how would you print it out to the console?

public static void main(String[] args)

System.out.println(args[0]);

Where are command line arguments stored? What are they passed into?

They are stored in an array of String objects called args. This array is what gets passed to the main method.

What happens if you don’t enter enough arguments into your command line? Like you enter fewer arguments than what a method expected;

Then you would get an IndexOutOfBoundsException.

Show how you would pass in the argument “sofia” using the command line for a program called nameTag

> java nameTag sofia

What happens if you pass in too many arguments through the command line into a method?

Then the program only uses the first two, or however many it required; The rest of the extra arguments get stored in the array but are ignored, so you don’t get an IndexOutOfBoundsException.

What happens to arguments that you pass in through the command line? What is a command line argument?

Command line arguments are just arguments that get passed to the main method (but through cmd).

Are you allowed to type in numeric values directly into your command line?

No, you would need to convert a string into an int using parseInt

Write a main method that outputs the sum of the first 2 command line arguments.

public static void main(String[] args) {
    int argument0 = Integer.parseInt(args[0]);
    int argument1 = Integer.parseInt(args[1]);
    System.out.println(argument0 + argument1);

Write a main method that outputs the sum of the length of the first 2 command line arguments.

public static void main(String[] args) {
    int argument0 = args[0].length;
    int argument1 = args[1].length;
    System.out.println(argument0 + argument1);
}

What does varargs mean?

Variable arguments; It means allowing for an infinite amount of arguments to be passed into a method.

It is expressed as three dots only: …

Write a method called sofiasaverage which returns a double and has variable arguments:

public double sofiasaverage (int...sofiaslist) {
}

Using the sofiasaverage method we wrote before, calculate the average of all the numbers passed into the method. It should return the result.

public double sofiasaverage (int...mylist) {
}

public double sofiasaverage(int...mylist) {
    double sum = 0.0;
    double result;
    if(mylist.length > 0) {
        for(int num : mylist) {
            sum+=num;
        }
      result = sum/mylist.length;
    }
    return result;
} 

How would you pass in some numbers into this method?
Java

public double sofiasaverage(int...mylist) {
    double sum = 0;
    double result;
    if(mylist.length > 0) {
        for(int num : mylist) {
            sum+=num;
        }
      result = sum/mylist.length;
    }
    return result;
} 

sofiasaverage(3,4,12);

What happens if you try to pass in 0 arguments into varargs?

Nothing happens! You’re actually allowed to pass in 0 arguments. This is why we have to check that the user did not enter 0 arguments when calculating list averages and such.

Can you choose to have both fixed parameters and varargs in the same method?

Yes, you are allowed to do this as long as varargs comes last:

public int sofia(int age, String name, int...grades){
}

Can you pass in objects as varargs?

Yes

Write varargs for a method called printGrades that returns void, but contains two arguments; One called java that is of type Grade and fixed, and the other a varargs of Grades caled courses.

Loop through each of the variable args and print out each one:

public void printGrades(Grade java, Grade...grades) {
    for(Grade g : grades) {
        System.out.println(g);
    }
}

How are variable arguments actually stored in java under the hood?

They are stored as arrays! so here:

public void sofia(Grade...grades) {
} // grades would just be an array of Grade called grades

SR 8.21 Write a method called distance that accepts a multiple number of integer parameters (each of which represents the distance of one leg of a journey) and returns the total distance of the trip.

public double distance(int...legs) {
if(legs.length > 0) {
double sum = 0.0;
for(int leg : legs) {
sum+= leg;
}
return sum;
}

SR 8.22 Write a method called travelTime that accepts an integer parameter indicating average speed followed by a multiple number of integer parameters (each of which represents the distance of one leg of a journey) and returns the total time of the trip

public double travelTime(double avgspeed, int...legs) {
double sum = 0.0;
double time;
if(legs.length > 0) {
for(int leg : legs) {
sum+=leg;
}
time = (double) sum / avgspeed; // d = v/t or t = distance / speed
return time;
}

How would you declare a 2D Array?

int[ ][ ] sofias2darray;

How would you initialize a 2D Array with 3 rows and 4 columns?

int[3][4] sofiasdimensionalarray;

Initialize a 2D Array with values using an initializer list; Do all 2D arrays need to have a fixed size?

int[][] matrix = {
  {1,2,3},
  {1,2,3},
  {1,2,3}
};

// they can have variable sizes:

int[][] mymatrix = {
  {1,2},
  {3,4,5,6}
}

Print out the number 3 in this matrix:
int[][] sofiasmatrix = { {1,2,3}, {4,5,6}, {6,8,9} };

System.out.println(sofiasmatrix[0][2]);
// remember: indices count

Show how you would loop through all of the rows and columns of the following array, printing out each of its respective rows + colums to print out the whole matrix:

int[][] sofiasmatrix = {
{1,2,3},
{4,5,6},
{7,8,9}
};

for(int i = 0; i < sofiasmatrix.length; i++) { //rows
for(int s = 0; s < sofiasmatrix[i].length; s++) { //columns
System.out.println(sofiasmatrix[i][s] + "");
}
System.out.println();
}

Show how you would implement a linear search of a list to find a target element specified by the user.

public static int linearSearch(int[] sofiasarray, int target) {
    for(int i=0; i < sofiasarray.length(); i++) {
    if(sofiasarray[i] == target) {
        return i;
    }
}
return -1; // will return -1 if no match was found after the loop ended.
}

So by hand:

Let’s say our list was:

{5,8,1,3,7,9}, target = 7

Compare 5 → Not match

Compare 8 → Not match

Compare 1 → Not match

Compare 3 → Not match

Compare 7 → match at index 4

How would you perform a binary search?

public static int binarysearch(int[] sofiasarray, int target) {
    int low = 0;
    int high = sofiasarray.length -1;

while(low <= high) {
    int mid = (low + high) / 2;

    if(sofiasarray[mid] == target) {
       return mid;
    } else if(sofiasarray[mid] < target) {
       low = mid + 1; // searches the right half
    } else {
       high = mid - 1; // searches the left half
    }
  }
  return -1;
}

Which Big O notation represents a linear search? Which represents a binary search? Which is more efficient/faster?

What type of search is the linear search and binary search?

O(n) represents a linear search. The linear search is linear (duh)

O(log n) represents a binary search. The binary search is logarithmic.

What is the notation for merge sort/quick sort.

O(n log n), the growth type is efficient sorting

What is the notation for bubble sort?

O(n²) quadratic

Describe how the Selection Sort works. How would you complete a diagram to show how it works for the following list:

3,9,6,1,2

• Start at index 0.

• Find the smallest element in the whole array.

• Swap it with the element at index 0.

• Move to index 1, find the smallest in the remaining array, swap it into index 1.

• Continue until the array is sorted.

Describe how the Insertion Sort Works. Do it for the following list:
3,9,6,1,2

• Start at index 1 (since a single element at index 0 is “already sorted”).

• Take the current element and compare it backwards with the sorted portion.

• Shift larger elements one position to the right.

• Insert the current element into the correct spot.

• Repeat until the array is sorted.