自由串列（free list）

當你對某塊區塊呼叫 free() 時，配置器並不會立刻把那塊記憶體還給作業系統——那樣很慢，而且你很可能不久又會要記憶體。它反而保留該區塊、記住它可用，好讓下一次 malloc 能立即重用它。自由串列是配置器保留這些記憶體最簡單的方式：一個由目前閒置、可再次發放之區塊所組成的連結串列。

巧妙之處在這裡。配置器不需要任何額外儲存空間來建這份串列，因為閒置區塊本身是空的——沒人在用它們的內容。所以配置器把連結串列的下一個指標存進閒置區塊自己的記憶體裡。每個閒置區塊在它的前幾個位元組裡存著下一個閒置區塊的位址；它們一起串成一份串列。當你呼叫 malloc 時，配置器沿著這條鏈尋找一塊大到能滿足你請求的區塊，把它從串列中取下，回傳給你。當你呼叫 free 時，它把你的區塊重新接回串列。搜尋策略有名稱：first-fit（首次適配）取第一塊夠大的；best-fit（最佳適配）掃描找出仍裝得下的最小區塊，以減少浪費；這些是速度與碎片之間的取捨。

這是簡單配置器的概念核心，真實的配置器在此之上大幅精化——它們依尺寸級別分成多份自由串列以加快搜尋、為每塊保留描述用的標頭、並合併相鄰的閒置區塊。但你心中要握住的畫面是：閒置記憶體沒有消失，它停泊在一份串列上、穿過閒置區塊自身串接，等著被重用。這也是為什麼一個寫過已釋放區塊尾端的堆積緩衝區溢位能破壞配置器：它可能覆寫存在閒置區塊內的下一個指標，弄斷整條鏈。