Java Collections Overview

From Wikiversity
Jump to: navigation, search

Collections are objects whose sole purpose is to store other objects, like arrays. Unlike arrays, however, collections have convenience methods to, say, return a portion of the original collection. A drawback of collections is that they can't hold primitives. (They can, however, hold wrappers, like ​java.lang.Integer​.)

All collection objects ultimately implement the ​java.util.Collection​ interface. However, few if any implement the interface directly. There are multiple sub-interfaces of ​Collection​ that specify additional methods. These sub-interfaces decide the functionality of a collection; individual classes usually differ only in implementation. (For example, both ​ArrayList​ and ​LinkedList​ fulfill the general contract of the ​List​ interface, but do so differently.)

Most implementations of the ​Collection​ interface are in ​java.util​. Exceptions will be noted when introduced.

Although the ​Map​ interface does not extend ​Collection​, it is usually included in discussions of collections and will be explained here.

Hierarchy of Collections[edit]

The actual hierarchy of what extends what, and what implements what, is fairly intricate. Here is a simplified hierarchy of the collections framework:

  • Interface ​java.lang.Iterable​
    • Interface ​Collection​
      • Interface ​List​
        • Class ​ArrayList​
        • Class ​LinkedList​ (also implements ​Deque​)
        • Class ​Vector​
          • Class ​Stack​ (legacy class, use ​Deque​, which is more powerful)
      • Interface ​Set​
        • Class ​HashSet​
          • Class ​LinkedHashSet​
        • Interface ​SortedSet​
          • Interface ​NavigableSet​
            • Class ​TreeSet​
        • Class ​EnumSet​
      • Interface ​Queue​
        • Class ​PriorityQueue​
        • Interface ​Deque​
          • Class ​LinkedList​ (also implements ​List​)
          • Class ​ArrayDeque​
  • Interface ​Map​
    • Class ​HashMap​
    • Interface ​SortedMap​
      • Interface ​NavigableMap​
        • Class ​TreeMap​

Comparison of Collections[edit]

Comparison of Selected Interfaces
Class or
Superinterfaces Notes Allow
​Collection​ ​Iterable​ The parent interface of the entire collections framework. Depends Depends Through iterator
​List​ ​Collection​ Allows you to put elements in a specific order. Each element is associated with an index. Yes Depends Through iterator, or
Random access by numerical index
​Set​ ​Collection​ Prohibits duplicate elements. Easy test for membership. You can't order the elements. No Depends Through iterator
​Queue​ ​Collection​ Only the "head" (next out) is available. Yes Depends Peeking or polling, or
Through iterator
​PriorityQueue​ ​Queue​ High priority elements get to the head first. Yes No Peeking or polling
​Deque​ ​Queue​ A "double-ended queue": insert and remove at both ends. Yes Depends Peeking or polling, or
Through iterator
​Map​ n/a Maps keys to values Keys: no
Values: yes
Keys: (only 1 null key is allowed)
Values: yes
Lookup by key object , or
Through ​keySet​, ​entrySet​, ​values​ "views"


Comparison of Lists
ArrayList LinkedList
Description Dynamic (a.k.a. growable, resizable) array Doubly-linked list
Random Access with index (​get()​) O(1) O(n)
Insertion (​add()​) / removal at the back amortized O(1) O(1)
Insertion / removal at the front O(n) O(1)
One step of iteration through an ​Iterator​ O(1) O(1)
Insertion / removal in the middle through an ​Iterator​ / ​ListIterator​ O(n) O(1)
Insertion / removal in the middle through the index O(n) O(n)
Search ​contains()​ / removal ​remove()​ by object O(n) O(n)


Comparison of Sets
HashSet TreeSet
Description Hash table Self-balancing binary search tree
Requirements Objects need to implement a hash function (​hashCode()​) which is consistent with ​equals()​ Either objects need to implement the ​Comparable​ interface and be able to compare to each other; or a ​Comparator​ for the objects must be provided; the ordering must satisfy a "total ordering"
Test for membership (​contains()​) O(1) average
O(n) worst-case
O(log n)
Insertion (​add()​) / removal (​remove()​) O(1) average
O(n) worst-case
O(log n)
One step of iteration through an ​Iterator​ O(1) O(1)
Iterates through elements in ascending order No Yes


Comparison of Queues
PriorityQueue Other queues (e.g. LinkedList)
Description Priority queue. The head of the queue is a smallest element, according to the ordering of the elements, or the ordering provided by a comparator. FIFO (First In First Out) queue. The head of the queue is the element that was put into it longer ago than all the other elements in the queue.


Comparison of Deques
LinkedList ArrayDeque
Description Doubly-linked list Dynamic-array based structure