Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 108

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 . Figure 4.11 shows the reimplementation for the Link class to
support these methods. 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 (1) time, except in the case where the freelist is
exhausted and the new operation must be called. Figure 4.12 shows the necessary
modifications to members of the linked list class to make use of the freelist version
of the link class.
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 shared by all Link nodes.

4.1.3 Comparison of List Implementations

Now that you have seen two substantially different implementations for lists, it is
natural to ask which is better. In particular, if you must implement a list for some
task, which implementation should you choose?
Array-based lists have the disadvantage that their size must be predetermined
before the array can be allocated. Array-based lists cannot grow beyond their pre-
determined size. Whenever the list contains only a few elements, a substantial
amount of space might be tied up in a largely empty array. Linked lists have the
advantage that they only need space for the objects actually on the list. There is
no limit to the number of elements on a linked list, as long as there is free-store
memory available. The amount of space required by a linked list is (n), while the
space required by the array-based list implementation is (n), but can be greater.
Array-based lists have the advantage that there is no wasted space for an in-
dividual element. Linked lists require that an extra pointer be added to every list
node. If the element size is small, then the overhead for links can be a significant
fraction of the total storage. When the array for the array-based list is completely
filled, there is no storage overhead. The array-based list will then be more space
efficient, by a constant factor, than the linked implementation.
A simple formula can be used to determine whether the array-based list or
linked list implementation will be more space efficient in a particular situation.
Call n the number of elements currently in the list, P the size of a pointer in stor-
age units (typically four bytes), E the size of a data element in storage units (this
could be anything, from one bit for a Boolean variable on up to thousands of bytes
or more for complex records), and D the maximum number of list elements that
can be stored in the array. The amount of space required for the array-based list is