# Other Collections

* They constitute one of the basic building blocks of commonly developed code
* Most use ArrayList as the default, but there are different collections which might be better suited for your needs
* Collections can be classified as ordered or unordered.
  * Ordered collections have a predictable iteration order;
  * unordered collections do not have a predictable iteration order
* Collections are sorted or unsorted.
  * The elements in a sorted collection are sequenced from start to end based on a comparator;
  * unsorted collections have no particular sequence based on elements
* ordered collections have a predictable iteration order but no sort order
* Sorted collections have a predictable sort order, hence they have a predictable iteration order.
* **all sorted collections are ordered collections, but not all ordered collections are sorted collections**
* Examples
  * List
    * is an interface for ordered collections with a stable indexing order
    * allows duplicate elements to be inserted and provide a predictable iteration order
    * implementations like ArrayList and LinkedList
    * To find a particular element, the contains method can be used.
      * The contains operation traverses the list from the beginning, hence finding elements in a List is an O(n) operation.
  * Map
    * is an interface that maintains key-to-value relationships, and retains only unique keys
    * If the same key and different value is added to a map, the old value is replaced by the new value.
    * implementations like
      * HashMap
        * unordered
        * rely on hashCode and equals to determine unique keys.
      * LinkedHashMap
        * ordered
        * rely on hashCode and equals to determine uniquekeys.
      * TreeMap
        * sorted: the keys are sorted according to a comparator or by the sort order of Comparable keys.
        * relies on compareTo to determine sort order and uniqueness of keys
    * To find a particular element, Map provides the containsKey and containsValue methods
      * HashMap, containsKey looks up the key in the internal hash table. If the look-up results in a non-null object, it is checked for equality with the object passed to containsKey.
      * The containsValue operation traverses all the values from the beginning.
      * Hence, finding keys in a HashMap is an O(1) operation, whereas finding values in a HashMap is an O(n) operation
  * Set
    * is an interface for collections of unique elements
    * sets are backed by maps where the keys are the elements and values are null
    * implementations like HashSet (backed by HashMap), LinkedHashSet (backed by LinkedHashMap), and TreeSet (backed by TreeMap).
    * The contains method on a Set delegates to containsKey of a Map and therefore is an O(1)
  *

Basic collections see

* https://docs.oracle.com/javase/tutorial/collections/implementations/index.html

## unmodifiable equivalents

## Linked list

## Linked list hash map

## Queues

* https://dzone.com/articles/the-developers-guide-to-collections-queues
* https://www.javamex.com/tutorials/synchronization\_concurrency\_8\_queues\_2.shtml

## Stacks

## Sets

* https://dzone.com/articles/the-developers-guide-to-collections-sets

## Collections

* https://dzone.com/articles/a-deep-dive-into-collections

## Vector

## choosing

* https://www.javamex.com/tutorials/collections/how\_to\_choose.shtml
* https://www.javamex.com/tutorials/collections/how\_to\_choose\_2.shtml
* https://stackoverflow.com/questions/21974361/which-java-collection-should-i-use/21974362#21974362

## Links

* https://www.java67.com/2013/08/ata-structures-in-java-programming-array-linked-list-map-set-stack-queue.html
* Java docs about Collections library: https://docs.oracle.com/javase/8/docs/technotes/guides/collections/designfaq.html
* https://www.journaldev.com/1260/collections-in-java-tutorial
* https://www.jrebel.com/blog/java-collections-cheat-sheet
* https://www.javamex.com/tutorials/collections/index.shtml
* https://www.geeksforgeeks.org/how-to-learn-java-collections-a-complete-guide/
* https://www.logicbig.com/tutorials/core-java-tutorial/java-collections/java-collection-cheatsheet.html
* https://youtu.be/hB6DoyX3eBo Return to Planet Collections by Maurice Naftalin
* https://youtu.be/aj6E0KF6sd4 Escape from the Planet of the Collections by Stuart Marks, Maurice Naftalin
