TAOCP 2.5 Exercise 35
The dynamic storage allocation methods of Section 2.
Section 2.5: Dynamic Storage Allocation
Exercise 35. [**] [22] Contrast the dynamic storage allocation methods of this section with the techniques for variable-size sequential lists discussed at the end of Section 2.2.2.
Verified: yes
Solve time: 1m08s
The dynamic storage allocation methods of Section 2.5 store list elements in a storage pool and connect them by links. Insertions and deletions therefore require only local changes of links, independent of the physical positions of the records in memory. Storage can be reused through allocation and deallocation, and lists may grow, shrink, split, or merge without moving large blocks of information.
The variable-size sequential lists of Section 2.2.2 store elements in contiguous memory locations. Access to the $k$th element is efficient because its address is determined directly from the base address, but insertions and deletions generally require moving many elements to preserve contiguity. Expansion is limited by the availability of adjacent free space, and compaction may be necessary when storage becomes fragmented. Thus sequential lists favor direct access, while the dynamic allocation methods of Section 2.5 favor flexibility of storage management and efficient structural modification.