10. 空闲链表¶
10.1. 空闲链表¶
new 运算符的使用代价相对高昂，垃圾回收同样昂贵。
Memory Management
处理的是通用性的内存请求。
代价高昂的原因在于：
自由存储区 例程必须能够
处理进出自由存储区时毫无特定模式可言的请求，
以及大小差异悬殊的内存请求。
这一点，再加上垃圾回收器释放空间的不可预测性，
使得它们与针对更受控的内存访问模式而专门实现的方案相比效率低下。
在 链表 实现中，
结点的创建与删除方式，
使得 Link 类的程序员可以提供简单而高效的内存管理例程。
Link 类可以自己管理一个 空闲链表 ，
而不必反复调用 new 。
空闲链表保存那些当前未在使用的线性表结点。
从链表中删除一个结点时，该结点被放到空闲链表的表头。
要向链表添加新元素时，
先检查空闲链表中是否有可用的线性表结点；
如果有，就从空闲链表中取出该结点；
如果空闲链表为空，才必须调用标准的 new 运算符。
由此可见，空闲链表不过是
链式栈 的一个应用。
对于周期性地增长、随后又收缩的链表，空闲链表特别有用。 空闲链表绝不会超过链表至今达到过的最大规模。 链表收缩之后，对新增结点的请求就可以由空闲链表来满足。 程序使用多个链表时，也是使用空闲链表的良机。 只要这些链表不会同时增长和收缩， 空闲链表就能让链接结点在各链表之间流动。
在下面给出的实现中，
Link 类增加了 get 和 release 两个方法。 [1]
class Link { // Singly linked list node with freelist support
private Object e; // Value for this node
private Link n; // Point to next node in list
// Constructors
Link(Object it, Link inn) { e = it; n = inn; }
Link(Link inn) { e = null; n = inn; }
Object element() { return e; } // Return the value
Object setElement(Object it) { return e = it; } // Set element value
Link next() { return n; } // Return next link
Link setNext(Link inn) { return n = inn; } // Set next link
// Extensions to support freelists
static Link freelist = null; // Freelist for the class
// Return a new link, from freelist if possible
static Link get(Object it, Link inn) {
if (freelist == null)
return new Link(it, inn); // Get from "new"
Link temp = freelist; // Get from freelist
freelist = freelist.next();
temp.setElement(it);
temp.setNext(inn);
return temp;
}
// Return a link node to the freelist
void release() {
e = null; // Drop reference to the element
n = freelist;
freelist = this;
}
}
class Link<E> { // Singly linked list node with freelist support
private E e; // Value for this node
private Link<E> n; // Point to next node in list
// Constructors
Link(E it, Link<E> inn) { e = it; n = inn; }
Link(Link<E> inn) { e = null; n = inn; }
E element() { return e; } // Return the value
E setElement(E it) { return e = it; } // Set element value
Link<E> next() { return n; } // Return next link
Link<E> setNext(Link<E> inn) { return n = inn; } // Set next link
// Extensions to support freelists
private static Link freelist = null; // Freelist for the class
// Return a new link, from freelist if possible
static <E> Link<E> get(E it, Link<E> inn) {
if (freelist == null) {
return new Link<E>(it, inn); // Get from "new"
}
Link<E> temp = freelist; // Get from freelist
freelist = freelist.next();
temp.setElement(it);
temp.setNext(inn);
return temp;
}
// Return a link node to the freelist
void release() {
e = null; // Drop reference to the element
n = freelist;
freelist = this;
}
}
freelist 变量的声明使用了 static 关键字。
这会创建一个由所有 Link 结点实例共享的单一变量。
这样，所有 Link 结点就共享同一个空闲链表。
注意这两个方法是多么简单：
它们分别只需从空闲链表的前端移除和添加一个元素。
空闲链表方法 get 和 release 都在 \(\Theta(1)\) 时间内运行，
唯一的例外是空闲链表已耗尽而必须调用 new 操作的情形。
下面是为了使用空闲链表版本的链接类，
而对链表类的成员所做的必要修改。
// Insert "it" at current position
public boolean insert(Object it) {
curr.setNext(Link.get(curr.element(), curr.next())); // Get link
curr.setElement(it);
if (tail == curr) tail = curr.next(); // New tail
listSize++;
return true;
}
// Append "it" to list
public boolean append(Object it) {
tail.setNext(Link.get(null, null));
tail.setElement(it);
tail = tail.next();
listSize++;
return true;
}
// Remove and return current element
public Object remove () {
if (curr == tail) return null; // Nothing to remove
Object it = curr.element(); // Remember value
curr.setElement(curr.next().element()); // Pull forward the next element
if (curr.next() == tail) tail = curr; // Removed last, move tail
Link tempptr = curr.next(); // Remember the link
curr.setNext(curr.next().next()); // Point around unneeded link
tempptr.release(); // Release the link
listSize--; // Decrement element count
return it; // Return value
}
// Insert "it" at current position
public boolean insert(E it) {
curr.setNext(Link.get(curr.element(), curr.next())); // Get link
curr.setElement(it);
if (tail == curr) { tail = curr.next(); } // New tail
listSize++;
return true;
}
// Append "it" to list
public boolean append(E it) {
Link<E> temp = Link.get(null, null);
tail.setNext(temp);
tail.setElement(it);
tail = tail.next();
listSize++;
return true;
}
// Remove and return current element
public E remove () {
if (curr == tail) { return null; } // Nothing to remove
E it = curr.element(); // Remember value
curr.setElement(curr.next().element()); // Pull forward the next element
if (curr.next() == tail) { tail = curr; } // Removed last, move tail
Link<E> tempptr = curr.next(); // Remember the link
curr.setNext(curr.next().next()); // Point around unneeded link
tempptr.release(); // Release the link
listSize--; // Decrement element count
return it; // Return value
}
使用空闲链表能节省多少时间，取决于你所使用的编程语言。
在 C++ 这类必须由程序员调用 new 和 delete 来管理内存的语言中，
从自己的空闲链表获取一个结点所需的时间，
不足 new 运算符所需时间的十分之一。
在使用垃圾回收的 Java 这类语言中，
乍看之下使用自己的空闲链表似乎并不省时，
因为 Java 的 new 运算符可以从其内存池的当前起点快速返回空间。
然而，如果不使用空闲链表，
丢弃对结点的访问会产生垃圾，
进而在垃圾回收时导致昂贵的处理开销。
