- [Jeremy] Okay welcome back. In this lecture we'll explore the concept of collections and how to work with them within java. In particular, we'll review the following topics. We'll provide an overview of the Collection API, we'll review the different collection implementations, we'll explore how generics are used with collections, and we'll examine the concept of iterators for working with collections. At the conclusion of this lecture, you should be able to perform each of the items listed above. Take a moment to rate yourself on each of these items on a scale of one through to five. At the conclusion of this lecture, these objectives will be reviewed. You should write yourself again to see how much benefit you have received from this lecture. Even without collections we can still work with arrays, but even though arrays are being used a lot in java, they do have some serious limitations. The biggest one being the fact that the length of any array is fixed. Once an array has been allocated, it's size cannot be changed. When more items need to be stored in the same array, then are available slots, we will have to create a new array of a larger size and copy the content from the original array to the new array. To avoid running out of available slots, developers often allocate an array with enough slots to hold pretty much any amount of data. As a result, the array most often holds a whole lot of empty slots since most of the time the number of elements is less than the number of slots available in the array. If all of this is not bad enough, updating the content of the array is not easy. When for example, an entry must be inserted in the middle of the array, all elements after the insert position must be moved back to make room for the new entry. So to address these problems we can work with the collections framework. JDK 1.2 added a set of classes and interfaces to provide a more complete framework for representing data aggregation. While vector and hashtable proved to be extremely useful, there were a number of shortcomings with those classes. In addition to providing the classes and interfaces that make up the framework, there are also implementation classes that utilize these more robust features. The framework also easily supports the creation of application specific collections. Probably, the most notable feature of the collections framework is that while there may be implementations of collection classes that provides specific behaviors, such as indexed access, all classes in the framework support a more generic set of APIs, allowing different collection implementations to be treated simply as a collection of data. For example, there may be different implementations of a set, such as hashed. This is tree storage, yet application APIs can be written to utilize a set and not the underlying implementation type. The collection API defines a number of interfaces. Each interface type specifies some unique behavior of the class that implements this interface. As it can be seen here, the set, list, and queue interfaces all extend the root collection interface. Top level collection interfaces. At the top of the collection interface hierarchy is the collection interface. It is the high level interface from which all other collection interfaces extend. It provides the basic methods to represent an object that maintains a data collection. The Set interface extends directly from the collection interface, and adds no extra methods. An implementation class that implements this interface is simply stating that the elements in this collection are unique. The list interface also extends directly from the collection interface. Whereas elements in a set are unique, elements in a List may not be. A list adds the methods to support indexed access, which allows for more advanced capabilities like sorting and shuffling. And finally, the queue also extends directly from the collection interface. A queue is used to hold an ordered list of objects about to be processed, and provides various operations like insertion and removal. It follows the FIFO, or the first-in first-out principle, in that it is limited to inserting new elements at the end of the list, and deleting existing elements from the start of list. The Collection Interface. You'll notice that the methods in this interface are just enough to represent a class that maintains a group of elements. There are no methods that support indexed access, nor are there any methods that imply uniqueness, or non-uniqueness of elements. The set and list interfaces extend this interface, and the list interface adds the methods to support indexed access. Only a subset of the available methods is shown here and the methods are shown without the use of their generic type. List. The list interface extends the collection interface. It adds the methods to support indexed access to elements in the collection. A list may contain duplicate elements, although an implementation may choose not to allow this. There are no methods that provide sorting. However, a list may support sorting, and we'll see shortly that there is a helper method in the collections framework, that can perform sorting on any implementation of a list. As before, the example shown above only shows a subset of the available methods in the list interface. Also the methods are shown without their generic types. The collection API does not only define interfaces, it also comes with a standard set of interface implementations. The list interface, for example, comes with two implementations, the ArrayList and the LinkedList. The ArrayList implementation has been optimized for fast access indexing, while inserting and deleting elements from this implementation is relatively slow. The LinkedList on the other hand was optimized for fast insertions and removal, which results in a relatively slow operation when accessing elements. When creating an instance of the ArrayList class, you can now add any object type to this list. In the example above it is possible to add both dog and book instances to the list. But how often would you do this? In most cases it doesn't make sense to add any type of object to a list. It's far more likely that you'll need to create a list just containing dog references, or a separate list just containing book references. Collections and generics. Generics were introduced in Java 5. They provide compile-time type checking, and reduce the risk of a runtime error such as a ClassCastException. Generics are heavily used in the collections API. A generic type is specified when the instance of a collection is created. A generic type is also used to define method parameter and return types, limiting elements that can be added to the collection. When an instance of the generic class is created, the actual type is defined on the reference and on the assignment. To be exact, the type must be defined on the type of the reference, and only has to be defined on the type argument of the constructor when the compiler cannot determine or infer the type that has to be created. In most cases the compiler can figure out what type of object instance needs to be created by looking at the type that was defined by the reference to which the object reference will be assigned. As a result of defining the type during the construction of the object, all placeholders that were defined in the class, will now be replaced by the type you just specified. So in the example shown here, the add method now only accepts instances of book, and the get method returns book references only. When defining an API, the parameter and return types of the methods defined by the API, should use interface types, not implementation types. By doing so, the method can accept and return, any of the implementations of the interface. Also, when defining a reference to a collection, you will most often define a reference that is an interface type. Since a collection represents a group of elements, the contents of the collection can be iterated over. The enhanced for-loop can be used to iterate over any type of collection. When the collection you are iterating over is a list implementation, you can also use the for-loop and the index to retrieve each elements from the collection. The java.util.Iterator Interface. Each collection implementation will provide an implementation of this interface to allow traversing the elements in the collection. The primary advantage of iterator over enumeration, is that iterator may allow removal of elements during traversal. Enumeration does not support this method, and there is no reliable way of removing an element from a group, upon completion of the enumeration. Removing an element while traversing could also be much more efficient, especially in the case where the underlying storage is a linked list, and the element cannot be directly indexed. Also note that the remove method is optional in this interface. The ListIterator Interface. Because a List implicitly maintains ordering of elements, at least until you sort or shuffle them, there is a subtype of the iterator interface, which is called the ListIterator interface. The ListIterator provides additional methods to back up in the iteration, and also to return the next and previous index value. Okay before we complete this lecture, pause this video and consider the following questions to test yourself on the content that we have just reviewed. Write down each of your answers, and then resume the video to compare answers. Okay the answers to the above questions are, One, the collections framework defines these types, set, list, map, and queue. Two. No, all application method APIs should only reference interfaces.