Java Collections Framework PDF

The Collections Framework java.util is a package contains a largeassortment of classes and interfaces that support a broad range of functionality. The java.utilpackage contains one of Java’s most powerful subsystems: the Collections Framework. TheCollections Framework is a sophisticated hierarchy of...

The Collections Framework java.util is a package contains a largeassortment of classes and interfaces that support a broad range of functionality. The java.utilpackage contains one of Java’s most powerful subsystems: the Collections Framework. TheCollections Framework is a sophisticated hierarchy of interfaces and classes. Collections Overview The Java Collections Framework standardizes the way in which groups of objects are handledby the programs. Collections were not part of the original Java release, but were added later. The implementations for the fundamental collections(dynamic arrays, linked lists, trees, and hash tables) are highly efficient. Algorithms are another important part of the collection mechanism. Algorithms operateon collections and are defined as static methods within the Collectionsclass. Another item closely associated with the Collections Framework is the Iteratorinterface.An iterator offers a general-purpose, standardized way of accessing the elements within acollection, one at a time. The elements of any collection classcan be accessed through the methods defined by Iterator. The framework also defines several map interfaces and classes. Maps store key/value pairs. JDK 5 Changed the Collections Framework When JDK 5 was released, some fundamental changes were made to the CollectionsFramework. This significantly increased its power and streamlined its use. These changesinclude the addition of generics, autoboxing/unboxing, and the for-each style for loop.  Generics Fundamentally Changed the Collections Framework The addition of generics caused a significant change to the Collections Framework becausethe entire Collections Framework was reengineered for it. All collections are now generic,and many of the methods that operate on collections take generic type parameters.Generics added the one feature that collections had been missing: type safety. Prior togenerics, all collections stored Object references, which meant that any collection couldstore any type of object. Thus, it was possible to accidentally store incompatible types in acollection.   Autoboxing Facilitates the Use of Primitive Types Autoboxing/unboxing facilitates the storing of primitive types in collections. A collection can store only references, not primitive values. In the past, if the user wantedto store a primitive value, such as an int, in a collection, one had to manually box it into itstype wrapper. When the value was retrieved, it needed to be manually unboxed (by usingan explicit cast) into its proper primitive type. Because of autoboxing/unboxing there is no need to manually perform these operations.  The For-Each Style for Loop All collection classes in the Collections Framework were modified to implement theIterable interface, which means that a collection can be cycled through by use of the foreachstyle for loop. The Collection Interfaces The Collections Framework defines several interfaces. 1. Collection Interface The Collection interface is the foundation upon which the Collections Framework is built. Collection is a generic interface that has this declaration: interface Collection Here, E specifies the type of objects that the collection will hold. Collection declares the core methods that are needed. Methods defined by Collection interface: boolean add(E obj) Adds objto the invoking collection. Returns true if objwas added to the collection. Returns false if objis already a member of the collection and the collection does not allow duplicates. void clear( ) Removes all elements from the invoking collection. boolean contains(Object obj) Returns true if objis an element of the invoking collection. Otherwise, returns false. boolean equals(Object obj) Returns true if the invoking collection and objare equal. Otherwise, returns false. booleanisEmpty( ) Returns true if the invoking collection is empty. Otherwise, returns false. boolean remove(Object obj) Removes one instance of objfrom the invoking collection. Returns true if the element was removed. Otherwise, returns false. int size( ) Returns the number of elements held in the invoking collection. 2. List Interface The List interface extends Collection and declares the behaviour of a collection that storesa sequence of elements. Elements can be inserted or accessed by their position in the list. A list may contain duplicate elements. List is a generic interfacethat has this declaration: interface List Here, E specifies the type of objects that the list will hold. In addition to the methods defined by Collection, List defines some of its own. Methods defined by List interface: void add(int index, E obj) Inserts obj into the invoking list at the index passedin index. Any preexisting elements at or beyond thepoint of insertion are shifted up. Thus, no elementsare overwritten. E get(int index) Returns the object stored at the specified indexwithin the invoking collection. intindexOf(Object obj) Returns the index of the first instance of obj in theinvoking list. If obj is not an element of the list, –1 isreturned. intlastIndexOf(Object obj) Returns the index of the last instance of obj in theinvoking list. If obj is not an element of the list, –1 isreturned. E remove(int index) Removes the element at position index from theinvoking list and returns the deleted element. Theresulting list is compacted. That is, the indexes ofsubsequent elements are decremented by one. 3. Set Interface: The Set interface defines a set. It extends Collection and declares the behaviour of a collection that does not allow duplicate elements. It does not define anyadditional methods of its own. The change is that the add( ) method returns false if an attempt is made to add duplicate elements to a set.Setis a generic interface that has this declaration: interface Set Here, E specifies the type of objects. The SortedSet Interface: The SortedSet interface extends Set and declares the behaviour of a set sorted in ascending order.Set is a generic interface that has this declaration: interface Set Methods defined by SortedSet interface: E first( ) Returns the first element in the invoking sorted set. SortedSetheadSet(E Returns a SortedSet containing those elements lessthan end that are contained in the invoking sorted end) set. Elements in the returned sorted set are alsoreferenced by the invoking sorted set. E last( ) Returns the last element in the invoking sorted set. SortedSettailSet(E start) Returns a SortedSet that contains those elementsgreater than or equal to start that are contained inthe sorted set. Elements in the returned set are alsoreferenced by the invoking object. The NavigableSet Interface: The NavigableSet interface extends SortedSet and declares the behaviour of a collectionthat supports the retrieval of elements. NavigableSet is a generic interface that has this declaration: interfaceNavigableSet Methods defined by NavigableSet interface: E ceiling(E obj) Searches the set for the smallest element e such thate >= obj. If such an element is found, it is returned.Otherwise, null is returned. E floor(E obj) Searches the set for the largest element e such thate obj. If such an element is found, it is returned.Otherwise, null is returned. E lower(E obj) Searches the set for the largest element e such thate < obj. If such an element is found, it is returned.Otherwise, null is returned. 4. The Queue Interface The Queue interface extends Collection and declares the behavior of a queue, which isoften a first-in, first-out list. (However, there are types of queues in which the ordering is based upon other criteria) Queue is a generic interface that has this declaration: interface Queue Here, E specifies the type of objects that the queue will hold. Methods defined by Queue interface: E element( ) Returns the element at the head of the queue. The element is not removed. It throws NoSuchElementException if the queue is empty. boolean offer(E obj) Attempts to add obj to the queue. Returns true if obj was added and falseotherwise. E peek( ) Returns the element at the head of the queue. It returns null if the queue is empty. The element is not removed. E poll( ) Returns the element at the head of the queue, removing the element in the process. It returns null if the queue is empty. E remove( ) Removes the element at the head of the queue, returning the element inthe process. It throws NoSuchElementException if the queue is empty. The Deque Interface The Dequeinterface extends Queue and declares the behaviour of a double-ended queue.Double-ended queues can function as standard, first-in, first-out queues or as last-in, firstout stacks. Dequeis a generic interface that has this declaration: interfaceDeque Here, E specifies the type of objects that the deque will hold. Methods defined by DeQueue interface: void addFirst(E obj) Adds obj to the head of the deque. void addLast(E obj) Adds obj to the tail of the deque. E getFirst( ) Returns the first element in the deque. E getLast( ) Returns the last element in the deque. E peekFirst( ) Returns the element at the head of the deque. It returnsnull if the deque is empty. The object is not removed. E peekLast( ) Returns the element at the tail of the deque. It returnsnull if the deque is empty. The object is not removed. Collection classes. 1. The ArrayList Class The ArrayList class extends AbstractList and implements the List interface. ArrayList is ageneric class that has this declaration: classArrayList Here, E specifies the type of objects that the list will hold. ArrayList supports dynamic arrays that can grow as needed. In Java, standard arrays are of a fixed length. So theCollections Framework defines ArrayList. In essence, an ArrayList is a variable-length arrayof object references. That is, an ArrayList can dynamically increase or decrease in size.Array lists are created with an initial size. When this size is exceeded, the collection isautomatically enlarged. When objects are removed, the array can be shrunk. Example: importjava.util.*; classArrayListDemo { public static void main(String args[]) { // Create an array list. ArrayList al = new ArrayList(); System.out.println("Initial size of al: " + al.size()); // Add elements to the array list. al.add("C"); al.add("A");  al.add("E"); al.add("B"); al.add("D"); al.add("F"); al.add(1, "A2"); System.out.println("Size of al after additions: " + al.size()); // Display the array list. System.out.println("Contents of al: " + al); // Remove elements from the array list. al.remove("F"); al.remove(2); System.out.println("Size of al after deletions: " + al.size()); System.out.println("Contents of al: " + al); } } The output from this program is shown here: Initial size of al: 0 Size of al after additions: 7 Contents of al: [C, A2, A, E, B, D, F] Size of al after deletions: 5 Contents of al: [C, A2, E, B, D] The above program begins with an array list created. As no elements are inserted the size is 0. (Fetched using size() method) Using the add method, elements are inserted to the ArrayList. remove() is used to delete element from the list. Obtaining an Array from an ArrayList: importjava.util.*; classArrayListToArray { public static void main(String args[]) { // Create an array list. ArrayList al = new ArrayList(); // Add elements to the array list. al.add(1); al.add(2); al.add(3); al.add(4); System.out.println("Contents of al: " + al); // Get the array. Integer ia[] = new Integer[al.size()]; ia = al.toArray(ia); int sum = 0; // Sum the array. for(int i : ia) sum += i; System.out.println("Sum is: " + sum); } } The output from the program is shown here: Contents of al: [1, 2, 3, 4] Sum is: 10 The program begins by creating a collection of integers. Next, toArray( ) is called and it obtains an array of Integers. Then, the contents of that array are summed by use of a for-each stylefor loop. 2. The LinkedList Class: The LinkedList class extends AbstractSequentialList and implements the List, Deque, andQueue interfaces. It provides a linked-list data structure. LinkedList is a generic class thathas this declaration: classLinkedList Here, E specifies the type of objects that the list will hold. Example: importjava.util.*; classLinkedListDemo { public static void main(String args[]) { // Create a linked list. LinkedListll = new LinkedList(); // Add elements to the linked list. ll.add("F"); ll.add("B"); ll.add("D"); ll.add("E"); ll.add("C"); ll.addLast("Z"); ll.addFirst("A"); ll.add(1, "A2"); System.out.println("Original contents of ll: " + ll); // Remove elements from the linked list. ll.remove("F"); ll.remove(2); System.out.println("Contents of ll after deletion: "+ ll); // Remove first and last elements. ll.removeFirst(); ll.removeLast(); System.out.println("ll after deleting first and last: "+ ll); // Get and set a value. String val = 11.get(2); ll.set(2, val + " Changed"); System.out.println("ll after change: " + ll); } } The output from this program is shown here: Original contents of ll: [A, A2, F, B, D, E, C, Z] Contents of ll after deletion: [A, A2, D, E, C, Z] ll after deleting first and last: [A2, D, E, C] ll after change: [A2, D, E Changed, C] 3. The HashSet Class HashSetextends AbstractSetand implements the Set interface. It creates a collection that uses a hash table for storage. HashSetis a generic class that has this declaration: classHashSet Here, E specifies the type of objects that the set will hold. HashSetdoes not define any additional methods beyond those provided by itssuperclasses and interfaces.It is important to note that HashSet does not guarantee the order of its elements. Example: importjava.util.*; classHashSetDemo { public static void main(String args[]) { // Create a hash set. HashSeths = new HashSet(); // Add elements to the hash set. hs.add("B"); hs.add("A"); hs.add("D"); hs.add("E"); hs.add("C"); hs.add("F"); System.out.println(hs); } } The following is the output from this program:(May vary) [D, E, F, A, B, C] The TreeSet Class TreeSetextends AbstractSetand implements the NavigableSetinterface. It creates acollection that uses a tree for storage. Objects are stored in sorted, ascending order. Accessand retrieval times are quite fast, which makes TreeSetan excellent choice when storinglarge amounts of sorted information that must be found quickly.TreeSetis a generic class that has this declaration: classTreeSet Here, E specifies the type of objects that the set will hold. Example: importjava.util.*; classTreeSetDemo { public static void main(String args[]) { // Create a tree set. TreeSetts = new TreeSet(); // Add elements to the tree set.  ts.add("C"); ts.add("A"); ts.add("B"); ts.add("E"); ts.add("F"); ts.add("D"); System.out.println(ts); } } The output from this program is shown here: [A, B, C, D, E, F] Because TreeSet stores its elements in a tree, they are automatically arranged in sorted order, as the output confirms. Accessing a Collection via an Iterator Often there would be a need to cycle through the elements of the collection. One way to do this is to employ an iterator, which is an objectthat implements either the Iterator or the ListIterator interface. Iterator enables tocycle through a collection, obtaining or removing elements.ListIterator extends Iteratorto allow bidirectional traversal of a list, and the modification of elements. Using an Iterator Before accessing a collection through an iterator, it must be obtained first. By using this iterator object, each element in the collection can be accessed, one element at a time. In general, to use an iterator to cycle through the contents of acollection, follow these steps: 1. Obtain an iterator to the start of the collection by calling the collection’s iterator( ) method. 2. Set up a loop that makes a call to hasNext( ). Have the loop iterate as long ashasNext( ) returns true. 3. Within the loop, obtain each element by calling next( ). Example: classIteratorDemo { public static void main(String args[]) { // Create an array list. ArrayList al = new ArrayList(); // Add elements to the array list. al.add("C"); al.add("A"); al.add("E"); al.add("B"); al.add("D"); al.add("F"); // Use iterator to display contents of al. System.out.print("Original contents of al: ");  Iteratoritr = al.iterator(); while(itr.hasNext()) { String element = itr.next(); System.out.print(element + " "); } // Modify objects being iterated.UsingListinterator ListIteratorlitr = al.listIterator(); while(litr.hasNext()) { String element = litr.next(); litr.set(element + "+"); } System.out.print("Modified contents of al: "); itr = al.iterator(); while(itr.hasNext()) { String element = itr.next(); System.out.print(element + " "); } System.out.println(); // Now, display the list backwards. System.out.print("Modified list backwards: "); while(litr.hasPrevious()) { String element = litr.previous(); System.out.print(element + " "); } System.out.println(); } } The output is shown here: Original contents of al: C A E B D F Modified contents of al: C+ A+ E+ B+ D+ F+ Modified list backwards: F+ D+ B+ E+ A+ C+ The for-each version of the for loop is often a more convenient alternative tocycling through a collection than is using an iterator. Example: importjava.util.*; classForEachDemo { public static void main(String args[]) { // Create an array list for integers. ArrayListvals = new ArrayList(); // Add values to the array list. vals.add(1); vals.add(2); vals.add(3); vals.add(4); vals.add(5); // Use for loop to display the values. System.out.print("Contents of vals: "); for(int v : vals) System.out.print(v + " ");  System.out.println(); } } Storing User-Defined Classes in Collections The previous examples have stored built-in objects, such asString or Integer, in a collection. Collections are not limited to the storage ofbuilt-in objects.The power of collections is that they can store any typeof object, including objects of classes that the user creates.For example, the following example uses a LinkedListto store mailing addresses: importjava.util.*; class Address { private String name; private String street; private String city; private String state; private String code; Address(String n, String s, String c,Stringst, String cd) { name = n; street = s; city = c; state = st; code = cd; } public String toString() { return name + "\n" + street + "\n" +city + " " + state + " " + code; } } classMailList { public static void main(String args[]) { LinkedList ml = new LinkedList(); // Add elements to the linked list. ml.add(new Address("J.W. West", "11 Oak Ave", "Urbana", "IL", "61801")); ml.add(new Address("Ralph Baker", "1142 Maple Lane", "Mahomet", "IL", "61853")); ml.add(new Address("Tom Carlton", "867 Elm St", "Champaign", "IL", "61820")); // Display the mailing list. for(Address element : ml) System.out.println(element + "\n"); System.out.println(); } } Output: J.W. West 11 Oak Ave Urbana IL 61801 Ralph Baker 1142 Maple Lane Mahomet IL 61853 Tom Carlton 867 Elm St Champaign IL 61820