13.4: Shared Storage

When components of data structures are identical and require significant amounts of storage, it is only natural to attempt to avoid component replication. This means that identical components will all share the same storage, so references to each will always be to the same place. As an example, consider Figure 13.6. The two list-structures ls1 and ls2 share a common sublist. As a result, p1, p3, and p4 point to the shared sublist.

Figure 13.6 A Shared Sublist

As usual, what we gain in one area we pay for in another. Here, storage is saved, but the price is paid in more complex processing. In particular, suppose the sublist pointed to by p3 is to be deleted from ls2 by setting p3 to null. Since p1 and p4 still point to it, it is not valid to return its records' storage to the list of available space, as would be the case without sharing. Deciding when and how to reclaim deleted records or sublists by insertion on the list of available space requires more sophisticated reclamation algorithms than those of Chapter 3.