Table of Contents:

Arrays vs. ArrayLists

One of the biggest limitations of arrays is that they have a static size - i.e. you determine the array size when initializing the array and this cannot be changed later on, for instance, to append or remove array elements as needed while the program is running.

The ArrayList objects have the following advantages over regular arrays:

• they have a dynamic size - it can be changed after the array has been initialized - that is during the run-time of the program

• there are ready-made getter/setter methods for inserting and deleting ArrayList elements as well as other methods, such as sorting and reversing the arrayList elements.

Enabling arrayLists in your program

In order to use an arrayList in your program, you need to import the java.util library (a collection of related classes) which includes the needed definitions for this data type.

This is how you do it:

include java.util.*;

 The asterisk after the dot means that you want to bring in all the different classes that the java.util library contains. You could also just import the class needed for the functionality of your arrayList:

import java.util.ArrayList;

You will not be tested on importing the needed libraries on the AP exam, but you need to do it in order to be able to run your programs.

For the exam, you will be given the AP CS A Java Quick Reference, which includes the methods below - this means you don't have to memorize the syntax of these:

• int size() - returns the size of the ArrayList - this is the ArrayList equivalent of the .length property used with arrays. 

  • Example:     studentRoster.size();

• boolean add(E obj) - adds an object to the end of the ArrayList and returns true when successful. Integer values can be inserted directly - they get converted to an Integer object automatically (this is known as autoboxing). 

  • Examples: studentRoster.add("Tomas");    testScores.add(56);

• void add(int index, E obj) - inserts an object at the given index number position of an ArrayList and shifts the existing values at and beyond the index number to the right by one place. 

  • Example: studentRoster.add(0,"Aldyiar"); This will add "Aldyiar" at the beginning of the ArrayList and thus increases the index numbers for the other values by one.

• E remove(int index) - removes the value at the given index and moves the other values as needed, so that there is no gap in the ArrayList left. Returns the value deleted.

  • Example: studentRoster.remove(2); This will remove "Anton" from the ArrayList and shift "Anthony" and "Tomas" by one to the left.

• E get(int index) - returns the item at the given index number.

  • Example: studentRoster.get(2) will return "Anthony".

• E set(int index, E obj) - replaces the value at the index with obj. It returns the original value at the index. 

  • Example: studentRoster.set(3, "Tomáš") replaces the value "Tomas" with "Tomáš" and returns the original value, "Tomas".

Arrays vs ArrayLists - checking for size, reading, and modifying values:

You can traverse an array list by using the following structures (R-read, W-write, A-append): 

• an indexed for-loop (R/W/A)

• a while loop. (R/W/A)

• an enhanced for-loop (R only, otherwise the ConcurrentModificationException can be thrown.)

Here is an example of a program where all three types of loops are used:

import java.util.*;

public class TestVariousLoops

{

    public static void main()

    {

        ArrayList<Double> donations = new ArrayList<Double>();

        donations.add(50.50);

        donations.add(75.00);

        donations.add(83.00);

        donations.add(92.30);

        double total = 0;

        double sum = 0;

        // calculating the total donation - using the indexed for-loop for access only:

        for (int i=0; i < donations.size(); i++)

        {

            total = total + donations.get(i);

        }

        System.out.println("The sum of all the donations is "+total+" euros.");      

        // calculating the average donation - using the enhanced for-loop for access only:

        for (Double donation : donations)

            sum = sum + donation;

        System.out.println("The average donation was "+(sum/donations.size())+" euros.");

        // printing the highest donation - using the while loop for access only:    

        Double highest=donations.get(0);

        int index=0;

        while (index<donations.size())

            { 

                if (donations.get(index)>highest);

                    highest=donations.get(index);

                index++;

            }

        System.out.println("The highest donation was "+highest+" euros.");       

   }

}

When removing ArrayList elements, you need to be careful not to skip an element - as when you remove an element, the index numbers shift left. Consider this example:

import java.util.*;

public class TestingInventory

{

    public static void main()

    {

        ArrayList<String> inventory = new ArrayList();

        inventory.add("knife");

        inventory.add("axe");

        inventory.add("belt");

        inventory.add("belt");

        inventory.add("axe");

        // removing the belts:

            for (int i=0; i < inventory.size(); i++)

        {

            if (inventory.get(i).equals("belt"))

                inventory.remove(i);

        }

        System.out.println(inventory);      

    }

}

You would expect it to print knife, axe, axe, but instead, it prints knife, axe, belt, axe. The reason why it didn't delete the second "belt" (index number 3) is because upon removing an element from an ArrayList, the index numbers of all the elements to the right of it shift left by one. This results in the loop skipping over element number 3 as upon the deletion of element number 2, the one next to it - number 3 - becomes number two. See the table below:

