python vs java data structures

TODO

operations average O(1) unless specified

template

• init
• add
• get
• remove
• check
• iterate
• increment
• sort
• specialty
• implementation

---

dictionary / maps

python

• `dict
  • init
    • d = {}
    • d = dict()
  • adding values
    • dict[key] = value
  • getting values
    • get(key, default_val)
    • d[key]
      • keyerror if not exist
  • removing values
    • val = d.pop(key)
      • key error if not exist
    • del d[key]
  • check existence
    • if key in d
  • iterate k
    • for k in d
  • iterate v
    • for v in d.values()
  • iterate item
    • for k,v in d.items()
  • increment
    • d[k] += 1
  • sort
    • sorted(d.items())
    • sorted(d.items(), key=lambda x:x[1])
      • key accepts a function which gets applied to every iterable element (return val is used for comparison)
      • lambda creates small functions
      • lambda x: defines a function with a single arg x
      • ^ sorts list based on second element of the tuple
    • O(nlogn)
  • use for
    • frequency map
    • prefix-sum cache

java

• HashMap

  • init
    • Map<K,V> map = new HashMap<>()
  • adding values
    • map.put(key, value)
  • getting values
    • get(k)
    • getOrDefault(k, default)
  • removing values
    • map.remove(k)
  • check existence
    • if (map.containsKey(key))
  • iterate k
    • for (K k : map.keySet())
  • iterate v
    • for (V v : map.values())
  • iterate item
    • for (Map.Entry<K,V> e : map.entrySet())
  • increment
    • map.put(key, map.getOrDefault(key,0) + 1)
  • sort
    • map.entrySet().stream().sorted(Map.Entry.comparingByKey())
  • specialty
    • average O(1) retrieval
  • implementation
    • TODO

• TreeMap<Type>

  • specialty
    • Sorted by key
    • TODO

lists / arraylists

java

• init
  • List<T> l = new ArrayList<>()
• add
  • list.add(val)
    • amortized O(1)
• insert at index
  • list.insert(i, val)
    • O(n)
• get
  • list.get(val)
• remove by value
  • list.remove(val)
• pop end
  • list.remove(list.size()-1)
• iterate
  • for (int x : arr)
• length
  • list.size()
• sort ascending
  • Collections.sort(list);
    • O(nlogn)
• sorted copy
  • list.stream().sorted().toList()
    • nlogn
• Reverse
  • Collections.reverse(list)
    • O(n)
• Slice
  • list.subList(a,b)
    • O(k)
• specialty
  • expands
• convert to array
  • list.toArray(new T[0])
  • list.toArray()
    • requires object casting
  • list.stream().mapToInt(Integer::intValue).toArray()
    • todo
• convert from array
  • List<T> l = Arrays.asList(arr)
• implementation
  • todo

python

grouping values

python

• tuples (a,b)

java

• Pair