Memory Allocation for Lists
An advantage of linked lists over arrays is that linked lists gracefully grow and shrink during their lifetime. In particular, their maximum size does not need to be known in advance. One important practical ramification of this observation is that we can have several data structures share the same space, without paying particular attention to their relative size at any time.
The crux of the matter is to consider what happens when we use new to instantiate an object that is to be used as a node on a list. How does the system decide which piece of memory to reserve for that object? For example, when we remove a node from a list, it is one thing for us to rearrange the links so that the node is no longer hooked into the list, but what does the system do with the space that the node occupied? And how does the system recycle space such that it can always find space for a node when new is invoked and more space is needed? The mechanisms behind these questions provide another example of the utility of elementary list processing.
Some coding languages, such as C++, have an operator delete that is the counterpart to new. When we are done using a chunk of allocated memory in a C++ program, we invoke delete to inform the system that the chunk is available for later use. Dynamic memory allocation is the process of managing memory and responding to invocations of new and delete from client programs. In Java, we do not explicitly invoke a method to free memory, but the system still must do dynamic memory allocation.
When we are invoking new directly in apps such as Program 3.8 or Program 3.10, all the calls request memory blocks of the same size. This case is typical, and an alternate method of keeping track of memory available for allocation immediately suggests itself: Simply use a linked list! All nodes that are not on any list that is in use can be kept together on a single linked list. We refer to this list as the free list. When we need to allocate space for a node, we get it by removing it from the free list; when we remove a node from any of our lists, we dispose of it by inserting it onto the free list.
Program 3.13 is a class that implements the same interface as Program 3.11, but which does its own memory allocation for list nodes. Client programs do not refer to list nodes except by declaring variables of type Node and using them as parameters to methods defined in the interface. This program implements the same interface as Program 3.11 so that it can be used with a client such Program 3.12 (to compute the same result!) without changing the client code at all.
This implementation is not intended to be of practical use but rather to serve as a precise description of how a memory allocator might be built in a lower-level language where we could view the memory available as an array and provide clients with array indices (integers) as references to nodes, as in the example in Screenshot. Continuing this example, Screenshot illustrates how the free list grows as nodes are freed, for Program 3.12. Program 3.13 is not a direct implementation of this scenario because it works with an array of references to nodes, not an array of nodes. Regardless, all of this is hidden from the client program: the task of memory management is completely separate from the task of solving a problem like the Josephus problem.
Screenshot Array representation of a linked list, with free list
This version of Screenshot shows the result of maintaining a free list with the nodes deleted from the circular list, with the index of the first node on the free list given at the left. At the end of the process, the free list is a linked list containing all the items that were deleted. Following the links, starting at 1, we see the items in the order 2 9 6 3 4 7 1 5, which is the reverse of the order in which they were deleted.
Circular-list class with memory allocation
This program gives an alternate implementation of the circular-list class of Program 3.11 that illustrates a standard approach to allocating memory for fixed-size nodes. We create an array to hold all of the nodes, then build a free list that is initialized to the maximum number of nodes that our program will use, all linked together. When a client program creates a node, we remove that node from the free list; when a client program is finished with a node, we link that node in to the free list.
class CircularList { static class Node { int val; int next; } static Node M[]; static int free, max = 10000; CircularList() { M = new Node[max+1]; for (int i = 0; i < max; i++) { M[i] = new Node(); M[i].next = i+1; } M[max] = new Node(); M[max].next = 0; free = 0; } Node next(Node x) { return M[x.next]; } int val(Node x) { return x.val; } Node insert(Node x, int v) { int i = free; free = M[free].next; M[i].val = v; if (x == null) M[i].next = i; else { M[i].next = x.next; x.next = i; } return M[i]; } void remove(Node x) { int i = x.next; x.next = M[i].next; M[i].next = free; free = i; } }
In this case, maintaining the free list for fixed-size nodes is a trivial task, given the basic operations for inserting nodes onto and deleting nodes from a list. The general-purpose memory allocator in the Java environment is much more complex than is suggested by this simple example. The implementation of new is not as simple as is indicated by Program 3.13, and finding unreferenced nodes to put on the free list (a process known as garbage collection) is a significant part of the computational burden. One reason that new is more complicated is that it has to handle storage-allocation requests for nodes of varying sizes, ranging from tiny to huge. Several clever storage management algorithms have been developed to do memory management and garbage collection; in Java, the system implements these.
Programs that can take advantage of specialized knowledge about an app often are more efficient than general-purpose programs for the same task. Memory allocation is no exception to this maxim. An algorithm that has to handle storage requests of varying sizes cannot know that we are always going to be making requests for blocks of one fixed size, and it therefore cannot take advantage of that fact. Paradoxically, another reason to avoid general-purpose library methods is that doing so makes programs more portable-we can protect ourselves against unexpected performance changes when the library changes or when we move to a different system. Many programmers have found that using a simple memory allocator like the one illustrated in Program 3.13 is an effective way to develop efficient and portable programs that use linked lists. This approach applies to a number of the algorithms that we will consider throughout this tutorial, which make similar kinds of demands on the memory-management system. That said, we shall use the standard Java new operator to create objects and leave memory management and garbage collection to the Java system throughout the rest of the tutorial.
Exercises
Write a method that removes all the nodes on a circular list, given a reference to one of its nodes.
3.49 Write a program that removes the nodes in positions that are divisible by 5 in a circular list (the fifth, tenth, fifteenth, and so forth), starting at a given node.
Run empirical studies comparing the running times of the circular-list implementations in Program 3.11 and in Program 3.13 for Program 3.12 with M = 2 and N = 103, 104, 105, and 106.
Instrument Program 3.13 to provide a trace such as Screenshot.
3.54 Under the conditions of Exercise 3.53, write a code fragment that, given a link to a node, finds the number of different nodes that it ultimately reaches by following links from that node, without modifying any nodes. Do not use more than a constant amount of extra memory space.