VersionControlSystem

There are a few ways:

• LinkedList + Hash: Map (fileId: File) with previousFile: Filein the File for previous version

  • Time complexity:
    • $O(1)$ for removal and add
    • $O(n)$ for searching
  • Improvement could be Skip List but increase complexity
  • Store less file in our Cache

• Map (fileId: File) with static previousVersion: LinkedHashMap {version: File} in File for previous version across all files

  • Time complexity :
    • $O(1)$ for removal and Add
    • $O(1)$ for searching
  • Concurrency could be a problem since there is only Synchronised library
  • However version are not sorted
    >[!note]
    NOTE try to avoid this one because if we need to store the latest version, LinkedHashMap would not have the latest key API

• Map (fileId: File) with static previousVersion: TreeMap {version: File} for File for previous version accross all files

  • Time complexity:
    • $O(logn)$ for everything
  • Can use ConcurrentSkipListMap however will also be $O(logn)$
  • Versions are sorted
  • Recommended because it support a lot of api, last entry, tailMap, etc