在一开始，我们先用Virginia Tech的一段文字，对可利用空间表有一个初步的了解。

链表中节点的创建与删除方法，给了使用它的人一个简单而有效的管理内存的办法。Link类可以维护自己的可利用空间表，而不是频繁地调用new函数。一个可利用空间表存储着目前没有被使用的节点内存空间。当一个元素被从链表中释放的时候，它会被移至可利用空间表的头部。当把一个新元素插入链表中的时候，程序可以先检查可利用空间表中有没有可用的元素。如果有的话，会直接提取出那个元素；如果没有，再使用传统的new函数来申请一块空间。所以说，可利用空间表只是链表的一种应用。

对于周期性增减的链表来说，可利用空间表尤其有用。除非链表的大小达到空间上限，可利用空间表所需的空间就永远不会增加。当链表释放元素之后，对新元素的需求可以直接由可利用空间表来处理。当一个程序使用多个链表的时候，也不妨使用可利用空间表。这样，只要这几个链表不同时变长或变短，可利用空间表就可以让节点在链表之间转移（而非重复调用new和delete函数，无端地消耗时间）。

在下面的例子中，Link类增加了get和release函数。

弗吉尼亚理工大学的课程 数据结构与算法：可利用空间表

class Link<E> {      // 单链表节点，使用了可利用空间表
  private E e;       // 该节点的值
  private Link<E> n;    // 后继引用

  // 构造函数
  Link(E it, Link<E> inn) { e = it; n = inn; }
  Link(Link<E> inn) { e = null; n = inn; }

  E element() { return e; }                        // 返回节点的值
  E setElement(E it) { return e = it; }            // 修改节点的值
  Link<E> next() { return n; }                     // 返回后继引用
  Link<E> setNext(Link<E> inn) { return n = inn; } // 修改后继

  // 增加freelist支持
  private static Link freelist = null;                  // 该类的可利用空间表

  // 如果表中有可用节点，返回它
  static <E> Link<E> get(E it, Link<E> inn) {
    if (freelist == null)
      return new Link<E>(it, inn);                 // new一个link
    Link<E> temp = freelist;                       // 从freelist中取出
    freelist = freelist.next();
    temp.setElement(it);
    temp.setNext(inn);
    return temp;
  }

  // 将一个节点存入表中
  void release() {
    e = null;   // 取消对该节点的引用
    n = freelist;
    freelist = this;
  }
}

freelist变量的声明使用了static关键字。它可以创建一个由所有Link节点共用的对象。

请注意它有多么的简单，因为它们仅需要各自在表的前端移除或添加元素。可利用空间表的get和release函数的时间复杂度都为 Θ(1) ，除非表空了，必须调用new函数。为了适配可利用空间表版本的节点，我们要对链表类做一些必要的改动。

弗吉尼亚理工大学的课程 数据结构与算法：可利用空间表

  // 在当前位置插入“it”
  public boolean insert(E it) {
    curr.setNext(Link.get(curr.element(), curr.next())); // 得到link
    curr.setElement(it);
    if (tail == curr) tail = curr.next();    // 新的链表尾
    listSize++;
    return true;
  }

  // 将“it”推到链表中
  public boolean append(E it) {
    Link<E> temp = Link.get(null, null);
    tail.setNext(temp);
    tail.setElement(it);
    tail = tail.next();
    listSize++;
    return true;
  }

  // 将当前位置的元素移除并返回
  public E remove () {
    if (curr == tail) return null;          // 没有什么能移除的
    E it = curr.element();                  // 存储元素的值
    curr.setElement(curr.next().element()); // 将下一个元素往前移一位
    if (curr.next() == tail) tail = curr;   // 要是删除了链表尾元素，还需要修改表尾
    Link<E> tempptr = curr.next();          // 存储待删除节点的位置
    curr.setNext(curr.next().next());       // 修改前一位的指针，往后指一位
    tempptr.release();                      // 将待删除结点释放
    listSize--;                             // 链表长度-1
    return it;                              // 返回删除的节点值
  }

使用可利用空间表能够节省多长时间，取决于你用什么语言编写代码。对于C++这种语言，程序员必须使用new和delete函数来管理内存空间，从可利用空间表中取出节点只花费了使用new函数方法的不到十分之一时间。对于Java这种有垃圾清理的语言，最初似乎你使用可利用空间表不会节省多少时间，因为Java的new函数能够快速的从它的存储池中返回内存空间。然而，要是你不用可利用空间表，释放节点会产生垃圾，而这需要大量的回收垃圾的时间。

弗吉尼亚理工大学的课程 数据结构与算法：可利用空间表

仿照这种思路，我信心满满地在Clifford A. Shaffer的《数据结构与算法分析 第三版》链表实现线性表基础上，写成了一个可利用空间表类——很遗憾，这个并不能实现上述的多个链表之间共享节点的功能。嗯，坦白说，我并没有看懂前面的Java代码就开始上手写C++了。

需要特别注意的是，原书中的代码有一个问题：在moveToEnd()之后，curr指针指向的是tail，而输出的时候输出的是curr的后继的值。已经改正。

