Arrays & Array Lists Flashcards
Array
A collection of values of the same type stored in contiguous memory locations, each of which can be accessed by an integer index.
How do you declare an array?
As with other objects, you have to use the new keyword to create an array and assign its memory address to a variable. Simply declaring an array reference variable does not create an array. You must take both steps:
double [] values = new double [10];
OR
int [] numbers;
numbers = new int[6];
However, when you declare an array you can also specify the initial values, in which case you don’t use the new keyword. The compiler will determine the length of the array for you by counting the inputs:
double [] moreValues = {32, 54, 78, 16, 20};
*Note, if you do not initialize an array with values then each values is 0 by default.
Size declarator
The number inside the brackets of an array initialization that specifies the size or length of the array. This is important because once the amount of elements that an array can hold is set it cannot be changed. While an array’s size declarator must be a non-negative integer, it can be expressed as a literal value or a variable. It is common practice to use a final variable as a size declarator:
final int NUM_ELEMENTS = 6;
int[] numbers = new int[NUM_ELEMENTS];
Subscript
Each element in an array is assigned a number known as a subscript. It is used as an index to pinpoint a specific element. The first element is subscript 0, the second element is subscript 1, and so forth.
*Note, you can use variables and calculations in subscripts. For example:
public boolean firstLast6(int[] nums)
{
if (nums[0] == 6 || nums[nums.length-1] == 6)
{
return true;
}
return false;
}
How do you access elements of an array?
You can use the subscript to access and use elements as individual variables. This is done with the notation array[i].
For example, to assign a value to specific element:
values[4] = 35;
To display a specific value:
System.out.println(values[4]);
To compare elements:
if (cost[20] < cost[17] )
How do you print the contents of an array?
Depending on the desired format, you can either write a loop or call the Array class’s toString( ) method. For example:
String[] friends = {“Sally”, “Anna”, “Maureen”};
// Print with loop
for (String friend : friends)
{
System.out.println(friend);
}
// You could also write this loop as follows:
for( int i = 0; i < friends.size(); i++)
{
System.out.println( friends.get( i ));
}
// Using the toString( ) method System.out.println(Arrays.toString(friends));
* Note, the toString( ) method will return the results in the following format: [Sally, Anna, Maureen]
Bounds error
Trying to access an array element that is outside the legal range, which is the most common error when working with arrays. For example, in the following array, the valid subscripts are 0 to 9. Java will not allow a statement to use a subscript that is less than 0 or greater than 9 with this array:
int[] values = new int[10];
However, it is common to make an “off by one error” when accessing array elements and in this case, try to access element 10, which doesn’t exist, for example. Be careful because bounds checking occurs at runtime! The compiler will not display an error. This means it will cause your program to terminate.
Asymmetric bounds
Bounds that include the starting index but not the ending index.
How can you find the number of elements in an array?
Use the expression array.length
* Note, there are no parentheses!
You can also use this expression to ensure that you only access elements within legal bounds:
if (0 <= i && i < values.length - 1)
{
// your code here
}
Partially filled array
An array that is not filled to capacity.
Companion variable
A companion variable keeps track of how many elements are used in a partially filled array. For example, in the following code that collects inputs and stores it in an array, currentSize is a companion variable:
int currentSize = 0;
Scanner in = new Scanner(System.in); while(in.hasNextDouble())
{
if(currentSize < values.length)
{
values[currentSize] = in.nextDouble();
currentSize++;
}
}
Unfilled array
Allocating an array variable without actually filling it is another common error that’s made when working with arrays. For example, the following statement creates an array variable but does not fill it with any objects:
BankAccount[] accounts = new BankAccount[10];
To fill it with accounts you also need to do something akin to the following:
for (int i = 0; i < 10; i++;)
{
accounts[i] = new BankAccount();
}
Parallel arrays
Arrays of the same length, in which corresponding elements are logically related, such as: int[] accountNumber; double[] balance; This is poor design and should be converted into a single array of objects that hold the related information. In this case, the parallel arrays should be changed to a single BankAccount array: BankAccount[] accounts;
Enhanced for loop
A short cut to visit, or traverse, all elements in a set such as an array. The following example sums all elements in an array: double[] values = { 6, 8, 16, 27…..} double total = 0; for (double element : values) { total = total + element; } However, it has some significant limitations. Chiefly, it does not allow you to modify values. For example, the following loop does not fill each element in the array with 0 (although this can be done with a basic for loop): for (double element : values) { element = 0; // error! }
Common array algorithms: Filling an array with values
The following loop fills an array with squares (0, 1, 4, 9, 16…..): for (int i = 0; i < values.length; i++)
{
values[i] = i * i;
}
Common array algorithms: Sum and average value
To compute a sum:
// initialize an accumulator
double sum = 0;
for (double element : values)
{
sum += element;
}
To compute the average just add a counter to the loop above and then divide the total by the counter.
Common array algorithms: Finding the maximum value
// initialize value with first array element
double max = values[0];
for (int i = 1; i < values.length; i++)
{
if (values[i] > max)
{
max = values[i];
}
}
* Note that the loop starts at 1 since we set the first element to the maximum value seen so far. Thus we cannot use an enhanced for loop here.
Common array algorithms: Finding the minimum value
// initialize value with first array element
double min = values[0];
for (int i = 1; i < values.length; i++)
{
if (values[i] < min)
{
min = values[i];
}
}
* Note that the loop starts at 1 since we set the first element to the minimum value seen so far. Thus we cannot use an enhanced for loop here.
Common array algorithms: Linear search
Also known as sequential search, this algorithm uses a loop to sequentially search through an array, starting with the first element. It compares each element with the target value and stops when the value is found or the end of the array is reached. For example, the following loop searches for the first element in an array that is equal to 100:
int searchedValue = 100;
int position = 0;
boolean found = false;
while (position < values.length && !found)
{
if (values[position] == searchedValue)
{
found = true;
}
else
{
position++;
}
if (found)
{
System.out.println(“Found at position “ position);
}
else
{
System.out.println(“Not found”);
}
}
Common array algorithms: Separating elements for display
When you display the elements of an array you usually want to separate them, often with commas or pipe delimiters: 32 | 54 | 67 | 12 | 3 Note that there is one fewer separator than numbers. Therefore you print the separator before each array element except the first one:
for (int i = 0; i < values.length; i++)
{
if (i > 0)
{
System.out.print(“ | “);
}
System.out.print(values[i]);
}
For comma separators, you can use the Arrays.toString method:
Arrays.toString(values)
This returns: [32, 54, 67, 12, 3]
