Experiments

5 min read

Imports

Java Collections Hierarchy

Java-Collections-Framework-Hierarchy

Data Structures

Static

  • Array
    • cpp: int arr[10]
    • java: int[] arr = new int[10]

Dynamic

  • Vector
    • ArrayList (avoid Vector legacy class)
  • Stack
    • ArrayDeque (avoid Stack legacy class)
  • Queue
    • ArrayDeque
  • Priority Queue
    • PriorityQueue
  • Deque
    • ArrayDeque
  • Linked List (Doubly Linked List — Avoid its use it is not much performant and useful)
    • LinkedList

Associative

  • Set
    • Sorted: TreeSet
    • Unordered: HashSet
    • Keep Insertion Order: LinkedHashSet
  • Map
    • Sorted: TreeMap
    • Unordered: HashMap
    • Keep Insertion Order: LinkedHashMap

Size of Data structures

  • Static Arrays:
    • length — property
  • Strings:
    • length()
  • Collections:
    • size()

Obsolete Data structures

References

HashMap vs TreeMap vs LinkedHashMap

  • The following is true for corresponding HashSet, TreeSet and LinkedHashSet as well
  • HashMap: unordered keys
    • based on Hash table
    • O(1) get / put / remove / containsKey
  • TreeMap: sorted keys
    • based on Red-black tree
    • O(logN) get / put / remove / containsKey
  • LinkedHashMap: keep insertion order
    • based on Hash table and linked list
    • O(1) get / put / remove / containsKey
    • takes more memory compared to HashMap

HashMap

  • Syntax
Map<String, Integer> map = new HashMap<>(initialCapacity, loadFactor);

TreeMap

  • Syntax
// using map interface
Map<String, Integer> map = new TreeMap<>();
 
// using NavigableMap or TreeMap if special methods needed
NavigableMap<String, Integer> map = new TreeMap<>();
TreeMap<String, Integer> map = new TreeMap<>();
 
// reverse sorted map
Map<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
 
// custom in-line ordering
Map<String, Integer> map = new TreeMap<>((o1, o2) -> o2.compareTo(o1));
  • Special Methods
    • headMap(endkey)
      • portion of map where key < endkey for all keys
      • optional param: inclusive
    • tailMap(endkey)
      • portion of map where startKey <= key for all keys
      • optional param: inclusive
    • subMap(startKey, endKey)
      • portion of map where startKey <= key < endKey for all keys
      • optional params: fromInclusive, toInclusive
    • descendingMap() or reversed()
      • reverse sorted map
      • Both are equivalent
  • Special methods for finding Key (corresponding Entry methods are also available)
    • firstKey() — lowest key if exists else error
    • lastKey() — highest key if it exists else error
    • lowerKey(baseKey): key < baseKey
    • higherKey(baseKey): baseKey < key
    • floorKey(baseKey): key <= baseKey
    • ceilingKey(baseKey): baseKey <= key

LinkedHashMap

  • Syntax
Map<String, Integer> map =
                new LinkedHashMap<>(initialCapacity, loadFactor, accessOrder);
  • Can be configured to follow insertion order or access order
    • accessOrder = false (default)
      • follows insertion order
    • accessOrder = true
      • follows access order
      • Least Recently Used (Head) ------------> Most Recently Used (Tail)
      • Whenever access happens key goes to the end of the LinkedHashMap
  • Special Methods
    • reversed()
      • reverse ordered map

ArrayDeque

  • Syntax
Deque<Integer> q = new ArrayDeque<>();
  • Deque interface has lot of methods
  • Using as Stack (LIFO)
    • push()
      • Throws IllegalStateException if full (Not Applicable)
    • pop()
      • Returns top element and can be cast implicitly to primitive type (auto unboxing) safely if required
      • Throws NoSuchElementException if empty
    • peek()
      • Returns null if empty
  • Using as Queue (FIFO)
    • offerFirst()
    • offerLast() or offer()
      • Return true if success else false
    • pollFirst() or poll()
      • Returns element or null if empty
    • pollLast()
    • peekFirst() or peek()
      • Returns element or null if empty
    • peekLast()
    • Other methods which throws exception
      • These are useful in capacity-restricted queues
      • addFirst()
      • addLast() or add()
        • Throws IllegalStateException if full (Not Applicable)
      • removeFirst() or remove()
        • Returns top element and can be cast implicitly to primitive type (auto unboxing) safely if required
        • Throws NoSuchElementException if empty
      • removeLast()
      • getFirst() or element()
        • Throws NoSuchElementException if empty
      • getLast()
  • Interviews
    • For Algo/OA round: use add(), remove(), getFirst()
      • They fail-fast and help you debug code faster???
      • getFirst() is more modern compared to element() which is ambiguous
      • I would say why to even think about them, try to have offer/poll in muscle memory instead???
    • Multi-Threading : use offer(), poll(), peek()
    • LLD/HLD: use offer(), poll(), peek()
// CASE A: Standard Algorithmic Problem (BFS, Tree Traversal, Dijkstra)
Deque<Integer> q = new ArrayDeque<>();
q.add(10);
 
while (!q.isEmpty()) {
    // Fails fast if you made a logic error
    // primitive casting possible
    int val = q.remove(); 
 
    System.out.println(val);
}
 
// CASE B: Designing a System Component (e.g. In-Memory Message Broker)
Deque<Integer> q = new ArrayDeque<>();
q.offer(10); // add element
 
while (true) {
    // Returns null if empty
    Integer nextVal = q.peek();
    
    if (nextVal == null) {
        break; // Exit cleanly if queue is empty
    }
    
    // Returns null if empty
    Integer current = q.poll(); 
    if (current != null) {
        process(current);
    }
}

PriorityQueue

  • Syntax
// min priority queue
Queue<Integer> pq = new PriorityQueue<>();
 
// max priority queue
Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
 
// custom in-line logic
Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
  • Queue interface methods
    • offer()
    • poll()
    • peek()
    • Other methods which throws exception
      • These are useful in capacity-restricted queues
      • add()
      • remove()
  • PriorityQueue is unbounded
    • add() or offer() are practically same
    • remove() will throw an exception if the queue is empty, while poll() returns null

Enum

  • EnumSet
    • Set implementation where it can only take enums as elements
  • EnumMap
    • Map implementation where key can only take enums

Swap method