Your data structure (a list of tuple) is best referred as an associative list. As other pointed out, it is probably better to use a dictionary as you'll get better amortized cost on operation (insertion, deletion, and lookup are O(1) for a dictionary, but deletion and lookup are O(n) for associative list).
Concerning updating your associative list by converting it to a dictionary, and then back to an associative list, this method has three drawbacks. It is quite expensive, it may change the order of the items, and it will remove duplicate.
If you want to keep using associative lists, it is probably better to just use a list comprehension to update the data structure. The cost will be O(n) in time and memory, but that's already what you have when using an intermediate dictionary.
Here's a simple way to do it (require Python 2.5 because it use the ternary operator):
def update_in_alist(alist, key, value):
return [(k,v) if (k != key) else (key, value) for (k, v) in alist]
def update_in_alist_inplace(alist, key, value):
alist[:] = update_in_alist(alist, key, value)
>>> update_in_alist([('a', 'hello'), ('b', 'world')], 'b', 'friend')
[('a', 'hello'), ('b', 'friend')]
