Java Collections Overview

From Wikiversity
Jump to navigation Jump to 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 | edit source]

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
      • Class LinkedHashMap
    • Interface SortedMap
      • Interface NavigableMap
        • Class TreeMap

Comparison of Collections[edit | edit source]

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 | edit source]

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)
Iteration order Insertion order Insertion Order

Sets[edit | edit source]

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().

Special care is required when mutating objects within a HashSet.*

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"[1].

Special care is required when mutating objects within a TreeSet.**

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

*Because an object's position within the HashSet depends on its hashCode() (and its contents), changing an object changes its position in the HashSet. Objects within a HashSet should be made immutable or should be removed, changed and then re-added to the HashSet. Otherwise mutating objects within a HashSet, will result in the contains() method failing to find the object.

**Since objects are added in Comparable sort order when objects are inserted and not recalculated when the object is mutated, the sort order of the TreeSet maybe be incorrect if the object is mutated. Objects within a Treeset should be made immutable or should be removed, changed and then re-added to the TreeSet.

Queues[edit | edit source]

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 | edit source]

Comparison of Deques
LinkedList ArrayDeque
Description Doubly-linked list Dynamic-array based structure
  1. "Total order". Wikipedia. 2023-02-17. https://en.wikipedia.org/w/index.php?title=Total_order&oldid=1139875015.