Holding Your Objects

• In general, your programs will always be creating new objects based on some criteria that will be known only at run time.
• You can’t rely on creating a named reference to hold each one of your objects.
• The compiler-supported type is the array. if you want to hold a group of primitives.
• The fixed-sized constraint of an array is too limiting.
• Containers(collection classes) provide sophisticated ways to hold your objects, and you can solve a surprising number of problems by using these tools.
• Java container classes will automatically resize themselves.
• You don’t need to worry about how big to make the container while you’re writing the program.

Generics and type-safe containers

• With generics, you’re prevented, at compile time, from putting the wrong type of object into a container.
• With generics you not only know that the compiler will check the type of object that you put into a container, but you also get cleaner syntax when using the objects in the container.
• Upcasting works the same with generics as it does with other types.

Basic concepts

• The only place where you’ll specify the precise type you’re using is at the point of creation.
• The intent of using the interface is that if you decide you want to change your implementation, all you need to do is change it at the point of creation.
• This approach won’t always work, because some classes have additional functionality.

Adding groups of elements

• Collections.addAll( ) runs much faster, and it’s just as easy to construct the Collection with no elements and then call Collections.addAll( ), so this is the preferred approach.
• A limitation of Arrays.asList( ) is that it takes a best guess about the resulting type of the List, and doesn’t pay attention to what you’re assigning it to.
• explicit type argument specification——it’s possible to insert a "hint" in the middle of Arrays.asList( ), to tell the compiler what the actual target type should be for the resulting List type produced by Arrays.asList( ).

Printing containers

• Two primary categories in the Java container library. The distinction is based on the number of items that are held in each "slot" in the container.
  
• The Collection category only holds one item in each slot. A Map holds two objects, a key and an associated value, in each slot.
• A LinkedList contains more operations than an ArrayList.
• A Set will only hold one of each identical item, the different Set implementations store the elements differently.
• A Map only accepts one of each key.
• You don’t have to specify (or think about) the size of the Map because it resizes itself automatically.
• The HashMap implementation uses a very fast algorithm that controls the order.

List

• The List interface adds a number of methods to Collection that allow insertion and removal of elements in the middle of a List.
• That’s its fundamental value: a modifiable sequence.
• If you want to remove an object, you can pass that object’s reference to the remove( ) method.
• It’s important to be aware that List behavior changes depending on equals( ) behavior.
• For a LinkedList, insertion and removal in the middle of a list is a cheap operation (except for, in this case, the actual random access into the middle of the list), but for an ArrayList it is an expensive operation.
• Optimization is a tricky issue, and the best policy is to leave it alone until you discover you need to worry about it.
• It’s also interesting to note that order is unimportant for** subList( )** method.
• subList( ) produces a list backed by the original list. Therefore, changes in the returned list are reflected in the original list, and vice versa.
  
• You don’t have to worry about equals( ) behavior when using indexes.

Iterator

• In a List, add( ) is one way to insert elements, and get( ) is one way to fetch elements.
• You need to program to the exact type of the container in order to use it.
• You’d like to write, from the beginning, a piece of general-purpose code that doesn’t know or care what type of container it’s working with, so that it can be used on different types of containers without rewriting that code.
• An iterator is an object whose job is to move through a sequence and select each object in that sequence without the client programmer knowing or caring about the underlying structure of that sequence.
• With an Iterator, you don’t need to worry about the number of elements in the container.
• An Iterator will also remove the last element produced by next( ), which means you must call next( ) before you call remove( ).
• The true power of the Iterator: the ability to separate the operation of traversing a sequence from the underlying structure of that sequence.

ListIterator

• The ListIterator is a more powerful subtype of Iterator that is produced only by List classes.
• ListIterator is bidirectional.

LinkedList

• The LinkedList performs certain operations (insertion and removal in the middle of the List) more efficiently than does ArrayList. Conversely, it is less efficient for random-access operations.
• LinkedList also adds methods that allow it to be used as a stack, a Queue or a double-ended queue (deque).
• The element( ), offer( ), peek( ), poll( ) and remove( ) methods that were added to LinkedList in order that it could be a Queue implementation.

Stack

• LinkedList has methods that directly implement stack functionality.
• There is no common Stack interface in java.util.
• Even though java.util.Stack exists, LinkedList produces a better Stack.

Set

• A Set refuses to hold more than one instance of each object value.
• The most common use for a Set is to test for membership.
• A HashSet implementation is optimized for rapid lookup.
• Set has the same interface as Collection, so there isn’t any extra functionality like there is in the two different types of List.
• A Set determines membership based on the "value" of an object.
• TreeSet keeps elements sorted into a red-black tree data structure, whereas HashSet uses the hashing function. LinkedHashSet also uses hashing for lookup speed, but appears to maintain elements in insertion order using a linked list.

Map

• You can’t use primitives with containers.
• Maps, like arrays and Collections, can easily be expanded to multiple dimensions.
• Thus, it’s quite easy to combine containers to quickly produce powerful data structures.

Queue

• Queues are commonly used as a way to reliably transfer objects from one area of a program to another.
• Queues are especially important in concurrent programming, because they safely transfer objects from one task to another.
• LinkedList has methods to support queue behavior and it implements the Queue interface, so a LinkedList can be used as a Queue implementation.
• The Queue interface narrows access to the methods of LinkedList so that only the appropriate methods are available, and you are thus less tempted to use LinkedList methods.
• You can have a usable Queue without any of the methods that are in Collection, from which it is inherited.

PriorityQueue

• First-in, first-out says that the next element should be the one that was waiting the longest.
• A priority queue says that the element that goes next is the one with the greatest need (the highest priority).
• If you build a messaging system, some messages will be more important than others, and should be dealt with sooner, regardless of when they arrive.
• When you offer( ) an object onto a PriorityQueue, that object is sorted into the queue.
• The PriorityQueue ensures that when you call peek( ), poll( ) or remove( ), the element you get will be the one with the highest priority.
• If you want you use your own class in a PriorityQueue, you must include additional functionality to produce natural ordering, or provide your own Comparator.

Collection vs. Iterator

• In Java, it might seem sensible to follow the C++ approach, and to express commonality between containers using an iterator rather than a Collection.
• Implementing Collection also means providing an iterator( ) method.
• The use of Iterator becomes compelling when you implement a foreign class, one that is not a Collection, in which it would be difficult or annoying to make it implement the Collection interface.
• Producing an Iterator is the least-coupled way of connecting a sequence to a method that consumes that sequence, and puts far fewer constraints on the sequence class than does implementing Collection.

Foreach and iterators

• Working with foreach is a characteristic of all Collection objects.
• The Iterable interface is what foreach uses to move through a sequence.
• A foreach statement works with an array or anything Iterable, but that doesn’t mean that an array is automatically an Iterable, nor is there any autoboxing that takes place.

The Adapter Method idiom

• What if you have an existing class that is Iterable, and you’d like to add one or more new ways to use this class in a foreach statement?
• One solution is what I call the Adapter Method idiom.
• When you have one interface and you need another one, writing an adapter solves the problem.
• It’s important to be aware that Arrays.asList( ) produces a List object that uses the underlying array as its physical implementation.
• If you do anything to that List that modifies it, and you don’t want the original array modified, you should make a copy into another container.