__datastructures

Imports

• java.util.*
• java.lang — Auto imported
• import java.util.stream.* — for streams
• YouTube: Know your Java

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

• Vector: synchronizes on each operation
  • alternatives: CopyOnWriteArrayList or Collections.synchronizedList()
• Stack: synchronizes on each operation
• Hashtable: synchronizes on each operation
  • alternatives: ConcurrentHashMap or Collections.synchronizedMap()
• https://stackoverflow.com/questions/40471/what-are-the-differences-between-a-hashmap-and-a-hashtable-in-java

References

• Use ArrayDeque for Stack, Queue, Deque in java:
  • https://leetcode.com/discuss/explore/queue-stack/523448/one-who-chose-java-should-always-use-arraydeque-for-their-stacks-and-queues-best-performance
  • https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated
  • Vector synchronizes on each individual operation. Generally you want to synchronize a whole sequence of operations. Hence it is inefficient
• LinkedList is a doubly linked list and is different from queue
  • although you will think that removal by object reference is O(1) but that is not the case with LinkedList since it does not expose Node object (which contains prev/next references) hence object is searched making its complexity O(N)
  • https://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist-in-java
• Programming environments in leetcode
  • https://support.leetcode.com/hc/en-us/articles/360011833974-What-are-the-environments-for-the-programming-languages

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

• Using as Stack
  • peek()
  • push()
  • pop()
• Using as Queue
  • offerLast() or offer()
  • offerFirst()
  • pollLast()
  • pollFirst() or poll()
  • peekFirst() or peek()
  • peekLast()
  • Other methods which throws exception
    • These are useful in capacity-restricted queues
    • addFirst() / addLast() / add()
    • removeFirst() / removeLast() / remove()
    • getFirst() / getLast()
  • Generally preferable to use offer() over add()

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));

• methods
  • add() or remove()
  • peek()
  • Other methods which throws exception
    • These are useful in capacity-restricted queues
    • offer() or poll()

Enum

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

Swap method

• In java swapping of variables can be done using temporary variable
• But it is not possible to write that logic in a separate method, since references will be copied to the new variable
• https://www.baeldung.com/java-swap-two-variables