Introduction to CollectionsCollectionsTypes of CollectionThe Collections hierarchyCollections are ADTsThe Collection interfaceThe Iterator interfaceThe Set interfaceThe List interfaceThe SortedSet interfaceThe Map interfaceThe SortedMap interfaceSome implementationsLearn these slides well!The EndJan 14, 2019Introduction to Collections2CollectionsA collection is a structured group of objectsJava 1.2 introduced the Collections FrameworkCollections are defined in java.utilThe Collections framework is mostly about interfacesThere are a number of predefined implementationsJava 5 introduced generics and “genericized” all the existing collectionsVectors have been redefined to implement CollectionTrees, linked lists, stacks, hash tables, and other classes are implementations of CollectionArrays do not implement the Collection interfaces3Types of CollectionJava supplies several types of Collection:Set: cannot contain duplicate elements, order is not importantSortedSet: like a Set, but order is importantList: may contain duplicate elements, order is importantJava also supplies some “collection-like” things:Map: a “dictionary” that associates keys with values, order is not importantSortedMap: like a Map, but order is importantWhile you can get all the details from the Java API, you are expected to learn (i.e. memorize):The signatures of the “most important” methods in each interfaceThe most important implementations of each interface4The Collections hierarchy5Collections are ADTsCollections are one of the best-designed parts of Java, becauseThey are elegant: they combine maximum power with maximum simplicityThey are uniform: when you know how to use one, you almost know how to use them allYou can easily convert from one to another6The Collection interfaceMuch of the elegance of the Collections Framework arises from the intelligent use of interfacesThe Collection interface specifies (among many other operations):boolean add(E o)boolean contains(Object o)boolean remove(Object o)boolean isEmpty()int size()Object[] toArray()Iterator<E> iterator()You should learn all the methods of the Collection interface--all are important7The Iterator interfaceAn iterator is an object that will return the elements of a collection, one at a timeinterface iterator<E>boolean hasNext() Returns true if the iteration has more elements E next()Returns the next element in the iteration void remove()Removes from the underlying collection the last element returned by the iterator (optional operation)8The Set interfaceA set is a collection in which:There are no duplicate elements (according to equals), andOrder is not importantinterface Set<E> implements Collection, IterableThe methods of Set are exactly the ones in CollectionThe following methods are especially interesting:boolean contains(Object o) // membership testboolean containsAll(Collection<?> c) //subset testboolean addAll(Collection<? extends E> c) // unionboolean retainAll(Collection<?> c) // intersectionboolean removeAll(Collection<?> c) // differenceaddAll, retainAll, and removeAll return true if the receiving set is changed, and false otherwise9The List interfaceA list is an ordered sequence of elementsinterface List<E> implements Collection, IterableSome important List methods are:void add(int index, E element)E remove(int index)boolean remove(Object o)E set(int index, E element)E get(int index)int indexOf(Object o)int lastIndexOf(Object o)ListIterator<E> listIterator()A ListIterator is like an Iterator, but has, in addition, hasPrevious and previous methods10The SortedSet interfaceA SortedSet is a Set for which the order of elements is importantinterface SortedSet<E> implements Set, Collection, IterableTwo of the SortedSet methods are:E first()E last()More interestingly, only Comparable elements can be added to a SortedSet, and the set’s Iterator will return these in sorted orderThe Comparable interface is covered in a separate lecture11The Map interfaceA map is a data structure for associating keys and valuesInterface Map<K,V>The two most important methods are:V put(K key, V value) // adds a key-value pair to the mapV get(Object key) // given a key, looks up the associated valueSome other important methods are:Set<K> keySet() Returns a set view of the keys contained in this map.Collection<V> values()Returns a collection view of the values contained in this map12The SortedMap interfaceA sorted map is a map that keeps the keys in sorted orderInterface SortedMap<K,V>Two of the SortedMap methods are:K firstKey()K lastKey()More interestingly, only Comparable elements can be used as keys in a SortedMap, and the method Set<K> keySet() will return a set of keys whose iterator will return them sorted orderThe Comparable interface is covered in a separate lecture13Some implementationsclass HashSet<E> implements Setclass TreeSet<E> implements SortedSetclass ArrayList<E> implements Listclass LinkedList<E> implements Listclass Vector<E> implements Listclass Stack<E> extends VectorImportant methods: push, pop, peek, isEmptyclass HashMap<K, V> implements Mapclass TreeMap<K, V> implements SortedMapAll of the above provide a no-argument constructor14Learn these slides well!I hate to ask students to memorize lists of methods, but this time I willYou should know the signatures of all the methods in this set of slidesOnce you have a better feel for how these collections are used, the methods will make sense and be easier to remember15The
View Full Document
Unlocking...