Bài giảng Chapter 10 – Arrays and ArrayLists

Chapter 10 – Arrays and ArrayListsArray BasicsArray DeclarationArray CreationArray Element InitializationArray Default ValuesArray length PropertyPartially Filled ArraysCopying an ArraySearching an ArraySorting an ArraySelection Sort1Chapter 10 – Arrays and ArrayListsTwo-Dimensional ArraysArrays of ObjectsThe ArrayList ClassHow to Create an ArrayList ObjectAdding Elements to an ArrayList ObjectHow to Access an Element Within an ArrayListHow to Update an ArrayList ObjectAdditional ArrayList MethodsPrinting or Concatenating an ArrayListStoring Primitives in an ArrayListArrayList Example Using Anonymous Objects and the For-Each LoopArrayList Objects Versus Standard Arrays2Array BasicsA class stores a group of related data, and it stores the methods that operate on that data.An array is a limited version of a class.Like a class, an array also stores a group of related data, but an array does not store methods.Another difference between an array and a class is that an array's data must all be of the same type.Here's a picture of an array that holds a list of phone numbers. Each of the five boxes is called an array element and each box stores one phone number.phoneList81674120002024561111785296323280086753090035318842133first phone numberlast phone number3Array BasicsA class uses dot notation to access one of its members.On the other hand, an array uses square brackets around an index to access one of its elements.The rightmost column shows how to access each of the 5 elements in the phoneList array.Note that the index values start at 0 instead of 1 and the last index value is one less than the number of elements in the array.indexphoneListhow to access each element08167412000phoneList[0]12024561111phoneList[1]27852963232phoneList[2]38008675309phoneList[3]40035318842133phoneList[4]5 elements4Array BasicsHere's how you can change the first phone number to 2013434:phoneList[0] = 2013434;And here's how you can print the second phone number:System.out.println(phoneList[1]);5Array Basics/************************************************************** ContactList.java* Dean & Dean** This program creates a cell phone contacts phone number* list and prints the created list.*************************************************************/import java.util.Scanner;public class ContactList{ public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); long[] phoneList; // list of phone numbers int sizeOfList; // number of phone numbers long phoneNum; // an entered phone number System.out.print( "How many contact numbers would you like to enter? "); sizeOfList = stdIn.nextInt(); phoneList = new long[sizeOfList];6Array Basics for (int i=0; i[] ;Array declaration examples:int[] ids;double[] workHours;String[] names;9Array CreationIn Java, arrays are objects.As with all objects, arrays are created/instantiated with the new operator.Syntax for creating and assigning an array object: = new [];Example:long[] phoneList;phoneList = new long[10]; indicates the type of each element in the array indicates the number of elements in the arrayarray creation10Array CreationIt's legal to combine an array's declaration, creation, and assignment operations. Here's an example:long[] phoneList = new long[10];Provide a single statement that declares, creates, and assigns a 100-element array that stores book titles.11Array Element InitializationAn array initializer is a single statement made up of an array declaration, creation, and {} assignment.Array element initialization syntax:[] = {};Array element initialization example:String[] students = {"Hamoud", "Lee", "Brandon"};When an array initializer is used, the size of the array equals the number of elements in the initialization list.Note that with an array initializer, you create an array object without using the new operator.12Array Default ValuesAn array is an object and an array's elements are the instance variables for an array object. As such, an array's elements get default values when the array is instantiated, the same as any other instance variables get default values.Here are the default values for array elements (they're also the default values for instance variables and class variables):Array element's typeDefault valueinteger0floating point0.0booleanfalsereferencenullFor example, what are the default values below?float[] gpas = new float[1000];String[] states = new String[50];13Array length PropertySuppose you have a five-element colors array that's been initialized like this: String[] colors = {"blue", "gray", "lime", "teal", "yellow"};Here's how to print such an array:for (int i=0; i 16) { System.out.println("Invalid entry." + " Must enter between 1 and 16 characters."); }Array length property does not use ( )'s.String length method uses ( )'s.15Array length Property and Partially Filled Arrays else { phoneList[filledElements] = phoneNum; filledElements++; } System.out.print("Enter phone number (or q to quit): "); phoneNum = stdIn.nextLine(); } // end while System.out.println("\nContact List:"); for (int i=0; i increment i28Searching an arrayProblem description:Write a helper method named findStudent that searches for an id value within an array of student id's.The findStudent method should receive an id parameter and return the index value of id's location within a studentIds array instance variable.If id's value is not found, then return -1.As always, use appropriate access modifiers (public vs. private, class method vs. instance method).29Sorting an ArraySorting is a very common task in programming.Examples:Sort emails in an inbox – by date, by senderSort songs – by title, by author Sort student records – by student ID31There are many different sorting algorithms with varying degrees of complexity and efficiency. Since this is your first exposure to sorting, we'll cover a simple algorithm - the selection sort algorithm. Here it is:for (i0; i.length . And to loop through the elements within a particular row, use [0].length. For example:for (int i=0; i} // end class FlightTimes45Arrays of ObjectsSuppose you need to keep track of total sales for each sales clerk in a department store.In the following clerks array, each array element holds a reference for a SalesClerk object.Each SalesClerk object holds a sales clerk's name and a total-sales value for the sales clerk.If sales clerk Derrick sells two items for $55.45 and $22.01, then you'd like to store 77.46 for his total-sales value.clerksclerks[0]clerks[1]clerks[2]clerks[3]nullOybek, 6.25Chris, 58.12Derrick, 77.4647Arrays of ObjectsUsing the input shown below, how would the clerks array get filled?clerksnullnullnullnullinputfilledElementsOybek06.25Chris58.12Derrick40Oybek-6.25Chris12.8848Arrays of Objectsimport java.util.Scanner;public class SalesClerksDriver{ public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); SalesClerks clerks = new SalesClerks(2); String name; System.out.print("Enter clerk's name (q to quit): "); name = stdIn.nextLine(); while (!name.equals("q")) { System.out.print("Enter sale amount: "); clerks.addSale(name, stdIn.nextDouble()); stdIn.nextLine(); // flush newline System.out.print("Enter clerk's name (q to quit): "); name = stdIn.nextLine(); } // end while clerks.dumpData(); } // end main} // end SalesClerksDriver49Arrays of Objectsclass SalesClerks{ private SalesClerk[] clerks; // contains names and sales private int filledElements = 0; // number of elements filled //*********************************************************** public SalesClerks(int initialSize) { clerks = new SalesClerk[initialSize]; } // end SalesClerks constructor //*********************************************************** // Process a sale for the clerk whose name is passed in. // If the name is not already in the clerks array, // create a new object and insert a reference to it in the // next array element, doubling array length if necessary. public void addSale(String name, double amount) { int clerkIndex = findClerk(name); if (clerkIndex == -1) // add a new clerk { if (filledElements == clerks.length) { doubleLength(); }50Arrays of Objects clerkIndex = filledElements; clerks[clerkIndex] = new SalesClerk(name); filledElements++; } // end if clerks[clerkIndex].adjustSales(amount); } // end addSale //********************************************************** // Print all the data - sales clerk names and sales. public void dumpData() { for (int i=0; i reference-variable = new ArrayList();For example, here's how to initialize an ArrayList reference variable named students:ArrayList students = new ArrayList();Compare the above ArrayList example to this corresponding standard-array example:Student[] students = new Student[100];56How to Create an ArrayList ObjectWhat are the syntax differences between the ArrayList example and the standard-array example? With the ArrayList example:Use angled brackets to specify the type for the elements. must be a class name (not a primitive).Do not specify the number of elements (because ArrayList objects start out with no elements).57Adding Elements to an ArrayList ObjectTo add an element to the end of an ArrayList object, use this syntax:ArrayList-reference-variable.add(item);The item that's added must be the same type as the type specified in the ArrayList's declaration.Write a code fragment that creates this ArrayList object:computerScientists0"Ada Lovelace"1"Grace Hopper"2"Carol Bartz"58Java APIAPI stands for application programming interface.The Java API is the interface to the huge library of pre-built Java classes.As a programmer, you don't need to know the internals of those classes; you just need to know how to use them. Or said another way, you just need to know how to interface with them.To interface with them, you need to use their public methods.To use a method, you need to know what type of argument(s) to pass to it and what type of value it returns. A method's API shows the method's parameters and its return type.The standard way to show that information is to show the method's heading. For example, here's the API heading for the Math class's pow method:public static double pow(double num, double power)59How to Access an Element Within an ArrayListWith standard arrays, you use square brackets to access and update an element. ArrayList objects don't use square brackets. Instead, they use a get method to access an element and a set method to update an element.Here's the API heading for the ArrayList's get method:public E get(int index)Semantics:The index parameter specifies the position of the desired element within the ArrayList calling object. As with standard arrays, the first element is at position 0, the second element is at position 1, etc.If index refers to a nonexistent element, then a runtime error occurs.If index is valid, then get returns the element at the specified position.60How to Access an Element Within an ArrayListNote the E return type for the ArrayList's get method:public E get(int index)The E stands for element. It represents the data type of the ArrayList's elements. It's the same as the element-type specified in the ArrayList's initialization:ArrayList reference-variable = new ArrayList();61How to Update an ArrayList ObjectThe set method allows you to assign a value to an existing ArrayList element. Here's its API heading:public E set(int index, E elem)Semantics:The index parameter specifies the position of the element you're interested in.If index refers to a nonexistent element, then a runtime error occurs.If index is valid, then set assigns the elem parameter to the specified element, overlaying whatever was there originally.E represents the data type of the ArrayList's elements. 62How to Update an ArrayList ObjectDraw a picture of the colors ArrayList after this code fragment executes:String mixedColor;ArrayList colors = new ArrayList();colors.add("red");colors.add("green");colors.add("blue");mixedColor = colors.get(0) + colors.get(1);colors.set(2, mixedColor);63Additional ArrayList Methodspublic void add(int index, E elem)Starting with the specified index position, shift the original elements to higher-indexed positions. Then insert the elem parameter at the specified index position.public void clear()Remove all elements from the list.public int indexOf(Object elem)Search for the first occurrence of the elem parameter within the list. If it's found, return its index position. If it's not found, return -1.public boolean isEmpty()Return true if the list contains no elements.public E remove(int index)Remove the element at the specified index position, shift all higher-indexed elements to lower-indexed positions, and return the removed element.public int size()Return the number of elements in the list.Object is a generic class that can be used as a class type for any object.64Example ArrayList Programimport java.util.ArrayList;public class Survivor{ public static void main(String[] args) { int loserIndex; // index of person who gets kicked out String loser; // person who gets kicked out ArrayList tribe = new ArrayList(); tribe.add("Richard"); tribe.add("Jerri"); tribe.add("Colby"); tribe.add("Amber"); tribe.add("Rupert"); loserIndex = (int) (Math.random() * 5); loser = tribe.remove(loserIndex); System.out.println("Sorry, " + loser + ". The tribe has spoken. You must leave immediately."); System.out.println("Remaining: " + tribe); } // end main} // end Survivor66Printing or Concatenating an ArrayListIf you attempt to print or concatenate an ArrayList, the ArrayList returns a comma-separated list of ArrayList elements surrounded by square brackets, [].For example, in the Survivor program, if Colby is removed, the last line prints this:Remaining: [Richard, Jerri, Amber, Rupert]67Storing Primitives in an ArrayListAs mentioned previously, ArrayLists store references. For example, in the Survivor program, tribe is an ArrayList of strings, and strings are reference types.If you need to store primitives in an ArrayList, you can't do it directly, but you can do it if the primitives are wrapped up in wrapper classes.Ever since Java 5.0, the "wrapping up" process has been done behind the scenes. For ArrayLists, it's done automatically if a wrapper class is used in an ArrayList declaration.The StockAverage program on the next slide reads int stock values and stores them in an ArrayList. After all stock values are entered, the program calculates the average stock value.Why is an ArrayList appropriate for calculating a stock average?68Storing Primitives in an ArrayListimport java.util.Scanner;import java.util.ArrayList;public class StockAverage{ public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); ArrayList stocks = new ArrayList(); double stock; // a stock value double stockSum = 0; // sum of stock values System.out.print("Enter a stock value (-1 to quit): "); stock = stdIn.nextDouble(); while (stock >= 0) { stocks.add(stock); System.out.print("Enter a stock value (-1 to quit): "); stock = stdIn.nextDouble(); } // end whileMust be a wrapper class, not a primitive.Automatic boxing (“autoboxing”) takes place here.69Storing Primitives in an ArrayList for (int i=0; i bears = new ArrayList(); //********************************************************** // Fill store with specified number of standard teddy bears. public void addStdBears(int num) { for (int i=0; i : )Read this as "for each bear in bears, "For each iteration through the loop, bear accesses the next element in the bears ArrayList.77For-Each LoopNote that using the for-each loop is an option, not a requirement. Here's an alternative displayInventory implementation that uses a standard for loop:public void displayInventory(){ for (int i=0; i<bears.size(); i++) { bears.get(i).display(); }} // end displayInventoryThe for-each loop implementation is preferred because it is simpler.78For-Each LoopBe aware that you can use for-each loops for more than just ArrayLists. You can also use them with standard arrays.Here's a for-each loop example that prints the numbers in a primes array:int[] primes = {2, 3, 5, 7, 11, 13};for (int p : primes){ System.out.println(p);}79For-Each LoopThe for-each loop can be used only with things that have elements - Java API collections and arrays. (The ArrayList is a Java API collection. To learn about Java’s other collections, go to LoopBe aware of several issues when using a for-each loop:It's new with Java 5.0, so it won't work with older compilers.The for-each loop doesn't use an index variable to loop through its elements. That can be a benefit in that it leads to less cluttered code. But it's a drawback if there's a need for an index within the loop.For example, given the primes array in the earlier slide, which type of loop (standard or for-each) should you use to print the following?primes[0] = 2primes[1] = 3...primes[5] = 13As a practice exercise, provide a standard for loop that prints the above and also provide a for-each loop that prints the above.81ArrayList Objects Versus Standard ArraysBenefits of an ArrayList Over a Standard ArrayBenefits of a Standard Array Over an ArrayListIt's easy to increase the size of an ArrayList – just call add.A standard array uses []'s to access array elements (which is easier than using get and set methods).It's easy for a programmer to insert or remove an element to or from the interior of an ArrayList – just call add or remove and specify the element's index position. A standard array is more efficient with storing primitive values.82