Collection : Java Glossary

Introduction

You will see the term used in three contexts:

1. A collection in data structure terms, is a group of elements. It includes Sets and Lists. It also includes Maps which don’t implement Collection.
2. Collection is the interface implemented by the collection classes such as ArrayList, TreeSet and HashSet implement. It defines the methods common to them all.
3. Collections is a class of utility methods for working on collections, e.g. sorting and binary search, even though they only work on Lists.

In Java version 1.5 or later the Collection classes are generified to keep track of the class of the elements permitted to be contained in them.

All classes that implement Collection automatically implement the superinterface Iterable, allowing you to iterate over all their elements.

Gotchas

• A common programming error is to use the interface Collection when you meant the class Collections and vice versa.
• The sort method is not part of the Collection interface. It lives in the Collections class. So you cannot say myCollection. sort(). You must say Collections.sort( myCollection ); However, sort will not work on Collections generally, only Lists.
• Maps such as HashMap are not Collections, i.e. they don’t implement the Collection interface.

Examples of Collections

Missing Collections

• FIFOQueue, a FIFO (First In First Out) buffering queue.
• FIFOPriorityQueue, a FIFO queue with N levels of priority, so that the top priority items are normally taken first, but it is possible to service the lower priorities less frequently, e.g. serve four from top level, for every two from next level for everyone from the level below, or with priority bumping if an item waits in a queue past a given threshold. You could use it for applications like airline boarding, emergency waiting rooms, computer task scheduling or even your personal todo list. You can fudge a simple FIFO queue with LinkedList using use only addFirst, removeLast.
• SortedList that gives the illusion of always automatically staying sorted. I wrote one.
• Cached collections that automatically drop elements not used in a long time to keep the collection from growing too large.
• Persistent collections that automatically load from disk and save back to disk.
• For other missing collections check out these sources:
  AmberArcher
  Jakarta Common Collections (includes bidirectional map)
  PCJ
  Trove4J
  Walt Disney Tea Trove (includes: FlyweightSet, PropertyMap, SortedArrayList)

Duplicate Keys

• Write your own collection that permit duplicates.
• Invent tie breaker logic to create auxiliary tail ends to the key to artificially make all keys unique, e. g. First key rover goes in as rover and the next as rover2 Before inserting, you must always check if the key has already been added and if so, try a tie breaker until you find one that has not.
• Instead of storing data objects in your map, store a FIFOQueue of data objects that share the same key. This preserves FIFO order on duplicates. When there are no duplicate for a given keys, store a data object directly. You could similarly handle the problem with ArrayLists of duplicates instead of FIFOQueues. FIFOQueues have the advantage of not needing to estimate the number of duplicates for each key ahead of time.

The new java.lang.Comparable interface makes it easier to sort Collections. Even String implements it.

Even if you are stuck with Java version 1.1, you can still retrofit some of the 1.2 JDK (Java Development Kit) Collections classes. You won’t be able to use any of the natural ordering methods since they require adding the java.lang. Comparable interface to the core classes.

Alternatives

There are a number of techniques for returning multiple objects from a method.

// Making collections unmodifiable
Collection<C> x =  Collections.unmodifiableCollection( someCollection );
List<V> x =        Collections.unmodifiableList( someMap );
Map<K,V> x =       Collections.unmodifiableMap( someMap );
Set<S> x =         Collections.unmodifiableSet( someSet );
SortedMap<K,V> x = Collections.unmodifiableSortedMap( someSortedMap );

Books

Book referral for Data Structures and the Java Collections Framework

	recommend book⇒Data Structures and the Java Collections Framework
	by	William Collins	978-0-470-48267-4	paperback
	publisher	Wiley	978-1-118-13620-1	eBook
	published	2011-01-11	B005FHM6FU	kindle
This is about abstract data collections in general, not just the ones implemented in Java.
Online bookstores carrying Data Structures and the Java Collections Framework abe books anz abe books.ca abe books.de amazon.ca amazon.de Chapters Indigo amazon.es Chapters Indigo eBooks iberlibro.com abe books.com abe books.fr amazon.com amazon.fr Barnes & Noble abe books.it Nook at Barnes & Noble amazon.it Kobo junglee.com Google play abe books.co.uk O’Reilly Safari amazon.co.uk Powells other stores
Greyed out stores probably do not have the item in stock. Try looking for it with a bookfinder.

Book referral for Java Generics and Collections

	recommend book⇒Java Generics and Collections
	by	Maurice Naftalin & Philip Wadler	978-0-596-52775-4	paperback
	publisher	O’Reilly	978-0-596-55150-6	eBook
	published	2006-10-18	B0026OR2HM	kindle
Covers both generics and Collections. Covers Java 1.5+ features such as autoboxing, for:each as well. Recommended by Mike Schilling.
Online bookstores carrying Java Generics and Collections abe books anz abe books.ca abe books.de amazon.ca amazon.de Chapters Indigo amazon.es Chapters Indigo eBooks iberlibro.com abe books.com abe books.fr amazon.com amazon.fr Barnes & Noble abe books.it Nook at Barnes & Noble amazon.it Kobo junglee.com Google play abe books.co.uk O’Reilly Safari amazon.co.uk Powells other stores
Greyed out stores probably do not have the item in stock. Try looking for it with a bookfinder.

Learning More