Java: Alternative Data Structures

Packages have been developed outside of Sun for additional functionality. The following free, GPL, packages fill in missing parts of the Collections package, but remain consistent with the basic Java List, Map, and Set interfaces. These packages address several shortcomings of the Java Collections data structures: lack of support for primitive data types, lack of support for generics, etc.

Jakarta Commons Collections Package

Has "special-purpose implementations of Lists and Maps for fast access" and "methods to test or create typical set-theory properties of collections such as union, intersection, and closure". It also has some implementations of "bags", which are maps that count the number of times an element is added. Free, open source.

fastutil (fastutil.dsi.unimi.it)

"Provides type-specific maps and sets with a small memory footprint and much (2 to 10 times) faster access and insertion. The classes implement their standard counterpart interface (e.g., Map for maps) and can be plugged into existing code." Free, open source.

Primitive Collections for Java (PCJ, pcj.sourceforge.net)

Is a set of collection classes for primitive data types in Java. The goal is to provide an efficient alternative to the Java Collections Framework (JCF) when using primitive data types, such as int, boolean, or double. Some of its main features are:
Interface hierarchy for all primitive types. PCJ provides symmetrical interface hierarchy for each of the primitive Java data types: boolean, char, byte, short, int, long, float, and double. Each hierarchy includes interfaces for general collections, sets, lists, and maps. To increase the learning rate and make adaptions easier to implement, each hierarchy resembles the interfaces of JCF as close as possible. Free.

GNU Trove for Java

Provides free, fast, lightweight implementations of the Java Collections API as well as collections support for primitive types.

Colt

Provides support for high-performance numerical algorithms.

Sosnoski Collections

Provides collections for primitive types.

Glazed Lists

"Glazed Lists is an application of the Decorator and Observer patterns over Java Lists. It provides transforming views of a source list that respond to changes as they occur. These views can be layered to provide simple and powerful manipulation of the source data." Some GUI component models are also defined to make it easy to use them in a Swing GUI.