//freelist.h
#include <stack>
#include "list_adt.h"
using namespace std;
#ifndef LINK
#define LINK
template <typename E>
class Link //node的实现
{
public:
    E element;
    Link *next;
    Link(const E &elemval, Link *nextval = NULL)
    {
        element = elemval;
        next = nextval;
    }
    Link(Link *nextval = NULL)
    {
        next = nextval;
    }
};
#endif
#ifndef FREELIST_H
#define FREELIST_H
template <typename E>
class Freelist : public List<E>
{
private:
    stack<Link<E> *> spareElem; //存放暂时不用的元素地址
    Link<E> *head;              //头指针
    Link<E> *tail;              //尾指针
    Link<E> *curr;              //当前位置的前驱节点
    int cnt;
    Link<E> *getNewElem() //获取一个新元素的地址
    {
        Link<E> *temp;
        if (spareElem.empty()) //可利用空间表中无元素
        {
            temp = new Link<E>;
        }
        else //还有元素，可以直接传过来地址
        {
            temp = spareElem.top();
            spareElem.pop();
        }
        return temp;
    }
    void init() //初始化链表，只有一个head元素
    {
        curr = tail = head = getNewElem();
        cnt = 0;
    }
    void removeall() //清空链表
    {
        while (head != NULL)
        {
            curr = head;
            head = head->next;
            spareElem.push(curr);
        }
    }

public:
    Freelist(int size = 65536)
    {
        init();
    }
    ~Freelist()
    {
        removeall();
    }
    void clear() //清空链表并初始化
    {
        removeall();
        init();
    }
    void insert(const E &it) //插入元素
    {
        curr->next = getNewElem();
        curr->next->element = it;
        tail->next->next = NULL;
        if (tail == curr)
        {
            tail = curr->next;
        }
        cnt++;
    }
    void append(const E &it) //在最后添加元素
    {
        tail->next = getNewElem();
        tail->next->element = it;
        tail->next->next = NULL;
        tail = tail->next;
        cnt++;
    }
    E remove() //删除当前位置的元素
    {
        E it = curr->next->element;
        Link<E> *ltemp = curr->next;
        if (tail == curr->next)
        {
            tail = curr;
        }
        curr->next = curr->next->next;
        spareElem.push(ltemp);
        cnt--;
        return it;
    }
    void moveToStart() //移至头部
    {
        curr = head;
    }
    void moveToEnd() //移至尾部
    {
        curr = tail;
        prev(); //curr最后必须是tail的前驱才行
    }
    void prev() //左移一位
    {
        if (curr == head)
        {
            return;
        }
        Link<E> *temp = head;
        while (temp->next != curr)
        {
            temp = temp->next;
        }
        curr = temp;
    }
    void next() //右移一位
    {
        if (curr != tail)
        {
            curr = curr->next;
        }
    }
    int length() const //返回长度
    {
        return cnt;
    }
    int currPos() const //返回当前位置
    {
        Link<E> *temp = head;
        int i = 1;
        for (i = 0; curr != temp; i++)
        {
            temp = temp->next;
        }
        return i;
    }
    void moveToPos(int pos) //移动至指定位置
    {
        //Assert((pos>=0)&&(pos<=cnt),"Position Out of Range");
        curr = head;
        for (int i = 0; i < pos; i++)
        {
            curr = curr->next;
        }
    }
    const E &getValue() const //返回当前位置的值
    {
        //Assert(curr->next!=NULL,"No Value");
        return curr->next->element;
    }
};
#endif

为了探究可利用空间表的效果，我写了一段程序进行推入、清空，再推入的操作，并测定运行时间。

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include "freelist.h"
#include "linklist.h"
using namespace std;

int main()
{
    printf("=============LINKLIST============\n");
    LList<int> l;
    srand(time(NULL));
    clock_t stage1, stage2, stage3;
    stage1 = clock();
    for (int i = 0; i < 10000000; i++)
    {
        l.append(0);
    }
    while (!l.empty()) //这里将链表全部清空
    {
        l.moveToStart();
        l.remove();
    }
    stage2 = clock();
    for (int i = 0; i < 10000000; i++)
    {
        l.append(rand());
    }
    stage3 = clock();
    double dur1, dur2;
    dur1 = (stage2 - stage1) * 1.0 / CLOCKS_PER_SEC;
    dur2 = (stage3 - stage2) * 1.0 / CLOCKS_PER_SEC;
    printf("Append & Clear Consumption:%lf\nRe-append Consumption:%lf\n", dur1, dur2);
    printf("=============FREELIST============\n");
    Freelist<int> f;
    srand(time(NULL));
    stage1 = clock();
    for (int i = 0; i < 10000000; i++)
    {
        f.append(0);
    }
    while (!f.empty())
    {
        f.moveToStart();
        f.remove();
    }
    stage2 = clock();
    for (int i = 0; i < 10000000; i++)
    {
        f.append(rand());
    }
    stage3 = clock();
    dur1 = (stage2 - stage1) * 1.0 / CLOCKS_PER_SEC;
    dur2 = (stage3 - stage2) * 1.0 / CLOCKS_PER_SEC;
    printf("Append & Clear Consumption:%lf\nRe-append Consumption:%lf\n", dur1, dur2);
}

