Problem

1. Describe a scheme for creating list iterators that fail fast, that is, they all become invalid as soon as the underlying list changes.

2. An array is sparse if most of its entries are null. A list L can be used to implement such an array, A, efficiently. In particular, for each nonnull cell A[i], we can store an entry (i, e) in L, where e is the element stored at A[i]. This approach allows us to represent A using O(m) storage, where m is the number of nonnull entries in A. Describe and analyze efficient ways of performing the methods of the array list ADT on such a representation. Is it better to store the entries in L by increasing indices or not?