Java Collections Overview

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

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

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

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

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

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

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

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.