Fiveable
Fiveable

or

Log in

Find what you need to study


Light

Find what you need to study

7.4 Developing Algorithms Using ArrayLists

7 min readdecember 30, 2022

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

Standard Algorithms

Using the traversals and methods that we have learned in the previous two topics, we can make the same algorithms that we have developed for arrays (see Topic 6.4) with slight changes. Here, we will have a snippet for each algorithm you are expected to know, with each snippet annotated for you.

Modifying Array Values

/** Doubles each element of the */ public static void doubleArray(<Integer> array) { for (int i = 0; i < array.size(); i++) { array.set(i, array.(i) * 2); // doubles each individual element } }

Modifying Instance Variables of Objects in an Array

/** Represents a student */ public class Student { String name; /** Sets the name of the Student */ public void setName(String name) { this.name = name; } /** Other instance variables, methods, and constructors not shown */ } // IN ANOTHER CLASS /** Resets all students' names */ public static void doubleArray(<Student> array, String defaultName) { for (Student student: array) { student.setName(defaultName); // Sets each student's name to a default name } }

Finding the Minimum and Maximum

/** Finds the maximum */ public static int maximum(<Integer> array) { int maxValue = array.(0); for (int number: array) { if (number > maxValue) { //if new max value found, replace current maxValue maxValue = number; } } maxValue; } /** Finds the minimum */ public static int minimum(<Integer> array) { int minValue = array.(0); for (int number: array) { if (number < minValue) { //if new min value found, replace current minValue minValue = number; } } minValue; }

A common mistake is initializing the maxValue and minValue to 0.

  • If all the values in the array are positive, it would incorrectly keep minValue at 0 (all the values are greater than 0, leaving 0 as the minimum).

  • If all the values in the array are negative, it would incorrectly keep maxValue at 0 (all the values are less than 0, leaving 0 as the maximum).

To counter these errors, initialize these to the first value in the array.

Finding a Sum

/** Sums up all elements in the */ public static int sum(<Integer> array) { int sum = 0; for (int number: array) { sum += number; //adds every element to sum } sum; }

Finding a Mean

/** Finds the mean/average of the */ public static int mean(<Integer> array) { int sum = sum(array); // find the sum of the , can be replaced with sum algorithm above (double) sum / (array.size()); }

Finding a Mode

/** Finds the mode of an Prerequisite: The array must have a mode */ public static int mode(<Integer> array) { int mostCommon = 0; int mostCommonFrequency = 0; for (int i = 0; i < array.size() - 1; i++) { //traverse through the int currentFrequency = 1; for (int j = i + 1; j < array.size(); j++) { //traverse through rest of if (array.(j) == array.(i)) { // if any element matches current element being checked, add 1 to frequency

currentFrequency++; } } if (currentFrequency > mostCommonFrequency) { mostCommon = array.(i); // replaces current mode if new most common element mostCommonFrequency = currentFrequency; } } mostCommon; // can also be modified to the frequency }

Determining If All Values Have a Certain Property

/** Determines whether all values are even */ public static isEven(<Integer> array) { //Assume all values are positive first for (int number: array) { if (number % 2 == 1) { //If there is one value that is not positive, false false; } } true; //No odd numbers were found }

Accessing All Consecutive Pairs/Triplets/Sequences of Length n of Elements

/** Returns all consecutive sequences of length n in the */ public static void returnAllConsecutiveSequences(<Integer> array, int length) { for (int i = 0; i <= array.size() - length; i++) { for (int j = 0; j < length; j++) {

//2 loops, one to the starting number the other to go through the sequences System.out.print(array.(i+j) + " "); } System.out.println(); } }

Checking if There are Duplicate Elements

/** Checks to see if there are duplicate elements */ public static duplicates(<Integer> array) { for (int i = 0; i < array.size() - 1; i++) { //traverse through the for (int j = i + 1; j < array.size(); j++) { //traverse through rest of if (array.(j) == array.(i)) {

// if any element matches current element being checked, true true; } } } false; // if this point reached, no duplicates found }

Determining How Many Elements Fit a Criteria

/** Returns how many even numbers there are */ public static int evenFrequency(<Integer> array) { int numberEven = 0; for (int number: array) { if (number % 2 == 0) { numberEven++; // increments every time an even integer is found } } numberEven; }

Shifting Elements One Index Left

/** Shifts Elements One Index to the Left */ public static <Integer> shiftLeft(<Integer> array) { int firstItem = array.(0) for (int i = 0; i < array.size() - 1; i++) { array.set(i, array.(i+1)); // Does the shifting } array.set(array.size() - 1, firstItem) array; }

Shifting Elements One Index Right

/** Shifts Elements One Index to the Right */ public static <Integer> shiftRight(<Integer> array) { int lastItem = array.(array.size()- 1) for (int i = array.size() - 1; i > 0; i--) { array.set(i, array.(i-1)); // Does the shifting } array.set(0, lastItem); array; }

Reversing an Array

/** Reverses the */ public static <Integer> reverse(<Integer> array) { <Integer> newArray = new <Integer>(); for (int i = 0; i < array.size(); i++) {

// places the items in the new in opposite order of the original newArray.add(array.(array.size() - i - 1)); } newArray; }

Putting Items from an ArrayList into an Array

/** Transfers all items into an Array */ public static int[] arrayListToArray(<Integer> array) { int[] newArray = new int[array.size()]; for (int i = 0; i < array.size(); i++) { newArray[i] = array.(i); } newArray; }

Putting Items from an Array into an ArrayList

/** Transfers all Array items into an */ public static <Integer> arrayToArrayList(int[] array) { <Integer> newArray = new <Integer>(); for (int i: array) { newArray.add(i); } newArray; }

Key Terms to Review (8)

% operator (modulus)

: The % operator, also known as the modulus operator, returns the remainder of a division operation. It is used to find the remainder when one number is divided by another.

+= operator

: The += operator is known as an assignment operator. It adds the value on the right-hand side of the operator to the variable on the left-hand side and assigns the result back to that variable.

ArrayList

: ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.

boolean

: A boolean is a data type that can only have two possible values: true or false. It is often used in programming to make decisions and control the flow of a program.

get

: The term "get" refers to retrieving the value of a variable or an object's property.

if statement

: An if statement is a programming construct that allows the execution of a block of code only if a certain condition is true.

Private

: In the context of programming, private refers to a visibility modifier that restricts access to certain variables or methods within a class. It means that only other members of the same class can access those private elements.

return

: The return keyword is used in functions/methods to send back a value to the caller. It terminates the execution of a function and passes control back to where it was called from.

7.4 Developing Algorithms Using ArrayLists

7 min readdecember 30, 2022

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

Athena_Codes

Athena_Codes

Milo Chang

Milo Chang

Standard Algorithms

Using the traversals and methods that we have learned in the previous two topics, we can make the same algorithms that we have developed for arrays (see Topic 6.4) with slight changes. Here, we will have a snippet for each algorithm you are expected to know, with each snippet annotated for you.

Modifying Array Values

/** Doubles each element of the */ public static void doubleArray(<Integer> array) { for (int i = 0; i < array.size(); i++) { array.set(i, array.(i) * 2); // doubles each individual element } }

Modifying Instance Variables of Objects in an Array

/** Represents a student */ public class Student { String name; /** Sets the name of the Student */ public void setName(String name) { this.name = name; } /** Other instance variables, methods, and constructors not shown */ } // IN ANOTHER CLASS /** Resets all students' names */ public static void doubleArray(<Student> array, String defaultName) { for (Student student: array) { student.setName(defaultName); // Sets each student's name to a default name } }

Finding the Minimum and Maximum

/** Finds the maximum */ public static int maximum(<Integer> array) { int maxValue = array.(0); for (int number: array) { if (number > maxValue) { //if new max value found, replace current maxValue maxValue = number; } } maxValue; } /** Finds the minimum */ public static int minimum(<Integer> array) { int minValue = array.(0); for (int number: array) { if (number < minValue) { //if new min value found, replace current minValue minValue = number; } } minValue; }

A common mistake is initializing the maxValue and minValue to 0.

  • If all the values in the array are positive, it would incorrectly keep minValue at 0 (all the values are greater than 0, leaving 0 as the minimum).

  • If all the values in the array are negative, it would incorrectly keep maxValue at 0 (all the values are less than 0, leaving 0 as the maximum).

To counter these errors, initialize these to the first value in the array.

Finding a Sum

/** Sums up all elements in the */ public static int sum(<Integer> array) { int sum = 0; for (int number: array) { sum += number; //adds every element to sum } sum; }

Finding a Mean

/** Finds the mean/average of the */ public static int mean(<Integer> array) { int sum = sum(array); // find the sum of the , can be replaced with sum algorithm above (double) sum / (array.size()); }

Finding a Mode

/** Finds the mode of an Prerequisite: The array must have a mode */ public static int mode(<Integer> array) { int mostCommon = 0; int mostCommonFrequency = 0; for (int i = 0; i < array.size() - 1; i++) { //traverse through the int currentFrequency = 1; for (int j = i + 1; j < array.size(); j++) { //traverse through rest of if (array.(j) == array.(i)) { // if any element matches current element being checked, add 1 to frequency

currentFrequency++; } } if (currentFrequency > mostCommonFrequency) { mostCommon = array.(i); // replaces current mode if new most common element mostCommonFrequency = currentFrequency; } } mostCommon; // can also be modified to the frequency }

Determining If All Values Have a Certain Property

/** Determines whether all values are even */ public static isEven(<Integer> array) { //Assume all values are positive first for (int number: array) { if (number % 2 == 1) { //If there is one value that is not positive, false false; } } true; //No odd numbers were found }

Accessing All Consecutive Pairs/Triplets/Sequences of Length n of Elements

/** Returns all consecutive sequences of length n in the */ public static void returnAllConsecutiveSequences(<Integer> array, int length) { for (int i = 0; i <= array.size() - length; i++) { for (int j = 0; j < length; j++) {

//2 loops, one to the starting number the other to go through the sequences System.out.print(array.(i+j) + " "); } System.out.println(); } }

Checking if There are Duplicate Elements

/** Checks to see if there are duplicate elements */ public static duplicates(<Integer> array) { for (int i = 0; i < array.size() - 1; i++) { //traverse through the for (int j = i + 1; j < array.size(); j++) { //traverse through rest of if (array.(j) == array.(i)) {

// if any element matches current element being checked, true true; } } } false; // if this point reached, no duplicates found }

Determining How Many Elements Fit a Criteria

/** Returns how many even numbers there are */ public static int evenFrequency(<Integer> array) { int numberEven = 0; for (int number: array) { if (number % 2 == 0) { numberEven++; // increments every time an even integer is found } } numberEven; }

Shifting Elements One Index Left

/** Shifts Elements One Index to the Left */ public static <Integer> shiftLeft(<Integer> array) { int firstItem = array.(0) for (int i = 0; i < array.size() - 1; i++) { array.set(i, array.(i+1)); // Does the shifting } array.set(array.size() - 1, firstItem) array; }

Shifting Elements One Index Right

/** Shifts Elements One Index to the Right */ public static <Integer> shiftRight(<Integer> array) { int lastItem = array.(array.size()- 1) for (int i = array.size() - 1; i > 0; i--) { array.set(i, array.(i-1)); // Does the shifting } array.set(0, lastItem); array; }

Reversing an Array

/** Reverses the */ public static <Integer> reverse(<Integer> array) { <Integer> newArray = new <Integer>(); for (int i = 0; i < array.size(); i++) {

// places the items in the new in opposite order of the original newArray.add(array.(array.size() - i - 1)); } newArray; }

Putting Items from an ArrayList into an Array

/** Transfers all items into an Array */ public static int[] arrayListToArray(<Integer> array) { int[] newArray = new int[array.size()]; for (int i = 0; i < array.size(); i++) { newArray[i] = array.(i); } newArray; }

Putting Items from an Array into an ArrayList

/** Transfers all Array items into an */ public static <Integer> arrayToArrayList(int[] array) { <Integer> newArray = new <Integer>(); for (int i: array) { newArray.add(i); } newArray; }

Key Terms to Review (8)

% operator (modulus)

: The % operator, also known as the modulus operator, returns the remainder of a division operation. It is used to find the remainder when one number is divided by another.

+= operator

: The += operator is known as an assignment operator. It adds the value on the right-hand side of the operator to the variable on the left-hand side and assigns the result back to that variable.

ArrayList

: ArrayList is a dynamic data structure that allows you to store and manipulate collections of objects. Unlike arrays, ArrayLists can grow or shrink dynamically as needed.

boolean

: A boolean is a data type that can only have two possible values: true or false. It is often used in programming to make decisions and control the flow of a program.

get

: The term "get" refers to retrieving the value of a variable or an object's property.

if statement

: An if statement is a programming construct that allows the execution of a block of code only if a certain condition is true.

Private

: In the context of programming, private refers to a visibility modifier that restricts access to certain variables or methods within a class. It means that only other members of the same class can access those private elements.

return

: The return keyword is used in functions/methods to send back a value to the caller. It terminates the execution of a function and passes control back to where it was called from.


© 2024 Fiveable Inc. All rights reserved.

AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.


© 2024 Fiveable Inc. All rights reserved.

AP® and SAT® are trademarks registered by the College Board, which is not affiliated with, and does not endorse this website.