Exercises

1. In the sparse array representation used in this chapter, the linked lists are always kept in order by index. Keeping these lists in order requires a small amount of extra work during insertion, but can also save work during lookup. Discuss the tradeoffs between keeping the lists ordered versus unordered. List any situations you can imagine where one or the other method is troublesome or inefficient.
2. Devise an efficient algorithm that finds the intersection of two ordered linked lists (i.e. the list of values that appear in both lists) and prints it in order. The algorithm must visit each node in both lists at most once.

   Hint- consider the use of a cursor.

3. In many contexts, it is appropriate for uninitialized elements of a sparse array to be treated as having an undefined value, instead of having the default value. In such an array, for example, using saGet on an element that hadn't been assigned a value with saSet would be considered an error. What changes (if any) to the sa library would be necessary to implement this behavior?
4. Implement a library, similar to sa, that implements three-dimensional sparse arrays.
5. As mentioned in section 3.5, some of the sa code could be rewritten in a much better manner, with a cleaner and more abstract interface. Starting with the current sa library, define a cleaner interface for sparse arrays, and implement the corresponding library. Be sure to include cursors in your library.