Introduction to Java Arrays and Array ListsArrays • An array is an indexed list of values • Any type int, double, String, boolean, … • All values in an array must have same typeArrays • Example: int [] • The index starts at zero and ends at length-1 7 6521100 1 2 3 4 n-1Arrays • An array is defined using Type[] • Example: int[] values = new int[10]; values[0] = 7; values[1] = 10; ……. values[9] = 6; values[10] = 6; //WrongArrays • You can initialize an array when declaring the array • int[] values = {7, 10, 1, 2, 5}; • Access array elements using [ ] operator • values[3] = ? • int x = values[5] + 1; = ?Array • Each array has a length • int[] values = {7, 10, 1, 2, 5}; • int valuesize = values.length; //5Array • Two Dimensional Arrays • int[][] table = new int[3][3]; • int[][] table = { {1, 2, 3}, {6, 7, 8}, {4, 5, 6} };Array Lists • An array list manages a sequence of objects or values • Two conveniences: – Array lists can grow and shrink dynamically as needed – Array lists offer method for many common tasks, such as inserting, removing elementsArray Lists • Creates an array list • ArrayList grades = new ArrayList<Integer>(); • ArrayList names = new ArrayList<String>(); • ArrayList uscstudents = new ArrayList<Student>();Array Lists • boolean add (Object obj) – Appends the obj to the end of the list • Object remove (int index) – Removes the element at index from the list • Object get (int index) – Returns the object at index of the list • int size () – Returns the number of elements in the listArray Lists • boolean isEmpty () – Returns true if the list has no elements • void clear () – Removes all elements of the list • boolean add (int index, Object obj) – Insert the object into the location of given indexArray Lists • boolean add (Object obj) • Examples: grades.add(100); grades.add(85); grades.add(80); grades.add(82); 100808510085100828085100Array Lists • Object remove (int index) • Examples: int pos = 2; grades.remove(pos); 8280851008285100 8280100Array Lists • Determine the number of elements • Array a.length • String a.length() • Array List a.size()Array Algorithms • Counting matches • Find a Value • Maximum or Minimum • Sort elements • Inverse the arrayArray Algorithms • Counting MatchesArray Algorithms • Find a matchArray Algorithms • Maximum or MinimumArray Algorithms • Sort Elements • Popular algorithms – Insertion sort – Selection sort – Bubble sort – Quick sort – Merge sortChecking Problem • Write an efficient method to find the maximum nonrepeated grade in an array of grades. The grades in array are integers from 0 to 100. • For example, if the array is {100, 90, 90, 80, 100, 60}, the return value is 80.Checking Problem • Algorithm 1 – Sort the grades – Find the maximum grade appearing once • Time Complexity – O(nlogn) + O(n) => O(nlogn) • Find an algorithm with a time complexity O(n)Any
View Full Document