I have a really succinct implementation for a persistent map with $$$O(log N)$$$ querying and (hopefully) $$$O(log N)$$$ amortized average-case insertion. Is this correct, or is the insertion actually $$$O(log^2 N)$$$?

I know there's the pathological case where if you keep doing insertion for the version of the LinkedList where the sum of dict sizes is a power of two, then you might end up repeatedly copying the whole dictionary. Let's say that's not the average case.

Also, for anyone unfamiliar -- Python dictionaries are hashmaps, so insertion/querying is amortized $$$O(1)$$$,

class LinkedList:
  parent: LinkedList | None
  curr_dict: dict[str, int]

def update(parent: LinkedList, key: str, value: int) -> LinkedList:
  curr_dict = {key: value}
  while parent.parent is not null and len(parent.curr_dict) <= len(curr_dict):
    curr_dict |= parent.curr_dict
    parent = parent.parent
  return LinkedList(parent=parent, curr_dict=curr_dict)

def query(node: LinkedList, key: str) -> int | None:
  while node is not None:
    if value := curr_dict.get(key)
      return value
    node = node.parent
  return None