code: def add(self, key):
          
          if key not in self._map:
              self._map[key] = link = _Link()
              root = self._root
              last = root.prev
              link.prev, link.next, link.key = last, root, key
              last.next = root.prev = weakref.proxy(link)
docs: Store new key in a new link at the end of the linked list