7.6. Freelists¶

7.6.1. Freelists¶

The new operator is relatively expensive to use. Garbage collection is also expensive. A memory manager handles general-purpose memory requests. The expense comes from the fact that free store routines must be capable of handling requests to and from free store with no particular pattern, as well as memory requests of vastly different sizes. This, combined with unpredictable freeing of space by the garbage collector, makes them inefficient compared to what might be implemented for more controlled patterns of memory access.

List nodes are created and deleted in a linked list implementation in a way that allows the Link class programmer to provide simple but efficient memory management routines. Instead of making repeated calls to new, the Link class can handle its own freelist. A freelist holds those list nodes that are not currently being used. When a node is deleted from a linked list, it is placed at the head of the freelist. When a new element is to be added to a linked list, the freelist is checked to see if a list node is available. If so, the node is taken from the freelist. If the freelist is empty, the standard new operator must then be called. So we see that the freelist is simply an application of a linked stack.

Settings

Saving...

Server Error
Resubmit

Freelists are particularly useful for linked lists that periodically grow and then shrink. The freelist will never grow larger than the largest size yet reached by the linked list. Requests for new nodes (after the list has shrunk) can be handled by the freelist. Another good opportunity to use a freelist occurs when a program uses multiple lists. So long as they do not all grow and shrink together, the free list can let link nodes move between the lists.

In the implementation shown here, the Link class is augmented with methods get and release. 1

Java (Generic)
Java

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;
  }
}

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;
  }
}

The freelist variable declaration uses the keyword static. This creates a single variable shared among all instances of the Link nodes. In this way, a single freelist is shared by all Link nodes.

Note how simple they are, because they need only remove and add an element to the front of the freelist, respectively. The freelist methods get and release both run in \(\Theta(1)\) time, except in the case where the freelist is exhausted and the new operation must be called. Here are the necessary modifications to members of the linked list class to make use of the freelist version of the link class.

Java (Generic)
Java

  // 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
  }

  // 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
  }

How much time is saved by using freelists depends on the language that you are programming in. In a language like C++ where the programmer must call new and delete to manage memory, getting a node from your own freelist requires less than one tenth of the time required by the new operator. In a language like Java that uses garbage collection, it might at first appear that using your own freelist saves no time, because Java’s new operator can quickly return space from the current start of its memory pool. However, when you do not use a freelist, dropping access to nodes creates garbage which leads to expensive processing at garbage collection time.

1: A language like C++ could use operator overloading to redefine the new and delete operators.

Basic Data Structures

Chapter 7 Lists

7.6. Freelists¶

7.6.1. Freelists¶