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
Interface
Superinterfaces Notes Allow
Duplicates?
Allow
​null​?
Retrieval
​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"

Lists[edit]

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)

Sets[edit]

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

Queues[edit]

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.

Deques[edit]

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