Array Lists
2022년 4월 14일 목요일 오후 5:39
An ArrayList provies an alternative way of storing a list of objects and has the following advantages over an array:
-An ArrayList shrinks and grows as needed in a program, whereas an array has a fixed length that is set when the array is created.
-In an ArrayList, list, the last slot is always [Link]()-1, whereas in a partially filled array, you, the programmer, must keep track of the last slot currently in use.
-For an ArrayList, you can do insetion or deletion with just a single statement. Any shifting of elements is handled automatically. However, in an array, insertion or
delection requires you to write the code that shifts the elements.
-It is easier to print the elements of an ArrayList than those of an array. For an ArrayList list and an array arr, the statement
[Link](list);
will output the elements of list, nicely formatted in square brackets, with the elements separated by commas. Whereas to print the elements of arr, an explicit piece
of code that access and prints each element is needed. The statement
[Link](arr);
will produce weird output that includes an symbol-not the elements of the array.
The ArrayList Class
The ArrayList class is part of the [Link] package. An import statement makes this class available in a program. Java allows the generic type ArrayList<E>, where
E is the type of the elements in the ArrayList. When a generic class is declared, the type of parameter is replaced by an actual object type. For example,
private ArrayList<Clown> clowns;
In order to use the prewritten ArrayList class, you must import it from he [Link] package using the following Java code:
import [Link];
or
import [Link];
Import statements are usually used at the beginning of the Java file, before the class declaration.
Ex)
impot [Link];
public class Video7Point
{
public static void main(String[] args)
{
ArrayList<Integer> a1 = new ArrayList<Integer>();
ArrayList<String> a2 = new ArrayList<String>(5);
ArrayList<Student> a3 = new ArrayList<Student>();
}
}
Create an ArrayList
a) to store Boolean values
new ArrayList<Boolean>();
b) to store Trutle objects
new ArrayList<Turtle>();
c) To store 10 Strings, initially
new ArrayList<String>(10);
Differences between Array and ArrayList
Arrays are static in size, once initialized, their size conanot be changed.
ArrayLists are dynamic in size, the size of the list can be changed at any time.
Array
Fixed length
Fundamental Java feature
An Object with no methods
Not as flexible
Can store primitve data
ArrayList
Part of a Framework
A Class with many methods
Is designed to be flexible
Not designed to store primitives
Is slightly slower than Arrays
Can only be used with an import statement
Note
1. The ArrayList class is implemented using Arrays.
2. The clowns list must contain only Clown objects. An attempt to add an Acrobat to the list, for example, will cause a compile-time error.
AP 페이지 1
Declare a Variable to Reference an ArrayList object
ArrayList<DataType> variableName;
List<DataType> variableName;
Instantiate an ArrayList object
Stores only elements of the same, nonprimitive DataType
new ArrayList<DataType>();
new List<DataType>(n);
Primitive Values Disguised as Wrapper Class Objects
ArrayList objects are designed to only store references to objects, not primitive values. A workaround is to use Wrapper classes, which store primitive values as
objects.
Primitive Data Types Wrapper Class Data Types
boolean Boolean
char Character
double Double
int Integer
The Methods of ArrayList<E>
Here are the methods you should know:
ArrayList()
Constructor constructs an empty list.
int size()
Returns the number of elements in the list.
Ex) Consider the following code:
ArrayList<Integer> a1 = new ArrayList<Integer>();
The ArrayList a1 has been instantiated with no entries.
[Link]([Link]());
ArrayList<Double> a2 = new ArrayList<Double>(15);
Adding items to an ArrayList
boolean add(E obj)
Appends obj to the end of the list. Always returns true. If the specified element is not of type E, throws a run-time exception.
Ex)
ArrayList<String> h = new ArrayList<String>(); //line10
[Link]("Hello"); //line12 Hello
[Link]("Hello"); //line 13 Hello Hello
[Link]("HELLO"); //line 14 Hello Hello HELLO
[Link]("Hello"); //line 15 Hello Hello HELLO Hello
[Link](1, "Hola"); //line 16 Hello Hola Bello HELLO Hello
!To add objects to an ArrayList, the object must be of the same data type used to instantiate the ArrayList.
AP 페이지 2
E remove(int index)
Removes and returns the element at the specified index. Elements to the right of position index have 1 substracted from their indices. Size of list is decreased by 1.
Ex)
Hello Hola Hello HELLO Hello
[Link](3); //line 20
Hello Hola Hello Hello
String h1 = [Link](0); //21
Hola Hello Hello
[Link](h1); will print "Hello"
E set(int index, E element)
Replaces item at specified index in the list with specified element. Returns the element that was previously at index. If the specified element is not of type E, throws
a run-time exception.
Ex)
Hola Hello Hello
[Link](1, "Hola"); //line 30
Hola Hola Hello
String str = [Link](0, "Bonjour"); //line 31
Bonjour Hola Hello
[Link](str); //will print out "Hola"
E get(int index)
Returns the element at the specified index in the list.
Ex)
Hola Hello Hello
[Link](1, "Hola"); //line 30
Hola Hola Hello
String str = [Link](0, "Bonjour"); //line 31
Bonjour Hola Hello
[Link](str); //will print out "Hola"
void add(int index, E element)
Inserts element at specified index. Elements from position index and higher have 1 added to their indices. Size of list is incremented by 1.
AP 페이지 3
Note
Each of these methods that has an index parameter-add, get, remove, and set-throws an IndexOutOfBoundsException. if index is out of range. For get, remove, and
set, index is out of range if
index < 0 || index >= size()
However, for add, it is okay to add an element at the end of the list. Therefore index is out of range if
index < 0 || index > size()
Autoboxing and Unboxing
An ArrayList cannot contain a primitive type like double or int: it must only contian objects. (it actually contains the references to those objects.) Therefore,
numbers must be boxed-placed in wrapper classes like Integer and Double-before insertion into an ArrayList.
Autoboxing is the automatic wrapping of primitive types in their wrapper classes.
To retrieve the numerical value of an Integer (or Double) stored in an ArrayList, the intValue() (or doubleValue()) method must be invoked (unwrapping).
Unboxing is the automatic conversion of a wrapper class ot its corresponding primitive type. This means that you don't need t o explicitly call the intValue() or
doubleValue() methods. Be aware that if a program tries to auto-unbox null, the method will throw a NullPointerException.
Note that while autoboxing and unboxing cut down on code clutter, these operations must still be performed behind the scenes, leading to decreased run-time
efficiency. It is much more efficient to assign and access primitive types in an array than an ArrayList. Therefore, you should consider using an array for a program
that mainpulates sequences of numbers and deos not need to use objects.
Note
1. Autoboxing and unboxing is now a prt of the AP Java subset.
2. The List<E> interface and the methods of List<E> are not longer part of the AP Java subset.
Using ArrayList<E>
Ex1)
//Create an ArrayList containing 0 1 4 9.
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 4; i++)
[Link](i * i); //example of autoboxing
//i*i wrapped in an Integer before insertion
Integer intOb = [Link](2); //assigns Integer with value 4 to intOb.
//Leaves list unchanged.
Int n = [Link](3); //example of auto -boxing
//Integer is retrieved and converted to int
//n contains 9
Integer x = [Link](3, 5); //list is 0 1 4 5
//x contains Integer with value 9
x = [Link](2); //list is 0 1 5
//x contains Integer with value 4
[Link](1, 7); //list is 0 7 1 5
[Link](2, 8); //list is 0 7 8 1 5
Ex2)
/** Swap two values in list, indexed at i and j. */
public static void swap(ArrayList<E> list, int i, int j)
{
E temp = [Link](i);
[Link](i, [Link](j);
[Link](j, temp);
}
Ex3)
/** Returns an ArrayList of random integers from 0 to 100. */
public static ArrayList<Integer> getRandomIntList()
{
ArrayList<Integer> list = new ArrayList<Integer>();
[Link]("How many integers? ");
int length = …; //read user input
for (int i = 0; i < length; i++)
{
int newNum = (int) ([Link]() * 101);
[Link](newNum); //autoboxing
}
return list;
}
Methods with an ArrayList as a parameter
ArrayList is a reference object and when passed as a parameter in a method, they are passed as references to their addresses, not copie s of their values
ArrayList arr = new ArrayList90;
AP 페이지 4
When a method updates elements of a passed ArrayList, the ArrayList's elements are updated automatically.
true
Returning an ArrayList from a method
In order to return an ArrayList, it is preferred that you specify the data type of the elements that the ArrayList stores
AP 페이지 5
Traversing An ArrayList
To traverse an ArrayList means to access all of the elements of the list using an iteration statement(for loop, while loop, or enhanced for loop)
Here are several examples to illustrate different types of traversals.
Possible loop conditions to Traverse an ArrayList
Initialization Boolean Condition Update
a) int i = 0; i < [Link](); i++;
b) int i = 0; i <= [Link]()-1; i++;
c) int i = [Link]()-1; i >= 0; i--;
d) int i = [Link]()-1; i > -1; i--;
AP 페이지 6
AP 페이지 7
Enhanced for loop
Also named a for-each loop because it iterates through each element of the ArrayList.
By design, it iterates via a first-to-last order and will each element of the ArrayList.
Indexes are not explicitly used and copies of the current element are made at each iteration.
Easier to setup than a for loop
AP 페이지 8
For simple accessing-for example, printing each element or adding each element to a running total, etc. -an enchaned for loop is a convenient method of traversal.
Ex4)
/** Print all nevatives in list.
* Precondition: list contains Integer values.
*/
public static void printNegs(ArrayList<Integer> list)
{
[Link]("The negative values in the list are: ");
for (Ineger i : list)
if (i < 0) //auto-boxing
[Link](i);
}
Note
Here's how to think of this algorithm: For each Integer i in ArrayList list, create a local copy of the element, test if it's negative, and print it if negative.
To access an element with a specific index-for example, to replace the element at that index, or insert an element at that index -use an index traversal. Since the
indices for an ArrayList start at 0 and end at [Link]()-1, trying to access an element with an index value outside of this range will cause an
IndexOutOfBoundsException to be thrown.
Ex5)
/** Precondition: ArrayList list contains Integer values sorted in increasing order.
* Postcondition: value inserted in its correct position in list.
*/
public static void insert(ArrayList<Integer> list, Integer value)
{
int index = 0;
//find insertion point
while (index < [Link]() && value > [Link](index) //unboxing
index++;
//insert value
[Link](index, value);
}
Note
Suppose value is larger than all the elements in list. Then the insert method will throw an IndexOutOfBoundsException if the first part of the test is omitted, that is,
index < [Link]().
Ex6)
/** Change every even-indexed element of strList to the empty string.
* Precondition: strList contains String values.
*/
public static void changeEvenToEmpty(ArrayList<String> strList)
{
boolean even = true;
int index = 0;
while (index < [Link]())
{
if (even)
[Link](index, "");
index++;
even = !even;
}
}
Note
Deleting elements during the traversal of an ArrayList requires special care to avoid skipping elements.
Ex7)
AP 페이지 9
Ex7)
/* Remove all occurrences of value from list. */
public static void removeAll(ArrayList<Integer> list, int value)
{
int index = 0;
while (index < [Link]())
{
if ([Link](index) == value)
[Link](index);
else
index++;
}
}
Note
1. Statement
[Link](index);
causes the elements to the right of the removed element to be shifted left to fill the "hole." In this case, if index is incremented, the current element will be skipped,
and if two consecutive elements are equal to value, one will be missed and (mistakenly) remain in the list.
2. Trying to add or delete an element during a traversal with an enhanced for loop may result in a ConcurrentModificationException being thrown. Therefore, if
you want to want to add or delete elements, don’t use an enhanced for loop to traverse the ArrayList.
Ex8)
ArrayList(Integer> list = new ArrayList<Integer>();
< code to initialize list >
for (Integer num : list)
{
if (num < 0)
[Link](0); //wrong
}
Note
This code segment throws a ConcurrentModificationException.
However, it is okay to use an enhanced for loop to modify objects that have a mutator method in their class definition.
Ex9) Considr a Clown class that has a changeAct method, and an ArrayList<Clown> that has been initialized with Clown objects. The following code is fine.
for (Clown c : clownList)
{
if ( <some condition on Clown c> )
[Link]();
}
Finding the Maximum and Minimum Value in ArrayList<Double>
Maximum
Minimum
AP 페이지 10
OR
Simultaneous Traversal of An ArrayList and An Array
In the traversal of a list, if it's important to keep track of indices (positions) in the list, you must use an index travers al. Sometimes an algorithm requries the
simultaneous traversal of an array and an ArrayList. Try your hand at writing code for the following problems.
Ex1) Consider an ArrayList<Integer> list, and an array arr of int that have both been initialized. A method getProductSum returns the sum of products of the
values of corresponding elements. Thus, prodArr[0] will be product of arr[0] and the first Integer value in list; prodArr[1] will be the product of arr[1] and the
second Integer value in list; and so on. The algorithm stops when the end of the shorter list is reached.
Here are some examples:
list arr getProductSum
[2, 1, 4] {5, 0, 3} 22
[1, 3, 5, 7, 9] {2, 4} 14
[7, 6, 5] {1, 2, 3, 4, 5} 34
[] {2, 3, 7} 0
The method getProductSum, whose header is given below, returns the sum of products as described above. Write code for the method.
public static int getProductSum(ArrayList<Integer> list, int[] arr)
Solution:
AP 페이지 11
Solution:
public static int gerProductSum(ArrayList<Integer> list, int[] arr)
{
int sum = 0;
int index = 0;
//Traverse both arr and list, until the end of
//one of the lists is reached.
while(index < [Link] && index <[Link]())
{
sum += arr[index] * [Link](index); //auto-boxing
}
return sum;
}
Note
Beware of going off the end of either list!
Ex2) Here is a trickier example.
Consider an ArrayList<Integer> list and an array arr of int that have both been initialized. An array called productArr is to be created that contains the products of
the values of corresponding elements. Thus, prodArr[0] will be the product of arr[0] and the first Integer value in list;prodArr[1] will be the prodcut of arr[1] and
the second Integer value in list;and so on. When the end of the shorter list is reached, the algorithm should copy the remaining elements of the longer list i nto
productArr.
Here are some examples:
list arr productArr
[2, 1, 4] {5, 0, 3} {10, 0, 12}
[1, 3, 5, 7, 9] {2, 4} {2, 12, 5, 7, 9}
[7, 6, 5] {1, 2, 3, 4, 5} {7, 12, 15, 4, 5}
[] {2, 3, 7} {2, 3, 7}
The method gerProducts, whose header is given below, returns an array of products as described above. Write code for the method.
public static int[] getProducts(ArrayList<integer> list, int[] arr)
Solution
public static int[] getProducts(ArrayList<integer> list, int[] arr)
{
int prodArrSize, smallerCount;
boolean arrayIsLonger;
//Determine length of prodArray.
if ([Link]() < [Link])
{
prodArrSize = [Link];
smallerCount = [Link]();
arrayIsLonger = true;
}
else
{
prodArrSize = [Link]();
smallerCount = [Link];
arrayIsLonger = false;
}
int[] prodArray = new int[prodArrSize];
//Place all products in prodArray.
for (int i = 0; i < smallerCount; i++)
prodArray[i] = arr[i] * [Link](i);
//How many elements must be transferred to prodArray?
int numExtra = [Link]([Link] - [Link]());
//Transfer those final elements to prodArray.
for (int i = 0; i <= numExtra - 1; i++)
{
if (arrayIsLonger)
prodArray[prodArrSize - numExtra + i] = arr[prodArrSize - numExtra + i];
else
prodArray[prodArrSize - numExtra + i] = [Link](prodArrSize - numExtra + i);
}
return prodArray;
}
Note
1. Use [Link] to get a positive value for the number of extra elements to be copied.
2. prodArray already has slots for the leftover elements that must be copied. But you must be careful in the indexes for these elements th at are taken from the end
of the longer list and placed in the end slots of the prodArray.
AP 페이지 12