Collections & Generics

Collections 
  • Common collection activities include adding objects, removing objects, verifying object inclusion, retrieving objects, and iterating.
  • Three meanings for "collection":
  • collection Represents the data structure in which objects are stored
  • Collection java.util interface from which Set and List extend
  • Collections A class that holds static collection utility methods
  • Four basic flavors of collections include Lists, Sets, Maps, Queues:
  • Lists of things Ordered, duplicates allowed, with an index.
  • Sets of things May or may not be ordered and/or sorted; duplicates not allowed.
  • Maps of things with keys May or may not be ordered and/or sorted; duplicate keys are not allowed.
  • Queues of things to process Ordered by FIFO or by priority.
  • Four basic sub-flavors of collections Sorted, Unsorted, Ordered, Unordered.
  • Ordered Iterating through a collection in a specific, non-random order.
  • Sorted Iterating through a collection in a sorted order.
  • Sorting can be alphabetic, numeric, or programmer-defined.

Key Attributes of Common Collection Classes
  • ArrayList: Fast iteration and fast random access.
  • Vector: It's like a slower ArrayList, but it has synchronized methods.
  • LinkedList: Good for adding elements to the ends, i.e., stacks and queues.
  • HashSet: Fast access, assures no duplicates, provides no ordering.
  • LinkedHashSet: No duplicates; iterates by insertion order.
  • TreeSet: No duplicates; iterates in sorted order.
  • HashMap: Fastest updates (key/values); allows one null key, many null values.
  • Hashtable: Like a slower HashMap (as with Vector, due to its synchronized methods). No null values or null keys allowed.
  • LinkedHashMap: Faster iterations; iterates by insertion order or last accessed; allows one null key, many null values.
  • TreeMap: A sorted map.
  • PriorityQueue: A to-do list ordered by the elements' priority.

Using Collection Classes
  • Collections hold only Objects, but primitives can be autoboxed.
  • Iterate with the enhanced for, or with an Iterator via hasNext() & next().
  • hasNext() determines if more elements exist; the Iterator does NOT move.
  • next() returns the next element AND moves the Iterator forward.
  • To work correctly, a Map's keys must override equals() and hashCode().
  • Queues use offer() to add an element, poll() to remove the head of the queue, and peek() to look at the head of a queue.
  • As of Java 6 TreeSets and TreeMaps have new navigation methods like floor() and higher().
  • You can create/extend "backed" sub-copies of TreeSets and TreeMaps.

Sorting and Searching Arrays and Lists

  • Sorting can be in natural order, or via a Comparable or many Comparators.
  • Implement Comparable using compareTo(); provides only one sort order.
  • Create many Comparators to sort a class many ways; implement compare().
  • To be sorted and searched, a List's elements must be comparable.
  • To be searched, an array or List must first be sorted.

Utility Classes: Collections and Arrays 

  • Both of these java.util classes provide
  • A sort() method. Sort using a Comparator or sort using natural order.
  • A binarySearch() method. Search a pre-sorted array or List.
  • Arrays.asList() creates a List from an array and links them together.
  • Collections.reverse() reverses the order of elements in a List.
  • Collections.reverseOrder() returns a Comparator that sorts in reverse.
  • Lists and Sets have a toArray() method to create arrays.
Generics 
  • Generics let you enforce compile-time type safety on Collections (or other classes and methods declared using generic type parameters).
  • An ArrayList<Animal> can accept references of type Dog, Cat, or any other subtype of Animal (subclass, or if Animal is an interface, implementation).
  • When using generic collections, a cast is not needed to get (declared type) elements out of the collection. With non-generic collections, a cast is required: List<String> gList = new ArrayList<String>(); 
            List list = new ArrayList();
           // more code
           String s = gList.get(0); // no cast needed
           String s = (String)list.get(0); // cast required
  • You can pass a generic collection into a method that takes a non-generic collection, but the results may be disastrous. The compiler can't stop the method from inserting the wrong type into the previously type safe collection.
  • If the compiler can recognize that non-type-safe code is potentially endangering something you originally declared as type-safe, you will get a compiler warning. For instance, if you pass a List<String> into a method declared as
  • void foo(List aList) { aList.add(anInteger); }
  • You'll get a warning because add() is potentially "unsafe".

  • "Compiles without error" is not the same as "compiles without warnings." A compilation warning is not considered a compilation error or failure.
  • Generic type information does not exist at runtime—it is for compile-time safety only. Mixing generics with legacy code can create compiled code that may throw an exception at runtime.
  • Polymorphic assignments applies only to the base type, not the generic type parameter. You can say
           List<Animal> aList = new ArrayList<Animal>(); // yes
          You can't say
           List<Animal> aList = new ArrayList<Dog>();


  • The polymorphic assignment rule applies everywhere an assignment can be made. The following are NOT allowed: 
  • void foo(List<Animal> aList) { } // cannot take a List<Dog>
  • List<Animal> bar() { } // cannot return a List<Dog>

  • Wildcard syntax allows a generic method, accept subtypes (or supertypes) of the declared type of the method argument:
  • void addD(List<Dog> d) {} // can take only <Dog>
  • void addD(List<? extends Dog>) {} // take a <Dog> or <Beagle>

  • The wildcard keyword extends is used to mean either "extends" or "implements."
  • So in <? extends Dog>, Dog can be a class or an interface.

  • When using a wildcard, List<? extends Dog>, the collection can be accessed but not modified.
  • When using a wildcard, List<?>, any generic type can be assigned to the reference, but for access only, no modifications.

  • List<Object> refers only to a List<Object>, while List<?> or
  • List<? extends Object> can hold any type of object, but for access only.
  • Declaration conventions for generics use T for type and E for element: public interface List<E> // API declaration for List
  • boolean add(E o) // List.add() declaration
  • The generics type identifier can be used in class, method, and variable declarations:
  • class Foo<t> { } // a class
  • T anInstance; // an instance variable
  • Foo(T aRef) {} // a constructor argument
  • void bar(T aRef) {} // a method argument
  • T baz() {} // a return type
  • The compiler will substitute the actual type.

  • You can use more than one parameterized type in a declaration:
  • public class UseTwo<T, X> { }

  • You can declare a generic method using a type not defined in the class:
  • public <T> void makeList(T t) { } is NOT using T as the return type. This method has a void return type, but to use T within the method's argument you must declare the <T>, which happens before the return type.

No comments:

Post a Comment