Java Programming I on YouTube:
https://www.youtube.com/playlist?list=PLLIqcoGpl73iaXAtS_-V_Xdx3mhTzPwb5
Both can store multiple occurrences of objects.
Some collection types (such as ArrayList) use arrays internally to store data.
An array is a Java language feature. Collections are classes in the Java API.
Collection classes have methods that perform operations that arrays don't provide.
Arrays are fixed in size. Collections are variable in size.
Arrays can store primitive types. Collections can't.
Indexes are almost always required to process arrays. Collections are processed without using indexes. Rather, collections provide methods such as
get(index) // returns stored value
set(index, object) // updates stored value
String[] codes = new String[3]; codes[0] = "mcb2"; codes[1] = "java"; codes[2] = "jsps"; for (String s : codes) System.out.println(s);
ArrayList<String> codes = new ArrayList<String>(); codes.add("mcb2"); codes.add("java"); codes.add("jsps"); for (String s : codes) System.out.println(s);
A collections framework is a unified architecture for representing and manipulating collections:
Note: shaded boxes at the top are abstract interfaces, the rest are concrete classes.
Collection Interfaces are abstract data types that represent collections.
Collection // supports conversion between different collection types and arrays Set // a collection that cannot contain duplicate elements List // a sequence of elements Queue // a collection of multiple elements held prior to processing Map // a collection of mappings that map keys to values SortedSet // a set that maintains its elements in ascending order SortedMap // a set that maintains its mappings in ascending order
Interfaces allow collections to be manipulated independently of the details of their representation (implementation).
In object-oriented languages, interfaces generally form a hierarchy.
The following loop is commonly referred to as Java for-each construct:
for (Object obj : collection) { System.out.println(obj); }
An Iterator is an object that enables you to
traverse through a collection, and
remove elements from the collection
To get an Iterator for a collection, call its iterator method. For example,
for ( Iterator<Integer> it = c.iterator(); it.hasNext(); ) { if (!cond(it.next())) { it.remove(); } }
public interface Iterator<E> { boolean hasNext(); // returns true if the iteration has more elements E next(); // returns the next element in the iteration void remove(); // removes the last element that was returned by next() }
Why use iterators instead of the for-each construct?
To remove selective elements during iteration. The for-each construct hides the iterator, so you cannot remove elements.
Iterate over multiple collections in parallel.
Collection classes are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.
ArrayList
LinkedList
HashSet
HashMap
TreeMap
CollectionClass<ElementType> collectionName = new CollectionClass<ElementType>();
Note that
CollectionClass<ElementType>
syntax specifies that the interface is generic.
Generic interface requires that the type of object contained in the collection (the element type) is specified when the CollectionClass is instantiated.
In other words, the type of the element of the container becomes known to the compiler, making your program much safer.
For example,
List<String> list = new ArrayList<String>(); list.add("hello"); String s = list.get(0);
/** * Generic version of the Box class. * @param <T> the type of the value being boxed */ public class Box<T> { // T stands for "Type" private T t; public void set(T t) { this.t = t; } public T get() { return t; } } // To instantiate the object, use Box<Integer> integerBox; integerBox = new Box<Integer>(); // In Java SE 7 and later: Box<Integer> integerBox = new Box<>();
In the last line of code the pair of angle brackets <> is informally called the diamond. It is based on Java type inference -- the ability of compiler to determine the type by default (the Integer in our example.)
Note that this example is from
http://docs.oracle.com/javase/tutorial/java/generics/types.html
Java Generic Types
tutorial online. It is highly recommended that you follow this tutorial through to get up to speed with Java Generics.
ArrayList<String> codes = new ArrayList<String>();
ArrayList<Integer> numbers = new ArrayList<Integer>();
LinkedList<Product> products; products = new LinkedList<Product>();
CollectionClass<ElementType> collectionName = new CollectionClass<>();
Note that modern Java documentation typically uses E for element types:
CollectionClass<E> collectionName = new CollectionClass<>();
ArrayList<String> codes = new ArrayList<>();
public class ClassName<TypeVariable [,TypeVariable]...>{}
public class GenericQueue<E>{}
java.util.ArrayList
ArrayList<E>() ArrayList<E>(intCapacity) ArrayList<E>(Collection)
|
|
// create an array list of type String ArrayList<String> codes = new ArrayList<>(); // add three strings codes.add( "mbdk" ); codes.add( "citr" ); codes.add( 0, "warp" ); // print the array list for ( int idx = 0; idx < codes.size(); ++idx ) { String code = codes.get( idx ); System.out.println( code ); }
Resulting output
warp mbdk citr
System.out.println(codes);
Resulting output
[warp, mbdk, citr]
codes.set(1, "wuth"); codes.remove("warp"); codes.remove(1); System.out.print(codes);
Resulting output
[wuth]
ArrayList<Integer> numbers = new ArrayList<>(); numbers.add(1); numbers.add(2); numbers.add(3); System.out.println(numbers);
Resulting output
[1, 2, 3]
List is a set of values of the same type. Basic operations performed on a list are:
Search list for given item
Sort list
Insert item in list
Delete item from list
java.util.LinkedList
LinkedList<E>()
|
|
|
// create a linked list of type String LinkedList<String> codes = new LinkedList<>(); // add three strings codes.add("mbdk"); codes.add("citr"); codes.add(0, "warp"); System.out.println(codes);
Resulting output
[warp, mbdk, citr]
codes.addFirst("wuth"); codes.addLast("wooz"); System.out.println(codes);
Resulting output
[wuth, warp, mbdk, citr, wooz]
for (String s : codes) System.out.println(s);
Resulting output
wuth warp mbdk citr wooz
String firstString = codes.removeFirst(); String lastString = codes.removeLast(); System.out.println(firstString); System.out.println(lastString); System.out.println(codes);
Resulting output
wuth wooz [warp, mbdk, citr]
Necessary components to search a list:
Array or Collection containing the list
Length of the list
Item for which you are searching
If search item is always at the end of the list, it will take many comparisons to find.
If search item is not in the list, then we will compare the item with every element in the list.
A sequential search is therefore not efficient for large lists; in fact, it can be proved that, on average, the number of comparisons made by a sequential search is equal to half the size of the list.
List is sorted by selecting list element and moving it to its proper position
Algorithm finds position of smallest element and moves it to top of unsorted portion of list
Repeats process above until entire list is sorted
public static void selectionSort(int[] list, int listLength) { int index; int smallestIndex; int minIndex; int temp; for (index = 0; index < listLength – 1; index++) { smallestIndex = index; for (minIndex = index + 1; minIndex < listLength; minIndex++) if (list[minIndex] < list[smallestIndex]) smallestIndex = minIndex; temp = list[smallestIndex]; list[smallestIndex] = list[index]; list[index] = temp; } }
It is known that for a list of length n, selection sort makes exactly
n(n – 1) / 2
key comparisons and exactly
3(n – 1)
item assignments.
Therefore, if n = 1000, then to sort the list, selection sort makes 500,000 key comparisons and about 3000 item assignments.
The insertion sort algorithm sorts the list by moving each element to its proper place
public static void insertionSort(int[] list, int listLength) { int firstOutOfOrder, location; int temp; for (firstOutOfOrder = 1; firstOutOfOrder < listLength; firstOutOfOrder++) { if (list[firstOutOfOrder] < list[firstOutOfOrder - 1]) { // list[firstOutOfOrder] is indeed out of order! temp = list[firstOutOfOrder]; location = firstOutOfOrder; do { list[location] = list[location - 1]; // shift previous down location--; } while (location > 0 && list[location - 1] > temp); list[location] = temp; } } } //end insertionSort
It is known that for a list of length n, on average, the insertion sort makes
(n2 + 3n – 4) / 4
key comparisons and about
n(n – 1) / 4
item assignments.
Therefore, if
n = 1000,
then to sort the list, the insertion sort makes about 250,000 key comparisons and about 250,000 item assignments.
Search item is compared with middle element of list
If search item < middle element of list, search is restricted to first half of the list
If search item > middle element of list, search second half of the list
If search item = middle element, search is complete
Determine whether 75 is in the list
public static int binarySearch(int[] list, int listLength, int searchItem) { int first = 0; int last = listLength - 1; int mid = 0; boolean found = false; while (first <= last && !found) { mid = (first + last) / 2; if (list[mid] == searchItem) { found = true; } else if (list[mid] > searchItem) { last = mid - 1; } else { first = mid + 1; } } if (found) { return mid; } else { return -1; } } //end binarySearch
In general, if list is a sorted list of size n, to determine whether an element is present in the list, the binary search makes at most
2log2n + 2
key (item) comparisons
push(element) pull() size()
import java.util.LinkedList; public class GenericQueue<E> { private LinkedList<E> list = new LinkedList<>(); public void push(E item) { list.addLast(item); } public E pull() { return list.removeFirst(); } public int size() { return list.size(); } }
GenericQueue<String> q1 = new GenericQueue<>(); q1.push("Item One"); q1.push("Item Two"); q1.push("Item Three"); System.out.println( "The queue contains " + q1.size() + " items"); while (q1.size() > 0) System.out.println(ql.pull()); System.out.println( "The queue now contains " + ql.size() + " items");
Resulting output
The queue contains 3 items Item One Item Two Item Three The queue now contains 0 items
java.util.HashMap java.util.TreeMap
Common constructors of the HashMap and TreeMap classes:
HashMap<K,V>() TreeMap<K,V>()
clear()
containsKey(key)
containsValue(value)
entrySet()
get(key)
put(key, value)
remove(key)
size()
Common methods of the Map.Entry interface
getKey() getValue()
// create an empty hash map HashMap<String,String> books = new HashMap<>(); // add three entries books.put("wooz", "Wizard of Oz"); books.put("mbdk", "Moby Dick"); books.put("wuth", "Wuthering Heights"); // print the entries for (Map.Entry book : books.entrySet()) System.out.println(book.getKey() + ": " + book.getValue()); // print the entry whose key is "mbdk" System.out.println("\nCode mbdk is " + books.get("mbdk"));
Resulting output for code that uses a hash map
wuth: Wuthering Heights mbdk: Moby Dick wooz: Wizard of Oz Code mbdk is Moby Dick
// create an empty tree map TreeMap<String,String> books = new TreeMap<>(); // add three entries books.put("wooz", "Wizard of Oz"); books.put("mbdk", "Moby Dick"); books.put("wuth", "Wuthering Heights"); // print the entries for (Map.Entry book : books.entrySet()) System.out.println(book.getKey() + ": " + book.getValue()); // print the entry whose key is "mbdk" System.out.println("\nCode mbdk is " + books.get("mbdk"));
Resulting output for code that uses a tree map
mbdk: Moby Dick wooz: Wizard of Oz wuth: Wuthering Heights Code mbdk is Moby Dick
These are obsolete (but not deprecated) Java collections, part of the original java.util. They synchronize each individual operation in a multithreaded program -- not what you want. (Generally, you want to synchronize a certain sequence of statements as opposed to a single statement.) The functionality of legacy collection classes is retrofitted into the latest Java API in a way that is best suitable for potentially thread-unsafe legacy code.
Vector // contains legacy methods no longer part of the collections framework // Vector is synchronized // For an alternative, see Collections.synchronizedList HashTable // similar to HashMap, but is synchronized Stack // subclass of Vector that implements a stack
Advice: do not use these legacy classes in your code! Instead,
ArrayList is the replacement of Vector
HashMap is the replacement of HashTable
Deque and ArrayDeque are replacements of Stack
// create a vector Vector codes = new Vector(); // add three strings codes.add("mbdk"); codes.add("citr"); codes.add(0, "warp"); // print the vector for (int i =0; i < codes.size(); i++) { String code = (String)codes.get(i); System.out.println(code); }
Resulting output
warp mbdk citr
// create an untyped array list ArrayList products = new ArrayList(); // add three productss products.add(new Product("dctp", "Duct Tape", 4.95)); products.add(new Product("blwr", "Bailing Wire", 14.95)); products.add(new Product("cgum", "Chewing Gum", 0.95)); // print the array list for (int i = 0; i < products.size(); i++) { Product p = (Product)products.get(i); System.out.println(p.getCode() + "\t" + p.getDescription() + "\t" + p.getFormattedPrice()); }
The compiler warning generated by the code:
Note: C:\murach\java\ch12_tester\src\Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Resulting output
dctp Duct Tape $4.95 blwr Bailing Wire $14.95 cgum Chewing Gum $0.95
Primitive Type Wrapper Class ---------------- --------------- byte Byte short Short int Integer long Long float Float double Double char Char boolean Boolean