Being mutable, when a Python list is extended (e.g., mylist.extend() or mylist += anotherlist), the id of the list does not change.
I understand that (at least in CPython) lists are contiguous in memory (and the id happens to be the address of the head of the list). What if the memory after the list is already highly fragmented and the list extension cannot be allocated (even though there's plenty of free space, albeit discontiguous in that area)? Does the allocation fail? How is that mitigated?
In CPython, this is a difference in the way lists and tuples are allocated. For a list, the object contains a pointer to the memory allocated for the list contents. The list object proper is small, and never needs to move; the address of the vector it points to may change any number of times.
For a tuple object, which is expected to be small most times, the memory for the tuple content is indeed allocated directly in the tuple object. But tuples can't be resized, so your scenario can't arise in that case.