Cómo reemplazar una tupla en una lista ordenada de tuplas basándose en el primer valor de Python

Soy nuevo en Python y estoy buscando ayuda para resolver el siguiente problema

Necesito crear una lista ordenada de tuplas / diccionarios basándome en los datos proporcionados. Luego, cuando se proporcionan nuevos datos y tienen la misma primera clave, quiero reemplazar su valor por uno nuevo. Para ser más claro, daré un ejemplo ... Imagine que tengo datos, que se ven como sigue:

data = [(1, 100), (2, 200), (4, 400), (7, 900)]

Entonces tengo una nueva entrada del usuario, por ejemplo:

(4,500)

Entonces, ahora quiero reemplazar esta tupla con (4,400)esta con (4,500). Sé que las tuplas son inmutables, por lo que no quiero actualizar nada, solo borrar la anterior basándome en la clave (aquí: 4) y reemplazarla con una nueva tupla.

Hasta ahora utilicé una clase de otra pila que inserta cada nueva entrada (tupla) de forma ordenada en una lista de tuplas, y quiero que permanezca así, porque además necesito calcular el número más cercano más bajo y más alto al proporcionado uno en caso de que no esté en una lista.

Mi código se ve como sigue:

from bisect import bisect_left


class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

    def __len__(self):
        return len(self.it)

data = [(1, 100), (2, 200), (4, 400), (7, 900)]
data.sort(key=lambda c: c[0])

newcol = (3, 500)

bslindex = bisect_left(KeyWrapper(data, key=lambda c: c[0]), newcol[0])
data.insert(bslindex, newcol)

La salida tiene el siguiente aspecto:

[(1,100),(2,200),(3,500),(4,400),(7,900)]

Y proporcionando una nueva variable por ej. newcols2 = (3,600), basándome en el primer elemento de una tupla (aquí 3), quiero que se muestre como:

[(1,100),(2,200),(3,600),(4,400),(7,900)]