Collections Framework in Java - (In Progress)

• Excerpt from Wikipedia

  • Abstract Data Type(ADT) - Serves the logical form of the data type - Conceptual idea, semantics, operations - user view
  • Few of the common ADT’s are
    • List/Sequence
    • Set
    • Map/Associative Array/Dictionary
    • Stack - LIFO - Has top of the stack - operations - push(), peek(), pop()
    • Queue - FIFO - Has head and tail - operations - offer(), peek(), poll()
    • Deque
    • PriorityQueue
    • Graph
    • Tree

  ---

  • Data structure - Implements the physical form of the data type - talks about internal implementation of ADT - programmers view
    • Array - Contiguous memory allocation of elements
    • LinkedList - Each node is an object that is stored at memory. All nodes are scattered across memory but, all are linked with references.
    • record/struct
    • HashTable - Read my post: Overview of HashTable implementation
    • Heap/Binary Heap - Specialized tree-based data structure satisfying the heap property(Min-Heap property or Max-Heap property)
      • Often used to implement PriorityQueues for Min-Heap, Max-Heap
      • Read Binary Heap
      • Worst case time complexity of operations
        • insert - O(log n)
        • Find-min - O(1)
        • Delete-min - O(log n)

• Think of an ADT as an interface and data structure as an interface(ADT) implementation

List, Queue, and Set

---

Map

---

Summary of frequently used Collections

---

Summary of Queue Methods

	Throws Exception Fail fast Operation	Return special value often (true/false) Fail safe Operation
Insert	add(e)	offer(e)
Remove	remove()	poll()
Examine	element()	peek()

Priority Queue

• Priority Queue is an ADT that is implemented by Heap/Binary-Heap Data Structure.
• By default, it stores the data as Min-Heap.
  • Note: The Min-Heap doesn’t mean the underlying storage array is sorted in natural ordered.
  • Given an array, how a Min-Heap and Max-Heap data structure is created is shown below theoritically.
• Does not permit null elements because it expects the elements to implement Comparable or Comparator so that they are compared and placed in Binary heap structure.
• Youtube video: Heap as Tree to Heap as Array

---

• Topics pertinent to Collections Framework in Java
  • java.lang.Comparable vs java.util.Comparator
    • public int compareTo(T o); vs int compare(T o1, T o2);
  • equals() and hashCode() contract
  • java.util.Collections static utility class
  • java.util.ConcurrentModificationException use-cases
  • java.lang.UnsupportedOperationExpcetion use-cases
  • External iteration(iterator and classic for loop, while loop, imperative way) vs internal iteration(for-each, declarative)
  • java.util.Iterator vs java.util.ListIterator
  • Generics in Java - Purpose, Type erasure
  • Capacity vs Size in java.util.ArrayList
  • Failfast vs Failsafe Collections
  • Synchronized vs Concurrent collections
  • java.util.Vector vs java.util.ArrayList
  • java.util.concurrent.CopyOnWriteArrayList, java.util.concurrent.ConcurrentHashMap - More reads, less/occasional writes
  • java.util.Collections.synchronizedList(List<Object> list), java.util.Collections.synchronizedMap(Map<K,V> m) VS java.util.concurrent.CopyOnWriteArrayList, java.util.concurrent.ConcurrentHashMap
  • java.util.Hashtable vs java.util.HashMap
  • java.util.Stack(LIFO, Synchronized) vs java.util.Deque(LIFO + FIFO)
  • java.util.PriorityQueue
  • java.util.concurrent.BlockingQueue
    • java.util.concurrent.PriorityBlockingQueue
    • java.util.concurrent.SynchronousQueue
  • java.util.Collections.emptyList() vs java.util.Collections.emptyMap() vs java.util.Collections.emptySet()

---

PS: Will add little more details. Discussion/Comments will be enabled for this post after it’s updated with details.