Array
2022년 4월 13일 수요일 오전 10:59
Array: a data strcture used to implement a collection (list) of primitive or object reference data
Element: a single value in the array
The index of an element is the position of the element in the array.
-In Java, the first element of an array is at index 0.
The length of an array is the number of elements in the array.
-length is a public final data member of an array
-Since length is public, we can access it in any class!
-Since length is final, we cannot change an array's length after it has been created
In Java, the last element of an array named list is at index [Link] -1
One-Dimensional Arrays
A one-dimensional array is a data structure used to implement a list object, where the elements in the list are of the same type; for example, a class list of 25 test scores, a
membership list of 100 names, or a store inventory of 500 itmes.
For an array of N elements in Java, index values ('subscripts") go from 0 to N - 1. Individual elements are accessed as follows: if arr is the name of the array , the
elements are individual elements are accessed as follows: If arr is the name of the array, the elements are arr[0], arr[1], … arr[n-1]. If a negative subscript is used, or a
subscript k where k
Initialization
In Java, an array is an object; therefore, the keyword new must be used in its creation. The one exception is an initializer list. The size of an array remains fixed once it
has been created. However, as with String objects, an array reference may be reassigned ot a new array of a different size.
Ex) All of the following are equivalent. Each creates an array of 25 double values and assigns the reference data to this array.
1. double[] data = new double [25];
2. double data [] = new double [25];
3. double [] = data;
data = new double [25];
A subsequent statement like
data = new double[40]
reassigns data to a new array of length 40. The memory allocated for the previous data array is recycled by Java's automatic garbage collection system.
When arrays are declared, the elements are automatically initialized to zero for the primitive numeric data types (int and double), to false for boolean variables, or to null
for object references.
It is possible to declare several arrays in a single statement.
Ex)
int[] intList1, intList2; //declare intList1 and intList2 to
//contain int values
int[] arr1 = new int[15], arr2 = new int[30]; //reserves 15 slots
//for arr1, 30 for arr2
Initializer List
Small arrays whose values are known can be conveniently declared with an initializer list.
Ex) instead of writing
int[] coins = new int[4];
coins[0] = 1;
coins[1] = 5;
coins[2] = 10;
coins[3] = 25;
you can write
int[] coisn = {1, 5, 10, 25};
This construction is the one case where new is not required to create an array.
Primitive Elements
Reference Elements
AP 페이지 1
Using initialier lists
Elements of an array initialized with a specific value based on the type of the element:
-Elements of type int are initialized to 0.
-Elements of a reference type are initialized to the reference value null.
-Element of type duble are intialized to 0.0
double [] listThree = new double [4];
-Element of type boolean are initialized to false
boolean [] listFour = new boolean [2];
When we know the values for the array at th etime of creation, an intializer list can be helpful.
double [] grades = {70.5, 88.2, 93.7, 98.7 };
String [] petNames = {"Ember", "Phoenix", "Kally" };
E is correct
AP 페이지 2
Free-response question
AP 페이지 3
AP 페이지 4
AP 페이지 5
Length of Array
A one-dimensional array in Java has a final public instance variable (i.e., a constant), length, which can be accseed when you need the number of elements in the array.
Ex)
String[] names = new String[25];
<code to initialize names>
//loop to process all names in array
for (int i = 0; i < [Link]; i++)
<process names>
Note
1. The array subscripts go from 0 to [Link]-1; therefore, the test on i in the for loop must be strictly less than [Link].
2. length is not a method and therefore is not followed by parentheses. Contrast this with String objects, where length is a method and must be followed by parentheses.
Ex)
String s = "Confusing syntax!";
int size = [Link](); //assigns 17 to size
Traversing a One-Dimensional Array
Use an enhanced for loop whenever you need access to every elements in an array without replacing or removing any elements. Use a for loop in all other cases: to
access the index of any element, to replace or remove elements, or to access just some of the elements.
Note that if you have an array of objects (not pirmitive types), you can use the enhanced for loop and mutator methods of the object to modify the fields of any instance.
Ex1)
/**Returns the number of even integers in array arr of integers. */
public static int countEven(int[] arr)
{
int count = 0;
for (int num : arr)
if (num 2 == 0) //num is even
count++;
return count;
}
Ex2)
/**Change each even-indexed element in array arr to 0.
* Precondition: xsxsarr contains integers.
* P c d : [0] [2] [4] … ve v lue 0
*/
public static void changeEven(int[] arr)
{
for (int i = 0; i < [Link]; i+=2)
arr[i] = 0;
}
AP 페이지 6
}
Bounds Errors
When using loops to access array element, we need to be careful with the condition in order to avoid an ArrayIndexOutOfBoundsException being thrown.
Ex1)
int [] list = new int[5];
for(int index = 0; index <= [Link]; index++) //<= is not allowed
{
list[index] = (int)([Link]() * 10)'
}
Ex2)
int [] arr = new int[5];
int position = 0;
while (position <= [Link]) //<= is not allowed
{
arr[position] = (int)([Link]() * 10);
position;
}
AP 페이지 7
Enhanced for loop with arrays
enhanced for loop is also called a for-each [Link] are only two parts to the enhanced for loop header and they're separated by a colon.
First half of an enhanced for loop signature is the type and name of the variable that is a copy of the value stored in the structure. Next, a colon separates the variable
section from the data structure being traversed with the loop.
Inside the body of the loop you are able to access the value stored in the variable. A key point to remember is that you are unable to assign into the variable defined in
the header(AKA signature).
You also do not have access to the indices of the array or subscript notation when using the enhanced for loop.
for(type declaration : structure)
{
//statement one;
//statement two;
…
}
Enhanced for loop with an array of int values
public static void main (String[] args)
{
int [] values = {14, 523, 7685, -123, 370}
for (int number : values)
{
[Link](number);
}
[Link]("Finished!");
}
14
523
7685
-123
370
Finished!
Enhanced for loop with an array of String
public static void main (String[] args)
{
String [] words {"alpha", "beta", "gamma", "delta"};
for (String word : words)
{
[Link](word);
}
[Link]("Finished!");
}
alpha
beta
gamma
delta
Finished!
Enhanced for loop with an array of DebugDuck
public static void main (String[] args)
{
DebugDeck [] ducks = {new DebugDuck(), new DebugDuck(3)};
for (DebugDuck current : ducks)
{
[Link]([Link]());
}
[Link]("Finished!");
}
0
3
Finished!
AP 페이지 8
Build the for each loop
for (Object currentThing : allTheThings)
{
[Link]([Link]());
}
Arrays as Parameters
Since arrays are treated as objects, passing an array as a parameter means passing its object reference. No copy is made of the array. Thus, the elements of the actual
array can be accessed-and modified.
Ex1) Array elements accessed but not modified:
/** Returns index of smallest element in array arr of integers. */
public static int findMin (int[] arr)
{
int min = arr[0];
int minIndex = 0;
for (int i = 0; i < [Link]; i++)
if (arr[i] < min) //found a smaller element
{
min = arr[i];
minIndex = i;
}
return minIndex;
}
To call this method (in the same class that it's a defined):
int [] array;
<code to initialize array>
int min = findMin(array);
Ex2)
Array elements modified:
/** Add 3 to each element of array b. */
public static void changeArray(int[] b)
{
for (int i = 0; i < [Link]; i++)
b[i] += 3;
}
To call this method (int the same class):
int [] list = {1, 2, 3, 4}
changeArray(list);
[Link]("The changed list is ";
for (int num : list)
[Link](num + " ");
The output produced is
The changed list is 4 5 6 7
Ex3) Contrast the changeArray method with the following attempt to modify one array element:
/** Add 3 to an element. */
public static void changeElement(int n)
AP 페이지 9
public static void changeElement(int n)
{ n += 3;}
Here is some code that invokes this method:
int[] list = {1, 2, 3, 4};
[Link] ("Original array: ");
for (int num : list)
[Link] (num + " ");
changeElement(list[0]);
[Link]("\nModified array: ");
for (int num : list)
[Link] (num + " ");
Contrary to the programmer's expectation, the output is
Original array: 1 2 3 4
Modified array 1 2 3 4
A look at the memory slots shows why the list remains unchanged.
The point of this is that primitive types-including single array elements of type int or double-are passed by value. A copy is made of the actual parameter, and the copy is
erased on exiting the method.
Ex4)
/** Swap arr[i] and arr[j] in array arr. */
public static void swap(int [] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
To call the swap method:
int[] list = {1, 2, 3, 4}
swap(list, 0, 3); //makes list (1,2,3,4) as arr, change value from 0 and 3.
[Link]("The changed list is: ");
for (int num : list)
[Link](num + " ");
The output shows that the program worked as intended:
The changed list is: 4 2 3 1
Ex5)
/**Returns array containing NUM_ELEMENTS integers read from the keyboard.
* Precondition: Array undefined.
* Postcondition: Array contains NUM_ELEMENTS integers read from the keyboard.
*
*/
public int[] getIntegers()
{
int[] arr = new int[NUM_ELEMENTS];
for (int i = 0; i <. [Link]; i++)
{
[Link]("Enter integer: ");
[ ] = …; e d u e pu
}
return arr;
}
To call this method:
int[] list = getIntengers()
How to calculate the average value from objects in an array
It is a common task to determine what is the average value returned from itmes stored inside an arrya. In order to do this, we need to a method that can take a parameter
of an array of Objects (DebugDuck) and calculate and return the average value that each instance of DebugDuck returns from the method.
Inside the method, a locial double vairble is needed to store the accumulated values. Then we use a for loop to traverse the array and add the current total to the variable.
After accumulating all the values we need to divide the toal by the number of itmes stored in the array.
Ex1)
private double calculateAverage(DebugDuck [ ] ducks)
{
double average = 0.0;
for (int index = 0; index < [Link]; index++)
{
AP 페이지 10
{
average += ducks[index].getQuestionCount();
}
average = average / [Link];
return average;
}
Ex2)
private double calculateAverage(DebugDuck [ ] ducks)
{
double average = 0.0;
for (DebugDeck currentDuck : ducks)
{
average += [Link]();
}
average = average / [Link];
return average;
}
Shifting Array contents to the right
The contents of an array often need to be shifted as part of a solution to using the data stored insdie.
We need to know how much to shift the array by. This will be need to be an int obviously.
In order to move the contents we next need to make an empty array of the same size and then literate over the original array and properly copy the values to the adjusted
index in the array.
We then need to assign the new array back into the original variable.
We must use a standard for loop, not an enhanced for loop since this algorithm is dependent on the index of each value in the array.
We can also shift using the same array and go to the left with the use of nested for loops. The outer loop will execute the number of times we are shifting. The inner loop
will first copy the value stored in the first index, then move all the contents one spot left. Finally copy the temp variable back to the end of the array.
Again, we must use a standard for loop, not an enhanced for loop since the algorithm is dependent on the index of each value in the array.
Ex1) Doing a right shift
public static void main(String [] args)
{
int [] numbers = {1, 2, 3, 4, 5};
int [] shifted = new int [[Link]];
int shift = 8;
for (int index = 0; index < [Link]; index++)
{
shifted [[Link]((index + shift) % [Link])] = number[index];
}
numbers = shifted;
for(int num : numbers)
{
[Link](num + " ");
}
}
3
4
5
1
2
Ex2) Doing a left shift
public static void main(String [] args)
{
String [] words = {"alpha", "beta", "gamma", "delta"};
int shiftWord = 2;
for (int count = 0; count < shiftWord; count++)
{
String temp = words[0];
for (int index = 0; index < [Link] - 1; index++)
{
words[index] = words[index + 1];
}
words[[Link] -1] = temp;
}
for (String word : words)
{
[Link](word + " ");
}
}
gamma
delta
alpha
beta
Note
1. We should use [Link] to call array index bceause if a negative number is assigned to the shift variable it will make the index of the array to be negative and cause
an IndexOutOfBoundsException to be thrown.
2. We should using the % operator to correctly account for the shift as the values wrap around the left and right sides of the array.
AP 페이지 11
Array Variables in a Class
Consider a simple Deck class in which a deck of cards is represented by the integers 0 to 51.
publci class Deck
{
private int[] deck;
public static final int NUMCARDS = 52;
/** constructor */
public Deck()
{
deck = new int[NUMCARDS];
for (int i = 0; i < NUMCARDS; i++)
deck[i] = i;
}
/** Write contents of Deck. */
public void writeDeck()
{
for (int card : deck)
[Link](card + " ");
[Link]();
[Link]();
}
/** Swap arr[i] and arr[j] in array arr. */
private void swap(int[] ar, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/** Shuffle Deck: Generate a random permutation by picking a
* random card from those remaining and putting it in the
* next slot, starting from the right.
*/
public void shuffle()
{
int index;
for (int i = NUMCARDS - 1; i > 0l i--)
{
//generate an int from o to I
index = (int) ([Link]() * (i + 1));
swap(deck, i, index);
}
}
}
Here is a simple dirver class that tests the Deck class:
public class DeckMain
{
public static void main(String args[])
{
deck d = new Deck();
[Link]();
[Link]();
}
}
Note
There is no evidnce of the array that holds the deck of cards-deck is a private instance variable and it therefore invisible to clients of the Deck class.
Array of Class Objects
Suppose a large card to tournament needs to keep track of many decks. The code to do this could be implemented with an array of Deck:
public class ManyDecks
{
private Deck[] allDecks;
public static final int NUMDECKS = 500;
/** constructor */
public ManyDecks()
{
allDecks = new Deck[NUMDECKS]
for (int i = 0; i < NUMDECKS; i++)
allDecks[i] = new Deck();
}
/** Shuffle the Decks. */
public void shuffleAll()
{
for (Deck d : allDecks)
[Link]();
}
AP 페이지 12
/** Write contents of all the Decks. */
public void printDecks()
{
for (Deck d : allDecks)
[Link]();
}
}
Note
1. The statement
allDecks = new Deck[NUMDECKS];
creates an array, allDecks, of 500Deck objects. The default initialization for these Deck objects is null. In order to initialize them with actual decks, the Deck constructor
must be called for each array element. This is achieved with the for loop of the ManyDecks constructor.
2. In the shuffleAll method, it's okay to use an enhanced for loop to modify each deck in the array with the mutator method shuffle.
Analyzing Array Algorithms
Ex1) Discuss the efficiency of the countNegs method below. What are the best and worst case configurations of the data?
/** Returns the number of negative values in arr.
* P ec d : [0] … [ le g -1] contain integers.
*/
public static int countNegs(int[] arr)
{
int count = 0;
for (int num : arr)
if (num < 0)
count++;
return count;
}
Solution:
This is algorithm sequentially examines each element in the array. In the best case, there are no negative elements, and count++ is never executed. In the worst case, all
the elements are negative, and count++ is executed in each pass of the for loop.
Ex2) The code fragment below inserts a value num, into its correct position in a sorted array of integers. Discuss the efficiency of the algorithm.
/** Precondition
* - arr[0],...arr[n-1] contain integers sorted in increasing order.
* -n < [Link].
* Postcondition: num has been inserted in its correct position.
*/
{
//find insertion point
int i = 0;
while (i < n && num > arr[i])
i++;
//if necessary, move elements arr[i]...arr[n-1] up 1 slot
for (int j = n; j >= i+1; j--)
arr[j] = arr[j-1];
//insert num in i-th slot and update n
arr[i] = num;
n++;
}
Solution:
In the best case, num is greater than all the elements in the array: Because it gets inserted at the end of the list, no elements must be moved to create a slot for it. The
worst case has num less than all the elements in the array. In this case, num must be inserted in the first slot, arr[0], and every element in the array must be moved up one
position to create a slot.
This is algorithm illustrates a disadvantage of arrays: Insertion and deletion of an element in an ordered list is inefficient, since, in the worst case, it may involve moving
all the elements in the list.
AP 페이지 13