Worked Example: Writing ArrayLists

Section 14.3 Worked Example: Writing ArrayLists - Shifting Values

Subgoals for Writing ArrayLists.

Importing the ArrayList class
🔗
1. Before using ArrayList, import it from the java.util package:
  🔗
  
  import java.util.ArrayList;
  🔗
  
  🔗
🔗
🔗
Declaring an ArrayList variable
🔗
1. Determine the type of objects to be stored (use wrapper classes for primitives, e.g., Integer instead of int)
  🔗
  
  🔗
2. Determine the name of the ArrayList variable
  🔗
  
  🔗
3. Use syntax: ArrayList<DataType> name;
  🔗
  
  🔗
🔗
🔗
Instantiating an ArrayList object
🔗
1. Use the new keyword with the constructor to create a new ArrayList object (When ArrayLists are instantiated, they are empty and have a size of 0.)
  🔗
  
  🔗
🔗
🔗
Adding elements to an ArrayList
🔗
1. To add to the end of an ArrayList, use: listName.add(valueToBeAdded)
  🔗
  
  🔗
2. To add an element at a specific location in an ArrayList, use: listName.add(index, valueToBeAdded) where index is within the bounds 0 to listName.size()
  🔗
  
  🔗
🔗
🔗
Accessing an element in an ArrayList
🔗
1. Determine the index of the element to be accessed
  🔗
  
  🔗
2. Use: listName.get(index) to retrieve the element
  🔗
  
  🔗
3. Ensure the index is within bounds: 0 to listName.size() - 1, otherwise an IndexOutOfBoundsException occurs
  🔗
  
  🔗
🔗
🔗
Changing a value in an ArrayList
🔗
1. Determine the index of the element to be changed
  🔗
  
  🔗
2. Determine the new value or expression to assign
  🔗
  
  🔗
3. Use: listName.set(index, newValue) to update the value
  🔗
  
  🔗
4. Ensure the index is within bounds: 0 to listName.size() - 1, otherwise an IndexOutOfBoundsException occurs
  🔗
  
  🔗
🔗
🔗
Traversing an ArrayList
🔗
1. Decide whether accessing all elements, updating, or accessing a subset
  🔗
  
  🔗
2. If only accessing elements, use an enhanced for (for-each) loop:
  🔗
  1. for (DataType item : listName) - iterates from first to last, storing a copy of each element in item
    🔗
    
    🔗
  🔗
  🔗
3. If updating or using indices, use a traditional for loop:
  🔗
  1. Initialize loop control variable to 0 (or listName.size() - 1 for reverse)
    🔗
    
    🔗
  2. Set condition: i < listName.size() (or i >= 0 for reverse)
    🔗
    
    🔗
  3. Increment or decrement loop control variable appropriately
    🔗
    
    🔗
  🔗
  🔗
4. Use Subgoals 5 or 6 to access or change values as appropriate
  🔗
  
  🔗
🔗
🔗
Whole list actions
🔗
1. Passing an ArrayList as an argument
  🔗
  1. Check if the method expects an ArrayList argument (check documentation or method signature)
    🔗
    
    🔗
  2. When calling a method, pass a reference to an ArrayList (usually variable name) as an argument in the method call.
    🔗
    
    🔗
  3. Note: changes to elements in the ArrayList that are done inside the method will persist
    🔗
    
    🔗
  🔗
  🔗
🔗
🔗

Subsection 14.3.1

Problem: Write the Java code that will store integer values in decreasing order. Values may be added at any time.

Subsection 14.3.2 SG1: Importing the ArrayList class and SG2: Declaring an ArrayList variable and SG3: Instantiating an ArrayList object

Because we don’t know how many values will be stored, we need to use an ArrayList of integers. We will name the variable decreasing.

🔗

import java.util.ArrayList;
ArrayList<Integer> decreasing = new ArrayList<Integer>();

🔗

Subsection 14.3.3 SG4: Adding elements to an ArrayList

Suppose we know in advance the first four values to be added. We can write the code to place them exactly where they belong in the ArrayList:

🔗

decreasing.add(50);			// [ 50 ]
decreasing.add(1, 25);		// [ 50, 25 ]
decreasing.add(0, 100);		// [ 100, 50, 25 ]
decreasing.add(2, 32);		// [ 100, 50, 32, 25 ]

