An array is sparse if most of its entries are null. A list L

Authors:

Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

Chapter:

List And Iterator Adts

Exercise:

Exercises

Question:47 | ISBN:9781118771334 | Edition: 6

Question

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 a pair (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