This article will give you an overview of all standard Java collections. We will categorize their distinguishable properties and main use cases. Besides that, we will list all correct ways of transforming your data between various collection types.
Array is the only collection type built in Java. It is useful when you know an upper bound on the number of processed elements in advance.
java.util.Arrays contains a lot of useful methods for array processing:
Arrays.asList– conversion from array to
List, which could be passed to other standard collection constructors.
Arrays.binarySearch– fast lookup in a sorted array or its subsection.
Arrays.copyOf– use this method if you need to expand your array while keeping its contents.
Arrays.copyOfRange– if you need to make a copy of the whole array or its subsection.
Arrays.deepHashCode– versions of
Arrays.equals/hashCodesupporting nested sub-arrays.
Arrays.equals– if you need to compare two arrays for equality, use this method instead of array
equalsmethod ( array.
equalsis not overridden in any array, so it only compares references to arrays, rather than their contents ). This method may be combined with Java 5 boxing and varargs in order to write a simple implementation of your class
equalsmethod – just pass all your class fields to
Arrays.equalsafter comparing object types.
Arrays.fill– populate the whole array or its subsection with a given value.
Arrays.hashCode– useful method for calculating a hashcode of array contents ( array own
hashcodemethod can not be used for this purpose ). This method may be combined with Java 5 boxing and varargs in order to write a simple implementation of your class
hashcodemethod – just pass all your class fields to
Arrays.sort– sort the full array or its subsection using natural ordering. There is also a pair of
Arrays.sortmethods for sorting an
Objectusing a provided
Arrays.toString– fine-print the array contents.
If you need to copy one part of array (or the whole array) into another already existing array, you need to use
System.arraycopy, which copies a given number of elements from a given position in the source array to a given position in the destination array. Generally, this is the fastest way to copy array contents in Java (but in some cases you may need to check if ByteBuffer bulk copy works faster ).
Finally, we need to mention that any
Collection could be copied into an array using
T Collection.toArray( T a ) method. The usual pattern of this method call:
Such method call allocates a sufficient array for storing the whole collection, so that
toArray doesn’t have to allocate sufficiently large array to return.
This part of the article describes non-thread-safe collections. All these collections are stored in the
java.util package. Some of these collections were present in Java since Java 1.0 (and are now deprecated), most of them were already present in Java 1.4. Enum collections were added in Java 1.5 with the support of generics in all collection classes.
PriorityQueue was also added in Java 1.5. The latest addition to the non-thread-safe collections framework is
ArrayDeque, which was added in Java 1.6.
ArrayList – the most useful
Listimplementation. Backed by an array and an
int– position of the first not used element in the array. Like all
Lists, expands itself when necessary. Has constant element access time. Cheap updates at the tail (constant complexity), expensive at the head (linear complexity) due to
ArrayListinvariant – all elements start from index = 0 in the underlying array, which means that everything to the right from the update position must be moved to the right for insertions and to the left for removals. CPU-cache friendly collection due to being backed by an array (unfortunately, not too friendly, because contains
Objects, which are just pointers to the actual objects).
Dequeimplementation – each
Nodeconsists of a value,
nextpointers. It means that element access/updates have linear complexity (due to an optimization, these methods do not traverse more than a half of the list, so the most expensive elements are located in the middle of the list). You need to use
ListIteratorsif you want to try to write fast
LinkedListcode. If you want a
Queue/Dequeimplementation (you need to access only first and last elements) – consider using
Vector– a prehistoric version of
ArrayListwith all synchronized methods. Use