13.8: Conclusion

Dynamic data structures require dynamic storage allocation and reclamation. This may be accomplished by the programmer or may be done implicitly by a high-level language. It is important to understand the fundamentals of storage management because these techniques have significant impact on the behavior of programs.The basic idea is to keep a pool of memory elements that may be used to store components of dynamic data structures when needed.

Allocated storage may be returned to the pool when no longer needed. In this way, it may be used and reused. This contrasts sharply with static allocation, in which storage is dedicated for the use of static data structures. It cannot then be reclaimed for other uses, even when not needed for the static data structure. As a result, dynamic allocation makes it possible to solve larger problems that might otherwise be storage-limited.

Garbage collection and reference counters are two basic techniques for implementing storage management. Combinations of these techniques may also be designed. Explicit programmer control is also possible. Potential pitfalls of these techniques are garbage generation, dangling references, and fragmentation.

High-level language may take most of the burden for storage management from the programmer. The concept of pointers or pointer variables underlies the use of these facilities, and complex algorithms are required for their implementation.