Java Collections Framework

CST 3613 Fall 2018 Application Development with DB Lecture 8: Data Structures in Java Java Collections Framework Professor HG Locklear Objectives  Define Collections in Java  Describe Collection Operations  Describe Collection Traversal  Describe the use of Algorithms on Collections General  A collection is an object that contains a group of objects.  A collection is also known as a container because contains objects.  Each object in a collection is known as an element of the collection.  The Collections Framework consist of Interfaces, Implementation classes, and some utility classes that allow the handling of most types collections that would be encountered in a Java application.  Collections are designed to work only with objects.  Primitive types can be used in collections but require a wrapper class.  All collections in Java are generic. General  Java Collections Major Resources  https://docs.oracle.com/javase/tutorial/collections/TOC.html  https://docs.oracle.com/javase/tutorial/collections/interfaces/index.html  https://docs.oracle.com/javase/tutorial/collections/implementations/index.html  https://docs.oracle.com/javase/tutorial/collections/algorithms/index.html  https://docs.oracle.com/javase/tutorial/collections/streams/index.html  https://docs.oracle.com/javase/tutorial/collections/custom-implementations/index.html  https://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html Collection Framework  The Collections Framework consist of three main components: Interfaces  Implementation Classes  Algorithms Classes   An interface represents a specific type of collection in the framework. There is one interface defined for very type of collection in the framework.  Java uses interfaces to define collections because:  Interfaces allow user-implemented class to be independent of any specific implementation.  Classes that implement collections defined by interfaces may be changed without forcing a change to the code that was written using the interface.   The Collections Framework provides implementation of collection interfaces which are known as implementation classes. Collections Framework (common interfaces) Collections Map SortedMap Queue List BlockingQueue SortedSet Deque TransferQueue Set BlockingDeque NaviagableSet Collection Data Structure  In general terms, the Java Collections Framework models common data structures. 1 2 3 4 Obj1 Obj2 Obj3 Obj4 Obj5 A LIST is just a ordered sequence of objects each located at a specific index A B C D E Obj1 Obj2 Obj3 Obj4 Obj5 A MAP is just an unordered sequence of KEY-VALUE pairs Add or remove only by referring to the KEY Insert at TAIL remove at HEAD Insert or remove object from any position in the LIST 1 2 3 4 Obj1 Obj2 Obj3 Obj4 Obj5 A QUEUE is just an LIST that conforms to LIFO rules 1 2 3 4 Obj1 Obj2 Obj3 Obj4 Obj5 A SET is just an LIST that does not contain duplicates Main Collection Interfaces Interface Description • • • Map • • Queue • • An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value. The Map interface provides three collection view s, which allow a map's contents to be viewed as a set of keys, collection of values, or set of key-value mappings. The order of a map is defined as the order in which the iterators on the map's collection views return their elements. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not. Queues typically, but do not necessarily, order elements in a FIFO (first-in-firstout) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out). Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties. Main Collection Interfaces Interface Description • • • List Set • • • • • An ordered collection (also known as a sequence). Allows precise control over where in the list each element is inserted. Can access elements by their integer index (position in the list), and search for elements in the list. Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. Models the mathematical set abstraction. The Collection Interface    The Collection interface is the root of the collection interface hierarchy. It defines a generic collection. There is no implementation of the collection interface.  The Collection interface is the most generic type of collection. It can be used where the type of collection be used is of no concern. (cannot be a map).  All non-map collection interfaces inherit from the Collection interface and add methods of their own to provide functionality specific to their type.  The methods of the Collection interface are classified into five categories:      Methods for Basic Operations Methods for Bulk(Group) Operations Methods for Aggregate Operations Methods for Array Operations Methods for Comparison Operations Basic Operations  Methods for basic operations allow operations such as: Basic Method Description int size() Returns the number of elements in the collection boolean isEmpty() Returns true if the collection is empty Boolean contains(Object o) Returns true if the collection contains the specified object Boolean add(E o) Adds an element to the collection and returns true if its successful Boolean remove(E o) Removes an element from the collection and returns true if it is successful Iterator iterator() Returns an iterator that can be used to traverse the collection Bulk Operations   Bulk or group operations all operations on the entire collection of elements at once. Methods for bulk or group operations allow operations such as: Bulk Operation Description boolean addAll (Collection c) Adds all elements of the specified collection to this collection. Returns true if successful void clear() Removes all elements of the collection boolean containsAll (Collection c) Returns true if all the elements in the specified collection are elements of the specified collection boolean removeAll (Collection c) Removes all the elements from the collection that are elements of the specified collection. Returns true if the collection is changed as a result of this operation. Aggregate Operations   Aggregate operations allow collections to support Streams (sequential list of elements) Methods for aggregate operations allow operations such as: Aggregate Operation Description Default Stream stream() Returns a sequential Stream with the collection as the source for the elements of the Stream Default Stream parallelStream () Returns a possibly parallel Stream with the collection as the source of elements for the Steam Array Operations   Array operations allow collections to be converted to arrays Methods for array operations allow operations such as: Array Operation Object[ ] toArray() Description Returns the elements of the collection in an array Returns the array of the specified type T that contains all elements of the collection. • If the passed in array length is equal to or greater than the size of the collection all elements are copied to it. T [ ] toArray(T[ ] • If the length of the passed in array is less than the size of a) the collection a new array of the same type with the required length is created. • If the array length is larger than the size of the collection then extra array indexes are set to null. Comparison Operations   Comparison operations allow for the comparing of two collection for equality Methods for comparison operations allow operations such as: Comparison Operation Description Boolean equals(Object o) Returns true if two collections are equal. The specifi c Int hashCode() Returns the hash code for the collection. For two elements collection specifi es the criteria for equality of the two collections. to be equal their hash codes must be equal. Example Operations (ArrayList) Traversing a Collection Different types of collections store their elements differently using different data structures.  Some collections impose ordering on their elements and some do not.  The Collections Framework provides three ways to traverse a collection.   Use an Iterator   Use a for-each Loop   Iterator allow the following operations: ▪ Check if there are elements that have not yet been accessed using the iterator. ▪ Access the next element in the collection ▪ Remove the accessed element of the collection Iterator allow the following operations: ▪ Check if there are elements that have not yet been accessed using the iterator. ▪ Access the next element in the collection Use the forEach() method   Iterates over all the elements in the collection and applies a specified action Not available for Maps Iterator Traversal Can remove elements of the collection using iterator Enhanced For Loop Traversal (for-each) forEach() Method Traversal Applying Algorithms  The Collections Framework allows the application of many types of algorithms on all or a few elements of a collection. All algorithms are static methods found in the Collections class. https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html