Unit 7 - Array List P3
A Unit of documents that overview Array Lists in Java
- 7.2 ARRAY LIST METHODS
- Essential Knowledge
- We will be learning about Sequential Searching but also known as Linear Searching.
- Selection Sort.
- College Board Example code below…
- Some common questions:
- Inserting Sort
- College Board Example code below…
UNIT 7: ARRAY LISTS
7.1: Array List Intro
7.2: Array List Methods</p> 7.3 Traversing Array Lists</p> 7.4: Developing Algorithms Using Array Lists</p> 7.5: Searching</p> 7.6: Sorting</p> 7.7: Ethical issues around Data Collection</p>
7.1 ARRAY LIST INTRO
- ArrayList is a resizeable array
- ArrayLists are dynamic meaning that its size can be altered as necessary
-
Instead of creating a new array of a different size and copying the data from the initial array to the new one, we can use ArrayLists
- To use an arrayList it is necessary to be imported from the java util package
VOCABULARY
Static: Once initialized, size cannot be changed (arrays)
Dynamic: Size of list can be changed at any time (arrayLists)
import java.util.ArrayList; // Import the ArrayList class
// Declare and initialize an ArrayList of integers
ArrayList<Integer> numbersList = new ArrayList<>();
System.out.println(numbersList);
- ArrayLists are created in a similar manner as other object classes
- in the <> when declaring an arrayList is the data type it will contain. (integer, string, etc…)
- Can also make an arraylist without declaring the data type but it can prevent error detection
ArrayList<String> wordList = new ArrayList<String>(); // with data type
ArrayList blankList = new ArrayList(); // without data type
System.out.println(wordList);
7.2 ARRAY LIST METHODS
- You can get the number of items in an ArrayList using the .size() method
- All arrayLists start with 0
ArrayList<String> sizeList = new ArrayList<String>();
System.out.println(sizeList.size());
-
You can add values to an array list by using add method. syntax: list.add(obj)
-
How you would join the end of a line to buy a ticket (similar concept)
ArrayList<String> addList = new ArrayList<String>();
addList.add("CSA");
System.out.println(addList.size());
System.out.println(addList);
-
int size() - Returns the count of elements within the list.
-
boolean add(E obj) - Appends the object obj to the end of the list and returns true.
-
void add(int index, E obj) - Inserts obj at the specified index, shifting elements at and above that position to the right (incrementing their indices by 1) and increasing the list’s size by 1.
-
E get(int index) - Retrieves the element at the given index in the list.
-
E set(int index, E obj) - Replaces the element at the specified index with obj and returns the previous element at that index.
-
E remove(int index) - Deletes the element at the specified index, shifting all subsequent elements one index to the left, reducing the list’s size by one, and returning the removed element.
-
Java allows the generic ArrayList
, where the generic type E specifies the type of element. -
When ArrayList
is specified, the types of the reference parameters and return type when using the methods are type E. -
ArrayList
is preferred over ArrayList because it allows the compiler to find errors that would otherwise be found at runtime.
ArrayList<Integer> a1 = new ArrayList<>();
System.out.println(a1.size());
ArrayList<Double> a2 = new ArrayList<>();
a2.add(1.0);
a2.add(2.0);
a2.add(3.0);
System.out.println(a2);
a2.remove(2.0);
System.out.println(a2);
import java.util.ArrayList;
// Create ArrayList of Integers
ArrayList<Integer> a1 = new ArrayList<>();
System.out.println("Initial size of a1: " + a1.size());
// Create ArrayList of Doubles and add elements
ArrayList<Double> a2 = new ArrayList<>();
a2.add(1.0);
a2.add(2.0);
a2.add(3.0);
System.out.println("Initial a2: " + a2);
// Remove element at index 2
a2.remove(2); // Use index for removal, not value
System.out.println("After removing element at index 2: " + a2);
// Insert element at index 1
a2.add(1, 1.5);
System.out.println("After inserting 1.5 at index 1: " + a2);
// Retrieve element at index 2
Double elementAtIndex2 = a2.get(2);
System.out.println("Element at index 2: " + elementAtIndex2);
// Replace element at index 1
Double previousElement = a2.set(1, 1.75);
System.out.println("After replacing element at index 1: " + a2);
System.out.println("Previous element at index 1: " + previousElement);
// Get the size of a2
int sizeOfA2 = a2.size();
System.out.println("Size of a2: " + sizeOfA2);
POPCORN HACKS 7.1 & 7.2 Create an ArrayList of Strings with the following elements: “Apple”, “Banana”, “Cherry”, “Date”, “Elderberry”. Complete the following tasks using the ArrayList methods you’ve learned:
- Task 1: Print the size of the ArrayList.
- Task 2: Add a new element “Fig” to the end of the list.
- Task 3: Insert “Grape” at index 2.
- Task 4: Replace the element at index 4 with “Guava”.
- Task 5: Remove the element at index 1.
- Task 6: Retrieve and print the element at index 3.
At the end of each task, print the current state of the ArrayList to verify the result.
7.3: Traversing Arrays
variable.get(i) retreives #i value. variable.remove(i) removes #i value from a list. when you remove #i value from a list, it will move all the values in that ArrayList up one value. under and over traversing results in errors.
traversing using and enhanced for loop known as for-each goes from first to last order in an ArrayList easier to setup than for loop structure consists of:
for (DataType variable : Collection )
{
// statement one;
// statement two;
// ...
}
example of how to use an enhanced for loop is this segment of code being used to determine the total number of charecters needed to write out the roster of student names:
int sum=0;
for (String names : roster)
{
sum = sum +name.length();
}
the biggest flaw of all with enhanced for loops is the fact that rather than updati0ng the ArrayList, they create a copy of the ArrayList. when you try to add entry, it brings up the error: ConcurrentModificationException
import java.util.ArrayList
you cannot declare or instantiate a ArrayList witha primitive data type include parenthasis () at the end of the Arraylist Constructor call not specifying the element type is a common problem when removing elements, ensure that you are not skipping over elements after removal.
swapConsecutive(ArrayList<Double> myList)
7.4 Developing ALgorithms Using Array Lists
Essential Knowledge
-> Iteration statements provide a means to access all the elements stored within an ArrayList. This process is referred to as “traversing the ArrayList.”
-> The following methods related to ArrayLists, their functions, and appropriate use are covered in the Java Quick Reference:
-> int size() - Returns the count of elements within the list.
-> boolean add(E obj) - Appends the object obj to the end of the list and returns true.
-> void add(int index, E obj) - Inserts obj at the specified index, shifting elements at and -> above that position to the right (incrementing their indices by 1) and increasing the list's size by 1.
-> E get(int index) - Retrieves the element at the given index in the list.
-> E set(int index, E obj) - Replaces the element at the specified index with obj and returns the previous element at that index.
-> E remove(int index) - Deletes the element at the specified index, shifting all subsequent elements one index to the left, reducing the list's size by one, and returning the removed element.
->There exist established algorithms for ArrayLists that make use of traversals to:
-> Insert elements.
-> Remove elements.
-> Apply the same algorithms commonly used with 1D arrays.
List<Integer> list1 = new ArrayList<Integer>();
list1.add(new Integer(1));
list1.add(new Integer(2));
list1.add(new Integer(3));
list1.remove(1);
A. [2, 3]
B. [1, 2, 3]
C. [1, 2]
D. [1, 3]
List<Integer> numList = new ArrayList<Integer>();
numList.add(new Integer(1));
numList.add(new Integer(2));
numList.add(new Integer(3));
numList.set(2,new Integer(4));
numList.add(1, new Integer(5));
numList.add(new Integer(6));
A. [1, 2, 3, 4, 5]
B. [1, 2, 4, 5, 6]
C. [1, 2, 5, 4, 6]
D. [1, 5, 2, 4, 6]
public class ArrayListExample {
private double getMax(double[] numbers) {
double highest = numbers[0];
for (double num : numbers) {
if (num > highest) {
highest = num;
}
}
return highest;
}
public static void main(String[] args) {
double[] nums = {1.0, 3.8, 2.0, 2.0, 1.9, 70.2, 2.0, 4.0, 6.3, 2.1, 5.0, 10.7};
ArrayListExample instance = new ArrayListExample();
System.out.println(instance.getMax(nums));
}
}
ArrayListExample.main(null);
When you look at the code above you should pay attention to the getMax() method. What the method is doing is it accepts a list of doubles as input and then uses a for loop to determine the highest value in the list.
Now instead of using just a List of Doubles, lets use an ArrayList of Doubles.
public class ArrayListExample {
private double getMax(ArrayList<Double> numbers) {
double highest = numbers.get(0);
for (double num : numbers) {
if (num > highest) {
highest = num;
}
}
return highest;
}
public static void main(String[] args) {
ArrayList<Double> nums = new ArrayList<>(Arrays.asList(1.0, 3.8, 2.0, 2.0, 1.9, 70.2, 2.0, 4.0, 6.3, 2.1, 5.0, 10.7));
ArrayListExample instance = new ArrayListExample();
System.out.println(instance.getMax(nums));
}
}
ArrayListExample.main(null);
Finish the code below so that it uses the findSum() method and it finds the sum of the numbers.
public class ArrayListHacks {
private int findSum(ArrayList<Integer> values) {
// Your code here
return 0;
}
public static void main(String[] args) {
ArrayList<Integer> nums = new ArrayList<>();
nums.add(0);
nums.add(1);
nums.add(2);
nums.add(3);
nums.add(5);
nums.add(8);
ArrayListHacks hacks = new ArrayListHacks();
hacks.findSum(nums);
}
}
ArrayListHacks.main(null);
7.5 Searching
We will be learning about Sequential Searching but also known as Linear Searching.
Linear search looks for a value in unsorted data by checking each element in order that the data is in. It then returns the index if found, or -1 if the value isn’t in the list.
public class ArraySearcher {
public static int sequentialSearch(int[] elements, int target) {
for (int j = 0; j < elements.length; j++) {
if (elements[j] == target) {
return j;
}
}
return -1;
}
public static void main(String[] args) {
int[] numArray = {3, -2, 9, 38, -23};
System.out.println("Tests of sequentialSearch");
System.out.println(sequentialSearch(numArray, 3));
System.out.println(sequentialSearch(numArray, 9)); // Expected output: 2
System.out.println(sequentialSearch(numArray, -23)); // Expected output: 4
System.out.println(sequentialSearch(numArray, 99)); // Expected output: -1
}
}
ArraySearcher.main(null);
You can also look for a String in an array or list, but be sure to use equals rather than ==. Remember that == is only true when the two references refer to the same String object, while equals returns true if the characters in the two String objects are the same.
public class SearchTest
{
public static int sequentialSearch(String[] elements, String target)
{
for (int j = 0; j < elements.length; j++)
{
if (elements[j].equals(target))
{
return j;
}
}
return -1;
}
public static void main(String[] args)
{
String[] arr1 = {"blue", "red", "purple", "green"};
// test when the target is in the array
int index = sequentialSearch(arr1, "red");
System.out.println(index);
// test when the target is not in the array
index = sequentialSearch(arr1, "pink");
System.out.println(index);
}
}
SearchTest.main(null)
7.6 - ArrayLists, Sorting
Selection Sort.
- The one of the easiest sorts to demonstrate.
- The selection sort identifies either the maximum or minimum of the compared values and iterates over the structure checking if the item stored at the index matches that condition, if so, it will swap the value stroed at that index and continue.
- This implementation uses a helper method to perform the swap operation since variables can hold only one value at a time!!!
Let’s use this array as an example: arr[] = {64, 25, 12, 22, 11}
College Board Example code below…
public class SelectionSortExample {
public static void main(String[] args) {
// Example array of DebugDuck objects
DebugDuck[] myDucks = {
new DebugDuck(5),
new DebugDuck(1),
new DebugDuck(3),
new DebugDuck(4),
new DebugDuck(2)
};
// Perform selection sort
selectionSort(myDucks);
// Print sorted array
System.out.println("Sorted array:");
for (DebugDuck duck : myDucks) {
System.out.println(duck);
}
}
// Method to perform selection sort
public static void selectionSort(DebugDuck[] myDucks) {
for (int outerLoop = 0; outerLoop < myDucks.length; outerLoop++) {
// Start by assuming the current item is the smallest
int minIndex = outerLoop;
// Check the rest of the array for anything smaller
for (int inner = outerLoop + 1; inner < myDucks.length; inner++) {
// If you find something smaller, update the index
if (myDucks[inner].compareTo(myDucks[minIndex]) < 0) {
minIndex = inner;
}
}
// If the smallest item isn’t already in the right place, swap them
if (minIndex != outerLoop) {
swapItems(minIndex, outerLoop, myDucks);
}
}
}
// Method to swap elements in the array
private static void swapItems(int i, int j, DebugDuck[] myDucks) {
DebugDuck temp = myDucks[i];
myDucks[i] = myDucks[j];
myDucks[j] = temp;
}
}
// DebugDuck class implementing Comparable
class DebugDuck implements Comparable<DebugDuck> {
private int someAttribute;
public DebugDuck(int someAttribute) {
this.someAttribute = someAttribute;
}
@Override
public int compareTo(DebugDuck other) {
return Integer.compare(this.someAttribute, other.someAttribute);
}
@Override
public String toString() {
return "DebugDuck{" + "someAttribute=" + someAttribute + '}';
}
}
Another Example…
public class SelectionSort {
public static void main(String[] args) {
int[] numbers = {64, 25, 12, 22, 11}; // Example array of numbers
// Perform selection sort
for (int outerLoop = 0; outerLoop < numbers.length - 1; outerLoop++) {
// Start by assuming the current item is the smallest
int minIndex = outerLoop;
// Check the rest of the array for anything smaller
for (int inner = outerLoop + 1; inner < numbers.length; inner++) {
// If you find something smaller, update the index
if (numbers[inner] < numbers[minIndex]) {
minIndex = inner;
}
}
// If the smallest item isn’t already in the right place, swap them
if (minIndex != outerLoop) {
// Swap numbers[outerLoop] and numbers[minIndex]
int temp = numbers[outerLoop];
numbers[outerLoop] = numbers[minIndex];
numbers[minIndex] = temp;
}
}
// Print the sorted array
System.out.println("Sorted array:");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
How does the swapping actualy happen?
- We use swap-item mothod.
Swap Algorithm
private void swapItems(int firstIndex, int secondIndex, Object[] arrayOfStuff)
{
// **thirdHand** temporarily holds the value from firstIndex so it doesn't get lost during the swap
Object thirdHand = arrayOfStuff[firstIndex];
// Move the value from secondIndex to firstIndex
arrayOfStuff[firstIndex] = arrayOfStuff[secondIndex];
// Place the value that was originally at firstIndex (stored in thirdHand) into secondIndex
arrayOfStuff[secondIndex] = thirdHand;
}
// First you will see the three parameters as you can see below↓↓↓
// **The firstIndex** = The index of the first item to be swapped.
// **The secondIndex** = The index of the second item to be swapped.
// **arrayOfStuff** = The array where the swapping takes place.
Some common questions:
Can an enhanced for loop be used?
- Answer: No, The Selection Sort algorithm needs to know the index of the item it is working with.
How does the swap occur?
- Answer: A third variable is needed to temporarily hold on to the swapped value from the array since variables can only hold one thing at a time.
Inserting Sort
- The insertion sort is characterized by building a sorted structure as it proceeds. It inserts each value it finds at the appropriate location in the data structure. This is often accomplished by using a while loop as the inner loop.
- Consider an array having elements : {23, 1, 10, 5, 2}
initial:
- Current element is 23
- The first element in the array is assumed to be sorted.
- The sorted part until 0th index is : [23]
First Pass:
- Compare 1 with 23 (current element with the sorted part).
- Since 1 is smaller, insert 1 before 23 .
- The sorted part until 1st index is: [1, 23]
Second Pass:
- Compare 10 with 1 and 23 (current element with the sorted part).
- Since 10 is greater than 1 and smaller than 23 , insert 10 between 1 and 23 .
- The sorted part until 2nd index is: [1, 10, 23]
Third Pass:
- Compare 5 with 1 , 10, and 23 (current element with the sorted part).
- Since 5 is greater than 1 and smaller than 10 , insert 5 between 1 and 10
- The sorted part until 3rd index is : [1, 5, 10, 23]
Fourth Pass:
- Compare 2 with 1, 5, 10 , and 23 (current element with the sorted part).
- Since 2 is greater than 1 and smaller than 5 insert 2 between 1 and 5 .
- The sorted part until 4th index is: [1, 2, 5, 10, 23]
Final Array:
- The sorted array is: [1, 2, 5, 10, 23]
College Board Example code below…
import java.util.ArrayList;
import java.util.List;
// Create a list of DebugDuck objects
List<DebugDuck> randomList = new ArrayList<>();
randomList.add(new DebugDuck(5));
randomList.add(new DebugDuck(1));
randomList.add(new DebugDuck(3));
randomList.add(new DebugDuck(4));
randomList.add(new DebugDuck(2));
// Print unsorted list
System.out.println("Unsorted list:");
for (DebugDuck duck : randomList) {
System.out.println(duck);
}
// Perform insertion sort
for (int outer = 1; outer < randomList.size(); outer++) {
// Store the current element to be inserted into the sorted portion
DebugDuck tested = randomList.get(outer);
int inner = outer - 1;
// Move elements to the right if they are greater than 'tested'
while (inner >= 0 && tested.compareTo(randomList.get(inner)) < 0) {
// Shift element at 'inner' to the right
randomList.set(inner + 1, randomList.get(inner));
inner--;
}
// Insert 'tested' at the correct position
randomList.set(inner + 1, tested);
}
// Print sorted list
System.out.println("Sorted list:");
for (DebugDuck duck : randomList) {
System.out.println(duck);
}
// DebugDuck class implementing Comparable
class DebugDuck implements Comparable<DebugDuck> {
private int someAttribute;
public DebugDuck(int someAttribute) {
this.someAttribute = someAttribute;
}
@Override
public int compareTo(DebugDuck other) {
return Integer.compare(this.someAttribute, other.someAttribute);
}
@Override
public String toString() {
return "DebugDuck{" + "someAttribute=" + someAttribute + '}';
}
}
Unsorted list:
DebugDuck{someAttribute=5}
DebugDuck{someAttribute=1}
DebugDuck{someAttribute=3}
DebugDuck{someAttribute=4}
DebugDuck{someAttribute=2}
Sorted list:
DebugDuck{someAttribute=1}
DebugDuck{someAttribute=2}
DebugDuck{someAttribute=3}
DebugDuck{someAttribute=4}
DebugDuck{someAttribute=5}
Another Example…
6th PopCorn - Hack
Problem: Sort the Ducks!
You have a list of ducks, and each duck has a name and weight. Your task is to sort these ducks by weight in ascending order.
Choose either Selection Sort or Insertion Sort to do the sorting.
Example:
Given this list:
- Duck A (4.5 kg)
- Duck B (2.1 kg)
- Duck C (5.0 kg)
- Duck D (1.9 kg)
After sorting, the output should be:
- Duck D (1.9 kg)
- Duck B (2.1 kg)
- Duck A (4.5 kg)
- Duck C (5.0 kg)
You can use this class for the ducks:
class DebugDuck implements Comparable<DebugDuck> {
String name;
double weight;
public DebugDuck(String name, double weight) {
this.name = name;
this.weight = weight;
}
@Override
public int compareTo(DebugDuck other) {
return Double.compare(this.weight, other.weight);
}
@Override
public String toString() {
return name + " (" + weight + " kg)";
}
}
Task:
- Implement either sorting algorithm to sort the ducks by weight.
- Print the sorted list.
7.7:Ethical issues around data collection
-
Privacy Risks: Personal data can be vulnerable to breaches or misuse when stored in systems. Programmers need to protect it.
-
Protection Methods:
- Delete Data: Remove personal info when it’s no longer needed.
- Minimize Data: Only collect essential information.
- Anonymize Data: Use methods like
hashCode()in Java to hide real info. - Encrypt: Secure data so it can’t be easily accessed even if stolen.
The main goal? Keep personal data safe with smart coding practices.
7th mini Hack:
What can be used in place of the blank to ensure the users data is cleared?
ArrayList<String> userData = new ArrayList<>();
userData.add("John Doe");
userData.add("john@example.com");
// Once you're done using the data
userData.clear(); // Removes all entries
userData = _____; //