At this point, run this code in the Active Code block at the bottom of the page to see the shifting and inserting happening. You should see that the value 50 is added to the list. Then the value 25 is inserted at position 1 in the list (the end of the list). The third line inserts the value 100 at the beginning (index 0) of the list. And the final line inserts the value 32 at index 2 in the list (between 50 and 25).

🔗

Recall that in Section 12.3, we had to do a lot of work to shift values of an array. The ArrayList has this shifting functionality built in, so when we insert at the beginning of a non-empty ArrayList, all the elements shift over and when we insert in the middle, all the elements after the inserted element shift over. We do not have to write the code to shift the elements inside the array list.

🔗

Subsection 14.3.4 Expanding the Code

Now we want to let the user enter additional values, and our logic will insert the values into the correct place in the ArrayList.

🔗

import java.util.Scanner;
import java.util.ArrayList;
public class Main {
   public static void main(String[] args) {
	// ArrayList code from above declaring variable and adding values
        System.out.println("Enter values to be inserted, -1000 to end"); 
        Scanner scan = new Scanner(System.in);
        int value = scan.nextInt();
        while (value != -1000) {
    	    int insertAtIndex = 0;
            while(insertAtIndex < decreasing.size() && decreasing.get(insertAtIndex) > value) {
                insertAtIndex++;
    	    }
    	    decreasing.add(insertAtIndex, value);
    	    System.out.println("Enter values to be inserted, -1000 to end"); 
    	    value = scan.nextInt();
        }
        System.out.println(decreasing);
   }
}

The purpose of the outer while loop is to continue reading values until the user enters a value signifying that they are done. This special value is sometimes called a sentinel. For this example, a user will enter the value -1000 to signify the end of the input. So the termination condition of the outer while loop is when the input is equal to -1000. We invert that to become the continuation condition (while input != -1000). The other important part of this outer while loop is the initialization of variables - we need to read the first value to be inserted before the loop and then update the value (read again) at the bottom of the loop. The initial read before the loop is sometimes called priming and is done to allow for 0 iterations of the loop. If the very first value the user types in is -1000 then the loop will never execute. Meanwhile the code at the end of the outer while loop is to read in the "next" value to be processed (the update part of the loop).

🔗

Now let’s look at the inner while loop:

🔗

int insertAtIndex = 0;
while(insertAtIndex < decreasing.size() && decreasing.get(insertAtIndex) > value) {
    insertAtIndex++;
}
decreasing.add(insertAtIndex, value);

We begin by initializing a variable (insertAtIndex) to be 0, the first possible spot to insert into the list. The boolean condition of the inner while loop says that while the index for inserting is still within the size of the loop (we haven’t walked off the end of the ArrayList) and the value in the ArrayList at that index is larger than the value we want to insert, then increment in the index.

🔗

Think about the termination of the inner while loop: that loop will end if insertAtIndex has a value of decreasing.size() OR the value at insertAtIndex in the ArrayList is <= to the value to be inserted. So if we have this example:

🔗

decreasing =

🔗

Table 14.3.1.

🔗

Index 🔗	0 🔗	1 🔗	2 🔗	3 🔗	4 🔗
Value 🔗	100 🔗	50 🔗	32 🔗	25 🔗	- 🔗

and the value = 41, initially insertAtIndex would be 0, which is less than decreasing.size() (value of 4).

🔗

Table 14.3.2.

🔗

insertAtIndex 🔗	decreasing.size() 🔗	decreasing.get 🔗 (insertAtIndex) 🔗	value 🔗	boolean condition 🔗
0 🔗	4 🔗	100 🔗	41 🔗	true 🔗
1 🔗	4 🔗	50 🔗	41 🔗	true 🔗
2 🔗	4 🔗	32 🔗	41 🔗	false 🔗

Once out of the inner while loop, we insert value into decreasing at the insertAtIndex location. For our example, insertAtIndex has a value of 2, so the value 41 would be inserted at index 2, which is exactly where it belongs.

🔗

Subsection 14.3.5 Practice Pages

Writing-ArrayLists-WE2-P1

🔗

🔗

You have attempted of activities on this page.

🔗

Prev Top Next