An array is sparse if most of its entries are null. A list L can be used
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 non null 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 non-null entries in A. Here is an array list ADT for your reference:size(), isEmpty(), get(i), set(i, e), add(i, e), and remove(i). Describe and analyze efficient ways of performing the methods of the array list ADT on such a representation. There is a trade-off between insertion and searching depending on whether the entries in L are sorted.
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser