Sequential Memory Allocation and Dynamic List Management

Key Insight

The simplest method for storing a linear list is sequential allocation, placing list items in consecutive memory locations. If each node occupies 'c' words, the location of node X[j+1] is LOC(X[j]) + c, meaning X[j]'s location is L0 + j * c, where L0 is a base address. Understanding the capabilities and limitations of this technique is crucial. For stacks, sequential allocation is highly convenient: a stack pointer 'T' tracks the top element. An empty stack sets T=0. To add element 'Y', T becomes T+c, and CONTENTS(T) is Y. To delete, Y becomes CONTENTS(T), and T becomes T-c.

Sequentially implementing queues or general deques is more complex. A naive approach uses front (F) and rear (R) pointers, both 0 when empty. Insertion at the rear is R ← R+c; CONTENTS(R) ← Y. Removal from the front is Y ← CONTENTS(F+c); F ← F+c. However, this leads to memory overruns as R continually advances, wasting space unless F regularly 'catches up' to R. A solution is to use a fixed memory block of M nodes (X[1]...X[M]) configured circularly, where X[1] logically follows X[M]. Insertion then becomes R ← (R mod (Mc)) + c, and deletion F ← (F mod (Mc)) + c, simulating a continuous circular buffer, similar to input-output buffering.

Practical sequential allocation must account for 'UNDERFLOW' (attempting to remove a nonexistent item, often a program control signal) and 'OVERFLOW' (memory full, more data to store, usually an error). For multiple variable-size lists, simply assigning maximum sizes is inefficient due to unpredictable growth. A common strategy for two lists is to have them grow towards each other from opposite ends of a memory block, preventing overflow until total space is exhausted. However, for three or more lists, this simple model fails if bottom elements require fixed locations. Dynamic relocation of base addresses becomes necessary, introducing a slight performance overhead for relative addressing. Advanced strategies, like Garwick's algorithm, dynamically 'repack memory' during overflow events for multiple stacks, reallocating space based on each stack's size changes, involving complex data shifting (Algorithm R) to preserve information.