这篇文章到这里似乎就结束了？并没有，你看到滚动条就会发现不对劲。结果很尴尬，这样的可利用空间表，比普通的链表还要慢上不少……这次甚至还是最快的结果。

就这样把这个问题搁了好几天，我突然想到了原因。在将元素推进可利用空间表的时候，STL <stack>需要再new一个Link指针，指向原来的空间；推出的时候，也需要类似于delete的操作——这样，不仅没有省下new和delete的时间，反而徒增了赋值的时间代价。虽然我也不明白，为什么会慢这么多……

下面我画了2张图，以删除节点为例，来描述我的前后两种理解。

我还意识到，闲置的结点，实际上是可以自行重新连接成链的，只需要维护一个栈顶指针即可。这样就不需要再new空间了。

少废话，上代码。

//freelist.h
#include "list_adt.h"
#include <stack>
using namespace std;
#ifndef LINK
#define LINK
template <typename E>
class Link //node的实现
{
public:
    E element;
    Link *next;
    Link(const E &elemval, Link *nextval = NULL)
    {
        element = elemval;
        next = nextval;
    }
    Link(Link *nextval = NULL)
    {
        next = nextval;
    }
};
#endif
#ifndef FREELIST_H
#define FREELIST_H
template <typename E>
class Freelist : public List<E>
{
private:
    Link<E> *freelist = nullptr; //可利用空间表的栈顶指针
    Link<E> *head;               //头指针
    Link<E> *tail;               //尾指针
    Link<E> *curr;               //当前位置的前驱节点
    int cnt;
    Link<E> *getNewElem() //获取一个新元素的地址
    {
        if (freelist == nullptr) //空的
        {
            return new Link<E>;
        }
        else
        {
            Link<E> *temp = freelist;
            freelist = freelist->next;
            return temp;
        }
    }
    void abandonElem(Link<E> *tgt)//将一个元素移至可利用空间表中
    {
        tgt->next = freelist;
        freelist = tgt;
    }
    void init() //初始化链表，只有一个head元素
    {
        curr = tail = head = getNewElem();
        cnt = 0;
    }
    void removeall() //清空链表
    {
        while (head != NULL)
        {
            curr = head;
            head = head->next;
            abandonElem(curr);
        }
    }

public:
    Freelist(int size = 65536)
    {
        init();
    }
    ~Freelist()
    {
        removeall();
        Link<E> *temp;
        while (freelist != nullptr) //程序结束的时候析构，要把没有利用的结点也全都释放掉
        {
            temp = freelist;
            freelist = freelist->next;
            delete temp;
        }
    }
    void clear() //清空链表并初始化
    {
        removeall();
        init();
    }
    bool empty()
    {
        if (head == tail)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    void insert(const E &it) //插入元素
    {
        curr->next = getNewElem();
        curr->next->element = it;
        tail->next->next = NULL;
        if (tail == curr)
        {
            tail = curr->next;
        }
        cnt++;
    }
    void append(const E &it) //在最后添加元素
    {
        tail->next = getNewElem();
        tail->next->element = it;
        tail->next->next = NULL;
        tail = tail->next;
        cnt++;
    }
    E remove() //删除当前位置的元素
    {
        E it = curr->next->element;
        Link<E> *ltemp = curr->next;
        if (tail == curr->next)
        {
            tail = curr;
        }
        curr->next = curr->next->next;
        abandonElem(ltemp);
        cnt--;
        return it;
    }
    void moveToStart() //移至头部
    {
        curr = head;
    }
    void moveToEnd() //移至尾部
    {
        curr = tail;
        prev(); //curr最后必须是tail的前驱才行
    }
    void prev() //左移一位
    {
        if (curr == head)
        {
            return;
        }
        Link<E> *temp = head;
        while (temp->next != curr)
        {
            temp = temp->next;
        }
        curr = temp;
    }
    void next() //右移一位
    {
        if (curr != tail)
        {
            curr = curr->next;
        }
    }
    int length() const //返回长度
    {
        return cnt;
    }
    int currPos() const //返回当前位置
    {
        Link<E> *temp = head;
        int i = 1;
        for (i = 0; curr != temp; i++)
        {
            temp = temp->next;
        }
        return i;
    }
    void moveToPos(int pos) //移动至指定位置
    {
        //Assert((pos>=0)&&(pos<=cnt),"Position Out of Range");
        curr = head;
        for (int i = 0; i < pos; i++)
        {
            curr = curr->next;
        }
    }
    const E &getValue() const //返回当前位置的值
    {
        //Assert(curr->next!=NULL,"No Value");
        return curr->next->element;
    }
};
#endif

时间很喜人。在Windows下，时间对比如图，可以看到可利用空间表用时大幅度领先：

而在Linux（Ubuntu 20.04.2，WSL2）下，优势都小了一些，但是重新添加元素过程的优势仍然十分明显。