nextfit

Next-fit, often written as next-fit, is an online heuristic used in the bin packing problem and in dynamic memory allocation. In bin packing, items with sizes are placed into fixed-capacity bins as a sequence is processed. The algorithm keeps a single open bin at a time: if the next item fits in the open bin, it is placed there; otherwise, the open bin is closed and a new bin is opened for that item. The process continues with the new bin being the open bin until it also fills.

Performance and characteristics: Next-fit runs in linear time O(n) with respect to the number of items and uses only constant extra space beyond the input data. Its worst-case competitive ratio is 2, meaning it can use up to twice the optimum number of bins in the worst case. A simple construction shows that each successive item can force the opening of a new bin, approaching the worst-case bound. In practice, next-fit is simple and fast but often uses more bins than first-fit or best-fit, particularly when item sizes vary widely.

In memory allocation, next-fit describes placing a memory request into the current free block if it fits; if not, the allocator advances to the next free block, optionally wrapping around to the beginning. This approach is easy to implement and fast, but it can lead to fragmentation and less efficient memory use compared with more selective strategies such as first-fit or best-fit.

History and relation: Next-fit is one of the classic online bin packing heuristics analyzed in competitive analysis and is commonly discussed alongside first-fit and best-fit. See also First-Fit, Best-Fit, and related heuristics.