In order to overcome this problem, we need to modify the for-loop in the following way:

 for (int i=0; i < inventory.size(); i++)

        {

            if (inventory.get(i).equals("belt"))

                {

                inventory.remove(i);

                i--;

                }

Adding the i--; statement will make sure the index readjusts to the now one-value shorter ArrayList and thus doesn't skip the value that comes after the deleted one.

Resources:

• Runestone Academy: CS Awesome: Unit 7.3 - make sure you do the FRQ at the end

• Practice it!: Exercises 10.2-10.17

You need to be familiar with the following algorithms in terms of using ArrayLists:

• Inserting items

• Deleting items

• Finding the minimum or maximum value

• Calculating a sum, average, or mode of the values in the array

• Searching for a particular value in the array

• Determining whether at least one item has a particular property

• Determining whether all elements have a particular property

• Accessing all consecutive (neighboring) pairs of items

• Determining the presence or absence of duplicate items

• Calculating the number of elements meeting specific criteria

• Shifting or rotating items left or right

• Reversing the order of the elements

There are multiple algorithms (methods) for sorting an unsorted array/ArrayList of numerical or textual data. The two sorting algorithms you should know for the AP exam are selection sort and insertion sort. Merge sort will not be tested this year as it involves recursion.

Unsorted arrays

Here's an example for an unsorted ArrayList of numerical data and an unsorted array of strings. 

 These data structures are unsorted because they are not arranged from smallest to largest. This brings about several disadvantages when trying to process such data structures; for instance, it is impossible to use the binary search algorithm or create a frequency table in a resources-efficient way. Sorting textual data alphabetically and numerical data from smallest to greatest (or the other way around) is a very common task that computers perform. Below, you can see the two data structures above after some sorting algorithm has been applied:

 Selection sort

In short, selection sort starts from the beginning of the array and compares element 0 to all the other elements and finds the minimum. It then swaps the minimum value with value that was at position 0, so that the minimum value appears at the beginning of the array (the swapped values appear in bold): 

[3,86,-20,14,40] --> [-20,86,3,14,40]

Then it moves to position 1; it finds the minimum from position 1 onward. It then swaps the new minimum with the value at position 1: 

[-20,86,3,14,40] --> [-20,3,86,14,40]

Afterwards, it moves to position 2; it finds the minimum from position 2 onward. It then swaps the new minimum with the value at position 2: 

[-20,3,86,14,40] --> [-20,3,14,86,40]

It then proceeds to position 3 and finds the minimum from position 3 onward. It then swaps the new minimum with the value at position 3:

[-20,3,14,86,40] --> [-20,3,14,40,86]

It does not need to check the last item as it would be checking it with itself; the array is now sorted numerically in ascending order.

The code for selection sort, as published in the AP CS A course description, is as follows: 

Insertion sort

It checks the current value with the values to its left of it and if need be swaps the values (done with a nested while-loop). This ways it progresses throughout the array (using the outer for-loop) all the way to its end (unlike selection sort which ends at length-1).

You start from position 1 of the array (37) and compare it with position 0 (55); swap the values if necessary (all the swaps are in bold; the crossed-out values are not being examined):

[55,37,93,79,28] --> [37,55,93,79,28]                                  // the first for   loop iteration

Then it proceeds to position 2 and checks its value with that in positions 1 and 0; if need be, swapping of values occurs:

[37,55,93,79,22] --> [37,55,93,79,22]                                   // the second for loop iteration

In this case, no swapping of values was necessary.

Then it proceeds to position 4 and checks its value with that in position 3, 2 and 1:

[37,55,93,79,22] --> [37,55,79,93,22]                                    // the third for loop iteration

Here it only needed to swap 79 with 93, no other swaps further to the left were necessary.

Finally, in the fourth for-loop iteration it moves on to the last position - 5 and checks its value with those in the positions to its left; whenever it finds a larger value, it makes a swap:

[37,55,79,93,22] --> [37,55,79,22,93] --> [37,55,22,79,93] --> [37,22,55,79,93] --> [22,37,55,79,93] 

Here it had to do four swaps before 22 got to the correct position in the array.

The array is now sorted numerically in ascending order.

The code for selection sort, as published in the AP CS A course description, is as follows: 

When it comes to ethical issues around data collection, you need to be able to "explain the risks to privacy from collecting and storing personal data on computer systems." 

• Computer programs may have unintended side effects - unintended consequences.

• You need to understand that whenever using the computer, your personal privacy is threatened. It is your job as a programmer to safeguard personal privacy.

• There can be both positive and effects on personal security of using the computer and developing software applications.

Terminology:

• Internet content provider (ICP)

• Internet service provider (ISP)

• legal vs. ethical behavior

• General Data Protection Regulation (GDPR)

• provider, consumer, third-party

Resources:

• The ten commandments of computer ethics

• A proposed methodology for the teaching of Information Technology ethics in schools (PDF)

• Computer and Information Ethics - an entry from Standford Encyclopaedia of Philosophy

• The Murky Ethics of Data Gathering in a Post-Cambridge Analytica World (article)

Videos: