School of Engineering and Applied Science
Department of Computer Science
CSci 133 -- Algorithms and Data Structures I
http://www.seas.gwu.edu/~csci133/spring06
Prof. Michael B. Feldman
mfeldman@gwu.edu

Linked List Node Management Using a List of Available Space (LAVS)
February 2004

What happens when we delete a node from a list? If we merely disconnect all references to it, the node is inaccessible and therefore unavailable for future allocations. This means there is, effectively, one fewer node in the storage pool. If we continue to delete nodes by simply "throwing them away", eventually there will be none left to allocate, and the next insertion will fail for lack of pool space. This slow "leakage" of nodes is like a bucket of water with a small hole in the bottom; if a few drops of water leak out, they are not noticed, but eventually all the drops will leak out and the bucket will be empty. That is why this process is often called a "storage leak" or "memory leak". It is a kind of logic bug that has plagued many commercial software packages over the years.

Some language implementations (Java implementations, for example) contain an automatic mechanism for reclaiming deleted blocks of storage and making them available for future allocations. This system function is called "storage reclamation" or, more colorfully, "garbage collection". A well-designed, reliable garbage collector can automatically prevent leaks.

On the other hand, it is actually very easy to manage our own storage instead of depending upon garbage collection. Dynamic data structures like linked lists are used because they can grow and shrink with time; for each node deleted, it is quite likely that another will be allocated very soon. This is especially true in applications where a number of lists of the same type are active at the same time. Some are longer; others are shorter.

Let us use this fact to set up a "recycling system" for deleted nodes. Instead of just disconnecting a node and waiting for the garbage collector to pick it up, let us recognize that the node is likely to be needed later, and simply attach it to an extra private list within our list system. (In Java, this would be a private list variable of the list class.) Historically this list was called LAVS, for List of AVailable Space. Sometimes it is called FreeList or a similar name.

As an example, here is a client’s list L1 and the LAVS. We assume that, as a result of previous deletions, LAVS currently has two nodes in it.

Each time a node is deleted from an active list, we add it to the front (or rear) of LAVS. In our example, deleting Hat from L1 will have these results:

The same physical node is detached from the middle of one list (L1) and attached to the front of another (LAVS).

Now each time a node must be allocated, we first check LAVS to see if there are any "recycled" nodes. If LAVS is not empty, we just disconnect the first node from LAVS and return a pointer designating it. If LAVS is empty, there are no "recycled" nodes and we must call new to allocate a new one from the storage pool.

The advantage of the LAVS approach is that it does not depend on any particular implementation of garbage collection. In fact, it is completely language- and system-independent, and it is efficient because it involves only copying a few references. You can also carry your knowledge of the LAVS scheme to other languages and systems; it is a universally useful method that has been employed almost since the very beginning of computer history.

(end of article)