In the previous chapters, we studied the representation of simple data structures using an array and a sequential mapping. These representations had the property that successive nodes of the data object were stored a fixed distance apart. Thus, (i) if the element aij of a table was stored at location Lij, then ai,j+1 was at the location Lij + c for some constant c; (ii) if the ith node in a queue was at location Li, then the i + 1- st node was at location Li + c mod n for the circular representation; (iii) if the topmost node of a stack was at location LT, then the node beneath it was at location LT - c, etc. These sequential storage schemes proved adequate given the functions one wished to perform (access to an arbitrary node in a table, insertion or deletion of nodes within a stack or queue).
However when a sequential mapping is used for ordered lists, operations such as insertion and deletion of arbitrary elements become expensive. For example, consider the following list of all of the three letter English words ending in AT:
(BAT, CAT, EAT, FAT, HAT, JAT, LAT, MAT, OAT, PAT, RAT, SAT, TAT, VAT, WAT)
To make this list complete we naturally want to add the word GAT, which means gun or revolver. If we are using an array to keep this list, then the insertion of GAT will require us to move elements already in the list either one location higher or lower. We must either move HAT, JAT, LAT, ..., WAT or else move BAT, CAT, EAT and FAT. If we have to do many such insertions into the middle, then neither alternative is attractive because of the amount of data movement. On the other hand, suppose we decide to remove the word LAT which refers to the Latvian monetary unit. Then again, we have to move many elements so as to maintain the sequential representation of the list.
When our problem called for several ordered lists of varying sizes, sequential representation again proved to be inadequate. By storing each list in a different array of maximum size, storage may be wasted. By maintaining the lists in a single array a potentially large amount of data movement is needed. This was explicitly observed when we represented several stacks, queues, polynomials and matrices. All these data objects are examples of ordered lists. Polynomials are ordered by exponent while matrices are ordered by rows and columns. In this chapter we shall present an alternative representation for ordered lists which will reduce the time needed for arbitrary insertion and deletion.
An elegant solution to this problem of data movement in sequential representations is achieved by using linked representations. Unlike a sequential representation where successive items of a list are located a fixed distance apart, in a linked representation these items may be placed anywhere in memory. Another way of saying this is that in a sequential representation the order of elements is the same as in the ordered list, while in a linked representation these two sequences need not be the same. To access elements in the list in the correct order, with each element we store the address or location of the next element in that list. Thus, associated with each data item in a linked representation is a pointer to the next item. This pointer is often referred to as a link. In general, a node is a collection of data, DATA1, ...,DATAn and links LINK1, ...,LINKm. Each item in a node is called a field. A field contains either a data item or a link.
Figure 4.1 shows how some of the nodes of the list we considered before may be represented in memory by using pointers. The elements of the list are stored in a one dimensional array called DATA. But the elements no longer occur in sequential order, BAT before CAT before EAT, etc. Instead we relax this restriction and allow them to appear anywhere in the array and in any order. In order to remind us of the real order, a second array, LINK, is added. The values in this array are pointers to elements in the DATA array. Since the list starts at DATA(8) = BAT, let us set a variable F = 8. LINK(8) has the value 3, which means it points to DATA(3) which contains CAT. The third element of the list is pointed at by LINK(3) which is EAT. By continuing in this way we can list all the words in the proper order.
We recognize that we have come to the end when LINK has a value of zero.
Some of the values of DATA and LINK are undefined such as DATA(2), LINK(2), DATA(5), LINK(5), etc. We shall ignore this for the moment.
It is customary to draw linked lists as an ordered sequence of nodes with links being represented by arrows as in figure 4.2. Notice that we do not explicitly put in the values of the pointers but simply draw arrows to indicate they are there. This is so that we reinforce in our own mind the facts that (i) the nodes do not actually reside in sequential locations, and that (ii) the locations of nodes may change on different runs. Therefore, when we write a program which works with lists, we almost never look for a specific address except when we test for zero.
Let us now see why it is easier to make arbitrary insertions and deletions using a linked list rather than a sequential list. To insert the data item GAT between FAT and HAT the following steps are adequate:
(i) get a node which is currently unused; let its address be X;
(ii) set the DATA field of this node to GAT;
(iii) set the LINK field of X to point to the node after FAT which contains HAT;
(iv) set the LINK field of the node containing FAT to X.
Figure 4.3a shows how the arrays DATA and LINK will be changed after we insert GAT. Figure 4.3b shows how we can draw the insertion using our arrow notation. The new arrows are dashed. The important thing to notice is that when we insert GAT we do not have to move any other elements which are already in the list. We have overcome the need to move data at the expense of the storage needed for the second field, LINK. But we will see that this is not too severe a penalty.
Now suppose we want to delete GAT from the list. All we need to do is find the element which immediately precedes GAT, which is FAT, and set LINK(9) to the position of HAT which is 1. Again, there is no need to move the data around. Even though the LINK field of GAT still contains a pointer to HAT, GAT is no longer in the list (see figure 4.4).
From our brief discussion of linked lists we see that the following capabilities are needed to make linked representations possible:
(i) A means for dividing memory into nodes each having at least one link field;
(ii) A mechanism to determine which nodes are in use and which are free;
(iii) A mechanism to transfer nodes from the reserved pool to the free pool and vice-versa.
Though DATA and LINK look like conventional one dimensional arrays, it is not necessary to implement linked lists using them. For the time being let us assume that all free nodes are kept in a "black box" called the storage pool and that there exist subalgorithms:
(i) GETNODE(X) which provides in X a pointer to a free node but if no node is free, it prints an error message and stops;
(ii) RET(X) which returns node X to the storage pool.
In section 4.3 we shall see how to implement these primitives and also how the storage pool is maintained.
Example 4.1: Assume that each node has two fields DATA and LINK. The following algorithm creates a linked list with two nodes whose DATA fields are set to be the values 'MAT' and 'PAT' respectively. T is a pointer to the first node in this list.
The resulting list structure is
Example 4.2: Let T be a pointer to a linked list as in Example 4.1. T= 0 if the list has no nodes. Let X be a pointer to some arbitrary node in the list T. The following algorithm inserts a node with DATA field 'OAT' following the node pointed at by X.
The resulting list structure for the two cases T = 0 and T
Example 4.3: Let X be a pointer to some node in a linked list T as in example 4.2. Let Y be the node preceding X. Y = 0 if X is the first node in T (i.e., if X = T). The following algorithm deletes node X from T.
We have already seen how to represent stacks and queues sequentially. Such a representation proved efficient if we had only one stack or one queue. However, when several stacks and queues co-exist, there was no efficient way to represent them sequentially. In this section we present a good solution to this problem using linked lists. Figure 4.5 shows a linked stack and a linked queue.
Notice that the direction of links for both the stack and queue are such as to facilitate easy insertion and deletion of nodes. In the case of figure 4.5(a), one can easily add a node at the top or delete one from the top. In figure 4.5(b), one can easily add a node at the rear and both addition and deletion can be performed at the front, though for a queue we normally would not wish to add nodes at the front. If we wish to represent n stacks and m queues simultaneously, then the following set of algorithms and initial conditions will serve our purpose:
Initial conditions:
Boundary conditions:
The solution presented above to the n-stack, m-queue problem is seen to be both computationaliy and conceptually simple. There is no need to shift stacks or queues around to make space. Computation can proceed so long as there are free nodes. Though additional space is needed for the link fields, the cost is no more than a factor of 2. Sometimes the DATA field does not use the whole word and it is possible to pack the LINK and DATA fields into the same word. In such a case the storage requirements for sequential and linked representations would be the same. For the use of linked lists to make sense, the overhead incurred by the storage for the links must be overriden by: (i) the virtue of being able to represent complex lists all within the same array, and (ii) the computing time for manipulating the lists is less than for sequential representation.
Now all that remains is to explain how we might implement the GETNODE and RET procedures.
The storage pool contains all nodes that are not currently being used. So far we have assumed the existence of a RET and a GETNODE procedure which return and remove nodes to and from the pool. In this section we will talk about the implementation of these procedures.
The first problem to be solved when using linked allocation is exactly how a node is to be constructed The number ,and size of the data fields will depend upon the kind of problem one has. The number of pointers will depend upon the structural properties of the data and the operations to be performed. The amount of space to be allocated for each field depends partly on the problem and partly on the addressing characteristics of the machine. The packing and retrieving of information in a single consecutive slice of memory is discussed in section 4.12. For now we will assume that for each field there is a function which can be used to either retrieve the data from that field or store data into the field of a given node.
The next major consideration is whether or not any nodes will ever be returned. In general, we assume we want to construct an arbitrary number of items each of arbitrary size. In that case, whenever some structure is no longer needed, we will "erase" it, returning whatever nodes we can to the available pool. However, some problems are not so general. Instead the problem may call for reading in some data, examining the data and printing some results without ever changing the initial information. In this case a linked structure may be desirable so as to prevent the wasting of space. Since there will never be any returning of nodes there is no need for a RET procedure and we might just as well allocate storage in consecutive order. Thus, if the storage pool has n nodes with fields DATA and LINK, then GETNODE could be implemented as follows:
The variable AV must initially be set to one and we will assume it is a global variable. In section 4.7 we will see a problem where this type of a routine for GETNODE is used.
Now let us handle the more general case. The main idea is to initially link together all of the available nodes in a single list we call AV. This list will be singly linked where we choose any one of the possible link fields as the field through which the available nodes are linked. This must be done at the beginning of the program, using a procedure such as:
This procedure gives us the following list:
Once INIT has been executed, the program can begin to use nodes. Every time a new node is needed, a call to the GETNODE procedure is made. GETNODE examines the list AV and returns the first node on the list. This is accomplished by the following:
Because AV must be used by several procedures we will assume it is a global variable. Whenever the programmer knows he can return a node he uses procedure RET which will insert the new node at the front of list AV. This makes RET efficient and implies that the list AV is used as a stack since the last node inserted into AV is the first node removed (LIFO).
If we look at the available space pool sometime in the middle of processing, adjacent nodes may no longer have consecutive addresses. Moreover, it is impossible to predict what the order of addresses will be. Suppose we have a variable ptr which is a pointer to a node which is part of a list called SAMPLE.
What are the permissable operations that can be performed on a variable which is a pointer? One legal operation is to test for zero, assuming that is the representation of the empty list. (if ptr = 0 then ... is a correct use of ptr). An illegal operation would be to ask if ptr = 1 or to add one to ptr (ptr
1) Is ptr = 0 (or is ptr
2) Is ptr equal to the value of another variable of type pointer, e.g., is ptr = SAMPLE?
The only legal operations we can perform on pointer variables is:
1) Set ptr to zero;
2) Set ptr to point to a node.
Any other form of arithmetic on pointers is incorrect. Thus, to move down the list SAMPLE and print its values we cannot write:
This may be confusing because when we begin a program the first values that are read in are stored sequentially. This is because the nodes we take off of the available space list are in the beginning at consecutive positions 1,2,3,4, ...,max. However, as soon as nodes are returned to the free list, subsequent items may no longer reside at consecutive addresses. A good program returns unused nodes to available space as soon as they are no longer needed. This free list is maintained as a stack and hence the most recently returned node will be the first to be newly allocated. (In some special cases it may make sense to add numbers to pointer variables, e.g., when ptr + i is the location of a field of a node starting at ptr or when nodes are being allocated sequentially, see sections 4.6 and 4.12).
Let us tackle a reasonable size problem using linked lists. This problem, the manipulation of symbolic polynomials, has become a classical example of the use of list processing. As in chapter 2, we wish to be able to represent any number of different polynomials as long as their combined size does not exceed our block of memory. In general, we want to represent the polynomial
A(x) = amxem + ... + a1xe1
where the ai are non-zero coefficients with exponents ei such that em > em-1 > ... > e2 > e1 >= 0. Each term will be represented by a node. A node will be of fixed size having 3 fields which represent the coefficient and exponent of a term plus a pointer to the next term
For instance, the polynomial A= 3x14 + 2x8 + 1 would be stored as
while B = 8x14 - 3x10 + 10x6 would look like
In order to add two polynomials together we examine their terms starting at the nodes pointed to by A and B. Two pointers p and q are used to move along the terms of A and B. If the exponents of two terms are equal, then the coefficients are added and a new term created for the result. If the exponent of the current term in A is less than the exponent of the current term of B, then a duplicate of the term of B is created and attached to C. The pointer q is advanced to the next term. Similar action is taken on A if EXP(p) > EXP(q). Figure 4.7 illustrates this addition process on the polynomials A and B above.
Each time a new node is generated its COEF and EXP fields are set and it is appended to the end of the list C. In order to avoid having to search for the last node in C each time a new node is added, we keep a pointer d which points to the current last node in C. The complete addition algorithm is specified by the procedure PADD. PADD makes use of a subroutine ATTACH which creates a new node and appends it to the end of C. To make things work out neatly, C is initially given a single node with no values which is deleted at the end of the algorithm. Though this is somewhat inelegant, it avoids more computation. As long as its purpose is clearly documented, such a tactic is permissible.
This is our first really complete example of the use of list processing, so it should be carefully studied. The basic algorithm is straightforward, using a merging process which streams along the two polynomials either copying terms or adding them to the result. Thus, the main while loop of lines 3-15 has 3 cases depending upon whether the next pair of exponents are =, <, or >. Notice that there are 5 places where a new term is created, justifying our use of the subroutine ATTACH.
Finally, some comments about the computing time of this algorithm. In order to carry out a computing time analysis it is first necessary to determine which operations contribute to the cost. For this algorithm there are several cost measures:
(i) coefficient additions;
(ii) coefficient comparisons;
(iii) additions/deletions to available space;
(iv) creation of new nodes for C.
Let us assume that each of these four operations, if done once, takes a single unit of time. The total time taken by algorithm PADD is then determined by the number of times these operations are performed. This number clearly depends on how many terms are present in the polynomials A and B. Assume that A and B have m and n terms respectively.
A(x) = amxem + ... + a1xe1, B(x) = bnxfn + ... + b1xf1
where
ai,bi
Then clearly the number of coefficient additions can vary as
0
The lower bound is achieved when none of the exponents are equal, while the upper bound is achieved when the exponents of one polynomial are a subset of the exponents of the other.
As for exponent comparisons, one comparison is made on each iteration of the while loop of lines 3-15. On each iteration either p or q or both move to the next term in their respective polynomials. Since the total number of terms is m + n, the number of iterations and hence the number of exponent comparisons is bounded by m + n. One can easily construct a case when m + n - 1 comparisons will be necessary: e.g. m = n and
em > fn > em-1 > fn-1 > ... > f2 > en-m+2 > ... > e1 > f1.
The maximum number of terms in C is m + n, and so no more than m + n new nodes are created (this excludes the additional node which is attached to the front of C and later returned). In summary then, the maximum number of executions of any of the statements in PADD is bounded above by m + n. Therefore, the computing time is O(m + n). This means that if the algorithm is implemented and run on a computer, the time taken will be c1m + c2n + c3 where c1,c2,c3 are constants. Since any algorithm that adds two polynomials must look at each nonzero term at least once, every algorithm must have a time requirement of c'1m + c'2n + c'3. Hence, algorithm PADD is optimal to within a constant factor.
The use of linked lists is well suited to polynomial operations. We can easily imagine writing a collection of procedures for input, output addition, subtraction and multiplication of polynomials using linked lists as the means of representation. A hypothetical user wishing to read in polynomials A(x), B(x) and C(x) and then compute D(x) = A(x) * B(x) + C(x) would write in his main program:
Now our user may wish to continue computing more polynomials. At this point it would be useful to reclaim the nodes which are being used to represent T(x). This polynomial was created only as a partial result towards the answer D(x). By returning the nodes of T(x), they may be used to hold other polynomials.
Study this algorithm carefully. It cleverly avoids using the RET procedure to return the nodes of T one node at a time, but makes use of the fact that the nodes of T are already linked. The time required to erase T(x) is still proportional to the number of nodes in T. This erasing of entire polynomials can be carried out even more efficiently by modifying the list structure so that the LINK field of the last node points back to the first node as in figure 4.8. A list in which the last node points back to the first will be termed a circular list. A chain is a singly linked list in which the last node has a zero link field.
Circular lists may be erased in a fixed amount of time independent of the number of nodes in the list. The algorithm below does this.
Figure 4.9 is a schematic showing the link changes involved in erasing a circular list.
A direct changeover to the structure of figure 4.8 however, causes some problems during addition, etc., as the zero polynomial has to be handled as a special case. To avoid such special cases one may introduce a head node into each polynomial; i.e., each polynomial, zero or non-zero, will contain one additional node. The EXP and COEF fields of this node will not be relevant. Thus the zero polynomial will have the representation:
while A = 3x14 + 2x8 + 1 will have the representation
For this circular list with head node representation the test for T = 0 may be removed from CERASE. The only changes to be made to algorithm PADD are:
(i) at line 1 define p, q by p
(ii) at line 3: while p
(iii) at line 16: while p
(iv) at line 20: while q
(v) at line 24: replace this line by LINK(d)
(vi) delete line 25
Thus the algorithm stays essentially the same. Zero polynomials are now handled in the same way as nonzero polynomials.
A further simplification in the addition algorithm is possible if the EXP field of the head node is set to -1. Now when all nodes of A have been examined p = A and EXP(p) = -1. Since -1
Let us review what we have done so far. We have introduced the notion of a singly linked list. Each element on the list is a node of fixed size containing 2 or more fields one of which is a link field. To represent many lists all within the same block of storage we created a special list called the available space list or AV. This list contains all nodes which are cullently not in use. Since all insertions and deletions for AV are made at the front, what we really have is a linked list being used as a stack.
There is nothing sacred about the use of either singly linked lists or about the use of nodes with 2 fields. Our polynomial example used three fields: COEF, EXP and LINK. Also, it was convenient to use circular linked lists for the purpose of fast erasing. As we continue, we will see more problems which call for variations in node structure and representation because of the operations we want to perform.
It is often necessary and desirable to build a variety of routines for manipulating singly linked lists. Some that we have already seen are: 1) INIT which originally links together the AV list; 2) GETNODE and 3) RET which get and return nodes to AV. Another useful operation is one which inverts a chain. This routine is especially interesting because it can be done "in place" if we make use of 3 pointers.
The reader should try this algorithm out on at least 3 examples: the empty list, and lists of length 1 and 2 to convince himself that he understands the mechanism. For a list of m
Another useful subroutine is one which concatenates two chains X and Y.
This algorithm is also linear in the length of the first list. From an aesthetic point of view it is nicer to write this procedure using the case statement in SPARKS. This would look like:
Now let us take another look at circular lists like the one below:
A = (x1,x2,x3). Suppose we want to insert a new node at the front of this list. We have to change the LINK field of the node containing x3. This requires that we move down the entire length of A until we find the last node. It is more convenient if the name of a circular list points to the last node rather than the first, for example:
Now we can write procedures which insert a node at the front or at the rear of a circular list and take a fixed amount of time.
To insert X at the rear, one only needs to add the additional statement A
As a last example of a simple procedure for circular lists, we write a function which determines the length of such a list.
Let us put together some of these ideas on linked and sequential representations to solve a problem which arises in the translation of computer languages, the processing of equivalence relations. In FORTRAN one is allowed to share the same storage among several program variables through the use of the EQUIVALENCE statement. For example, the following pair of Fortran statements
DIMENSION A(3), B(2,2), C(6)
EQUIVALENCE (A(2), B(1,2), C(4)), (A(1),D), (D,E,F), (G,H)
would result in the following storage assignment for these variables:
As a result of the equivalencing of A (2), B(1,2) and C(4), these were assigned the same storage word 4. This in turn equivalenced A(1), B(2,1) and C(3), B(1,1) and C(2), and A(3), B(2,2) and C(5). Because of the previous equivalence group, the equivalence pair (A(1), D) also resulted in D sharing the same space as B(2,1) and C(3). Hence, an equivalence of the form (D, C(5)) would conflict with previous equivalences, since C(5) and C(3) cannot be assigned the same storage. Even though the sum of individual storage requirements for these variables is 18, the memory map shows that only 7 words are actually required because of the overlapping specified by the equivalence groups in the EQUIVALENCE statement. The functions to be performed during the processing of equivalence statements, then, are:
(i) determine whether there are any conflicts;
(ii) determine the total amount of storage required;
(iii) determine the relative address of all variables (i.e., the address of A(1), B(1,1), C(1), D, E, F, G and H in the above example).
In the text we shall solve a simplified version of this problem. The extension to the general Fortran equivalencing problem is fairly straight-forward and appears as an exercise. We shall restrict ourselves to the case in which only simple variables are being equivalenced and no arrays are allowed. For ease in processing, we shall assume that all equivalence groups are pairs of numbers (i,j), where if EQUIVALENCE(A,F) appears then i,j are the integers representing A and F. These can be thought of as the addresses of A and F in a symhol table. Furthermore, it is assumed that if there are n variables, then they ale represented by the numbers 1 to n.
The FORTRAN statement EQUIVALENCE specifies a relationship among addresses of variables. This relation has several properties which it shares with other relations such as the conventional mathematical equals. Suppose we denote an arbitrary relation by the symbol
(i) For any variable x, x
(ii) For any two variables x and y, if x
(iii) For any three variables x, y and z, if x
Definition: A relation,
Examples of equivalence relations are numerous. For example, the "equal to" (=) relationship is an equivalence relation since: (i) x = x, (ii) x = y implies y = x, and (iii) x = y and y = z implies x = z. One effect of an equivalence relation is to partition the set S into equivalence classes such that two members x and y of S are in the same equivalence class iff x
then, as a result of the reflexivity, symmetry and transitivity of the relation =, we get the following partitioning of the 12 variables into 3 equivalence classes:
{1, 3, 5, 8, 12}; {2, 4, 6}; {7, 9, 10, 11}.
So, only three words of storage are needed for the 12 variables. In order to solve the FORTRAN equivalence problem over simple variables, all one has to do is determine the equivallence classes. The number of equivalence classes ii the number of words of storage to be allocated and the members of the same equivalence class are allocated the same word of storage.
The algorithm to determine equivalence classes works in essentially two phases. In the first phase the equivalence pairs (i,j) are read in and stored somewhere. In phase two we begin at one and find all pairs of the form (1,j). The values 1 and j are in the same class. By transitivity, all pairs of the form (j,k) imply k is in the same class. We continue in this way until the entire equivalence class containing one has been found, marked and printed. Then we continue on.
The first design for this algorithm might go this way:
The inputs m and n represent the number of related pairs and the number of objects respectively. Now we need to determine which data structure should be used to hold these pairs. To determine this we examine the operations that are required. The pair (i,j) is essentially two random integers in the range 1 to n. Easy random access would dictate an array, say PAIRS (1: n, 1: m). The i-th row would contain the elements j which are paired directly to i in the input. However, this would potentially be very wasteful of space since very few of the array elements would be used. It might also require considerable time to insert a new pair, (i,k), into row i since we would have to scan the row for the next free location or use more storage.
These considerations lead us to consider a linked list to represent each row. Each node on the list requires only a DATA and LINK field. However, we still need random access to the i-th row so a one dimensional array, SEQ(1:n) can be used as the headnodes of the n lists. Looking at the second phase of the algorithm we need a mechanism which tells us whether or not object i has already been printed. An array of bits, BIT(1:n) can be used for this. Now we have the next refinement of the algorithm.
Let us simulate the algorithm as we have it so far, on the previous data set. After the for loop is completed the lists will look like this.
For each relation i
In phase two we can scan the SEQ array and start with the first i, 1
The initialization of SEQ and BIT takes O(n) time. The processing of each input pair in phase 1 takes a constant amount of time. Hence, the total time for this phase is O(m). In phase 2 each node is put onto the linked stack at most once. Since there are only 2m nodes and the repeat loop is executed n times, the time for this phase is O(m + n). Hence, the overall computing time is O(m + n). Any algorithm which processes equivalence relations must look at all the m equivalence pairs and also at all the n variables at least once. Thus, there can be no algorithm with a computing time less than O(m + n). This means that the algorithm EQUIVALENCE is optimal to within a constant factor. Unfortunately,the space required by the algorithm is also O(m + n). In chapter 5 we shall see an alternative solution to this problem which requires only O(n) space.
In Chapter 2, we saw that when matrices were sparse (i.e. many of the entries were zero), then much space and computing time could be saved if only the nonzero terms were retained explicitly. In the case where these nonzero terms did not form any "nice" pattern such as a triangle or a band, we devised a sequential scheme in which each nonzero term was represented by a node with three fields: row, column and value. These nodes were sequentially organized. However, as matrix operations such as addition, subtraction and multiplication are performed, the number of nonzero terms in matrices will vary, matrices representing partial computations (as in the case of polynomials) will be created and will have to be destroyed later on to make space for further matrices. Thus, sequential schemes for representing sparse matrices suffer from the same inadequacies as similar schemes for polynomials. In this section we shall study a very general linked list scheme for sparse matrix representation. As we have already seen, linked schemes facilitate efficient representation of varying size structures and here, too, our scheme will overcome the aforementioned shortcomings of the sequential representation studied in Chapter 2.
In the data representation we shall use, each column of a sparse matrix will be represented by a circularly linked list with a head node. In addition, each row will also be a circularly linked list with a head node. Each node in the structure other than a head node will represent a nonzero term in the matrix A and will be made up of five fields:
ROW, COL, DOWN, RIGHT and VALUE. The DOWN field will be used to link to the next nonzero element in the same column, while the RIGHT field will be used to link to the next nonzero element in the same ROW. Thus, if aij
In order to avoid having nodes of two different sizes in the system, we shall assume head nodes to be configured exactly as nodes being used to represent the nonzero terms of the sparse matrix. The ROW and COL fields of head nodes will be set to zero (i.e. we assume that the rows and columns of our matrices have indices >0). Figure 4.12 shows the structure obtained for the 6 x 7 sparse matrix, A, of figure 4.11.
For each nonzero term of A, we have one five field node which is in exactly one column list and one row list. The head nodes are marked Hl-H7. As can be seen from the figure, the VALUE field of the head nodes for each column list is used to link to the next head node while the DOWN field links to the first nonzero term in that column (or to itself in case there is no nonzero term in that column). This leaves the RIGHT field unutilized. The head nodes for the row lists have the same ROW and COL values as the head nodes for the column lists. The only other field utilized by the row head nodes is the RIGHT field which is not used in the column head nodes. Hence it is possible to use the same node as the head node for row i as for column i. It is for this reason that the row and column head nodes have the same labels. The head nodes themselves, linked through the VALUE field, form a circularly linked list with a head node pointed to by A. This head node for the list of row and column head nodes contains the dimensions of the matrix. Thus, ROW(A) is the number of rows in the matrix A while COL(A) is the number of columns. As in the case of polynomials, all references to this matrix are made through the variable A. If we wish to represent an n x m sparse matrix with r nonzero terms, then the number of nodes needed is r + max {n,m} + 1. While each node may require 2 to 3 words of memory (see section 4.12), the total storage needed will be less than nm for sufficiently small r.
Having arrived at this representation for sparse matrices, let us see how to manipulate it to perform efficiently some of the common operations on matrices. We shall present algorithms to read in a sparse matrix and set up its linked list representation and to erase a sparse matrix (i.e. to return all the nodes to the available space list). The algorithms will make use of the utility algorithm GETNODE(X) to get nodes from the available space list.
To begin with let us look at how to go about writing algorithm MREAD(A) to read in and create the sparse matrix A. We shall assume that the input consists of n, the number of rows of A, m the number of columns of A, and r the number of nonzero terms followed by r triples of the form (i,j,aij). These triples consist of the row, column and value of the nonzero terms of A. It is also assumed that the triples are ordered by rows and that within each row, the triples are ordered by columns. For example, the input for the 6 X 7 sparse matrix of figure 4.11, which has 7 nonzero terms, would take the form: 6,7,7; 1,3,11;1,6,13;2,1,12;2,7,14;3,2,-4;3,6,-8;6,2,-9. We shall not concern ourselves here with the actual format of this input on the input media (cards, disk, etc.) but shall just assume we have some mechanism to get the next triple (see the exercises for one possible input format). The algorithm MREAD will also make use of an auxiliary array HDNODE, which will be assumed to be at least as large as the largest dimensioned matrix to be input. HDNODE(i) will be a pointer to the head node for column i, and hence also for row i. This will permit us to efficiently access columns at random while setting up the input matrix. Algorithm MREAD proceeds by first setting up all the head nodes and then setting up each row list, simultaneously building the column lists. The VALUE field of headnode i is initially used to keep track of the last node in column i. Eventually, in line 27, the headnodes are linked together through this field.
Since GETNODE works in a constant amount of time, all the head nodes may be set up in O(max {n,m}) time, where n is the number of rows and m the number of columns in the matrix being input. Each nonzero term can be set up in a constant amount of time because of the use of the variable LAST and a random access scheme for the bottommost node in each column list. Hence, the for loop of lines 9-20 can be carried out in O(r) time. The rest of the algorithm takes O(max {n,m}) time. The total time is therefore O(max {n,m} + r) = O(n + m + r). Note that this is asymptotically better than the input time of O(nm) for an n x m matrix using a two-dimensional array, but slightly worse than the sequential sparse method of section 2.3.
Before closing this section, let us take a look at an algorithm to return all nodes of a sparse matrix to the available space list.
Since each node is in exactly one row list, it is sufficient to just return all the row lists of the matrix A. Each row list is circularly linked through the field RIGHT. Thus, nodes need not be returned one by one as a circular list can be erased in a constant amount of time. The computing time for the algorithm is readily seen to be 0(n + m). Note that even if the available space list had been linked through the field DOWN, then erasing could still have been carried out in 0(n + m) time. The subject of manipulating these matrix structures is studied further in the exercises. The representation studied here is rather general. For most applications this generality is not needed. A simpler representation resulting in simpler algorithms is discussed in the exercises.
So far we have been working chiefly with singly linked linear lists. For some problems these would be too restrictive. One difficulty with these lists is that if we are pointing to a specific node, say P, then we can easily move only in the direction of the links. The only way to find the node which precedes P is to start back at the beginning of the list. The same problem arises when one wishes to delete an arbitrary node from a singly linked list. As can be seen from example 4.3, in order to easily delete an arbitrary node one must know the preceding node. If we have a problem where moving in either direction is often necessary, then it is useful to have doubly linked lists. Each node now has two link fields, one linking in the forward direction and one in the backward direction.
A node in a doubly linked list has at least 3 fields, say DATA, LLINK (left link) and RLINK (right link). A doubly linked list may or may not be circular. A sample doubly linked circular list with 3 nodes is given in figure 4.13. Besides these three nodes a special node has been
added called a head node. As was true in the earlier sections, head nodes are again convenient for the algorithms. The DATA field of the head node will not usually contain information. Now suppose that P points to any node in a doubly linked list. Then it is the case that
P = RLINK (LLINK(P)) = LLINK (RLINK(P)).
This formula reflects the essential virtue of this structure, namely, that one can go back and forth with equal ease. An empty list is not really empty since it will always have its head node and it will look like
Now to work with these lists we must be able to insert and delete nodes. Algorithm DDLETE deletes node X from list L.
X now points to a node which is no longer part of list L. Let us see how the method works on a doubly linked list with only a single node.
Even though the RLINK and LLINK fields of node X still point to the head node, this node has effectively been removed as there is no way to access X through L.
Insertion is only slightly more complex.
In the next section we will see an important problem from operating systems which is nicely solved by the use of doubly linked lists.
In a multiprocessing computer environment, several programs reside in memory at the same time. Different programs have different memory requirements. Thus, one program may require 60K of memory, another 100K, and yet another program may require 300K. Whenever the operating system needs to request memory, it must be able to allocate a block of contiguous storage of the right size. When the execution of a program is complete, it releases or frees the memory block allocated to it and this freed block may now be allocated to another program. In a dynamic environment the request sizes that will be made are not known ahead of time. Moreover, blocks of memory will, in general, be freed in some order different from that in which they were allocated. At the start of the computer system no jobs are in memory and so the whole memory, say of size M words, is available for allocation to programs. Now, jobs are submitted to the computer and requests are made for variable size blocks of memory. Assume we start off with 100,000 words of memory and five programs P1, P2, P3, P4 and P5 make requests of size 10,000, 15,000, 6,000, 8,000 and 20,000 respectively. Figure 4.14 indicates the status of memory after storage for P5 has been allocated. The unshaded area indicates the memory that is currently not in use. Assume that programs P4 and P2 complete execution, freeing the memory used by them. Figure 4.15 show the status of memory after the blocks for P2 and P4 are freed. We now have three blocks of contiguous memory that are in use and another three that are free. In order to make further allocations, it is necessary to keep track of those blocks that are not in use. This problem is similar to the one encountered in the previous sections where we had to maintain a list of all free nodes. The difference between the situation then and the one we have now is that the free space consists of variable size blocks or nodes and that a request for a block of memory may now require allocation of only a portion of a node rather than the whole node. One of the functions of an operating system is to maintain a list of all blocks of storage currently not in use and then to allocate storage from this unused pool as required. One can once again adopt the chain structure used earlier to maintain the available space list. Now, in addition to linking all the free blocks together, it is necessary to retain information regarding the size of each block in this list of free nodes. Thus, each node on the free list has two fields in its first word, i.e., SIZE and LINK. Figure 4.16 shows the free list corresponding to figure 4.15. The use of a head node simplifies later algorithms.
If we now receive a request for a block of memory of size N, then it is necessary to search down the list of free blocks finding the first block of size
This algorithm is simple enough to understand. In case only a portion of a free block is to be allocated, the allocation is made from the bottom of the block. This avoids changing any links in the free list unless an entire block is allocated. There are, however, two major problems with FF. First, experiments have shown that after some processing time many small nodes are left in the available space list, these nodes being smaller than any requests that would be made. Thus, a request for 9900 words allocated from a block of size 10,000 would leave behind a block of size 100, which may be smaller than any requests that will be made to the system. Retaining these small nodes on the available space list tends to slow down the allocation process as the time needed to make an allocation is proportional to the number of nodes on the available space list. To get around this, we choose some suitable constant
The second operation is the freeing of blocks or returning nodes to AV. Not only must we return the node but we also want to recognize if its neighbors are also free so that they can be coalesced into a single block. Looking back at figure 4.15, we see that if P3 is the next program to terminate, then rather than just adding this node onto the free list to get the free list of figure 4.17, it would be better to combine the adjacent free blocks corresponding to P2 and P4, obtaining the free list of figure 4.18. This combining of adjacent free blocks to get bigger free blocks is necessary. The block allocation algorithm splits big blocks while making allocations. As a result, available block sizes get smaller and smaller. Unless recombination takes place at some point, we will no longer be able to meet large requests for memory.
With the structure we have for the available space list, it is not easy to determine whether blocks adjacent to the block (n, p) (n = size of block and p = starting location) being returned are free. The only way to do this, at present, is to examine all the nodes in AV to determine whether:
(i) the left adjacent block is free, i.e., the block ending at p - 1;
(ii) the right adjacent block is free, i.e., the block beginning at p + n.
In order to determine (i) and (ii) above without searching the available space list, we adopt the node structure of figure 4.19 for allocated and free nodes:
The first and last words of each block are reserved for allocation information. The first word of each free block has four fields: LLINK, RLINK, TAG and SIZE. Only the TAG and SIZE field are important for a block in use. The last word in each free block has two fields: TAG and UPLINK. Only the TAG field is important for a block in use. Now by just examining the tag at p - 1 and p + n one can determine whether the adjacent blocks are free. The UPLINK field of a free block points to the start of the block. The available space list will now be a doubly linked circular list, linked through the fields LLINK and RLINK. It will have a head node with SIZE = 0. A doubly linked list is needed, as the return block algorithm will delete nodes at random from AV. The need for UPLINK will become clear when we study the freeing algorithm. Since the first and last nodes of each block have TAG fields, this system of allocation and freeing is called the Boundary Tag method. It should be noted that the TAG fields in allocated and free blocks occupy the same bit position in the first and last words respectively. This is not obvious from figure 4.19 where the LLINK field precedes the TAG field in a free node. The labeling of fields in this figure has been done so as to obtain clean diagrams for the available space list. The algorithms we shall obtain for the boundary tag method will assume that memory is numbered 1 to m and that TAG(0) = TAG(m + 1) = 1. This last requirement will enable us to free the block beginning at 1 and the one ending at m without having to test for these blocks as special cases. Such a test would otherwise have been necessary as the first of these blocks has no left adjacent block while the second has no right adjacent block. While the TAG information is all that is needed in an allocated block, it is customary to also retain the size in the block. Hence, figure 4.19 also includes a SIZE field in an allocated block.
Before presenting the allocate and free algorithms let us study the initial condition of the system when all of memory is free. Assuming memory begins at location 1 and ends at m, the AV list initially looks like:
While these algorithms may appear complex, they are a direct consequence of the doubly linked list structure of the available space list and also of the node structure in use. Notice that the use of a head node eliminates the test for an empty list in both algorithms and hence simplifies them. The use of circular linking makes it easy to start the search for a large enough node at any point in the available space list. The UPLINK field in a free block is needed only when returning a block whose left adjacent block is free (see lines 18 and 24 of algorithm FREE). The readability of algorithm FREE has been greatly enhanced by the use of the case statement. In lines 20 and 27 AV is changed so that it always points to the start of a free block rather than into
the middle of a free block. One may readily verify that the algorithms work for special cases such as when the available space list contains only the head node.
The best way to understand the algorithms is to simulate an example. Let us start with a memory of size 5000 from which the following allocations are made: r1 = 300, r2 = 600, r3 = 900, r4 = 700, r5 = 1500 and r6 = 1000. At this point the memory configuration is as in figure 4.20. This figure also depicts the different blocks of storage and the available space list. Note that when a portion of a free block is allocated, the allocation is made from the bottom of the block so as to avoid unnecessary link changes in the AV list. First block r1 is freed. Since TAG(5001) = TAG(4700) = 1, no coalescing takes place and the block is inserted into the AV list (figure 4.21a). Next, block r4 is returned. Since both its left adjacent block (r5) and its right adjacent block (r3) are in use at this time (TAG(2500) = TAG(3201) =1), this block is just inserted into the free list to get the configuration of figure 4.21b. Block r3 is next returned. Its left adjacent block is free, TAG(3200) = 0; but its right adjacent block is not, TAG(4101) = 1. So, this block is just attached to the end of its adjacent free block without changing any link fields (figure 4.21c). Block r5 next becomes free. TAG(1000) = 1 and TAG(2501) = 0 and so this block is coalesced with its right adjacent block which is free and inserted into the spot previously occupied by this adjacent free block (figure 4.21(d)). r2 is freed next. Both its upper and lower adjacent blocks are free. The upper block is deleted from the free space list and combined with r2. This bigger block is now just appended to the end of the free block made up of r3, r4 and r5 (figure 4.21(e)).
As for the computational complexity of the two algorithms, one may readily verify that the time required to free a block of storage is independent of the number of free blocks in AV. Freeing a block takes a constant amount of time. In order to accomplish this we had to pay a price in terms of storage. The first and last words of each block in use are reserved for TAG information. Though additional space is needed to maintain AV as a doubly linked list, this is of no consequence as all the storage in AV is free in any case. The allocation of a block of storage still requires a search of the AV list. In the worst case all free blocks may be examined.
An alternative scheme for storage allocation, the Buddy System, is investigated in the exercises.
In Chapter 3, a linear list was defined to be a finite sequence of n
Definition. A generalized list, A, is a finite sequence of n > 0 elements,
The list A itself is written as A = (
The above definition is our first example of a recursive definition so one should study it carefully. The definition is recursive because within our description of what a list is, we use the notion of a list. This may appear to be circular, but it is not. It is a compact way of describing a potentially large and varied structure. We will see more such definitions later on. Some examples of generalized lists are:
Example one is the empty list and is easily seen to agree with the definition. For list A, we have
head (A) = 'a', tail (A) = ((b,c)).
The tail (A) also has a head and tail which are (b,c) and ( ) respectively. Looking at list B we see that
head (B)) = A, tail (B)) = (A, ( ))
Continuing we have
head (tail(B)) = A, tail (tail(B)) = (( ))
both of which are lists.
Two important consequences of our definition for a list are: (i) lists may be shared by other lists as in example iii, where list A makes up two of the sublists of list B; and (ii) lists may be recursive as in example iv. The implications of these two consequences for the data structures needed to represent lists will become evident as we go along.
First, let us restrict ourselves to the situation where the lists being represented are neither shared nor recursive. To see where this notion of a list may be useful, consider how to represent polynomials in several variables. Suppose we need to devise a data representation for them and consider one typical example, the polynomial P(x,y,z) =
x10 y3 z2 + 2x8 y3 z2 + 3x8 y2 z2 + x4 y4 z + 6x3 y4 z + 2yz
One can easily think of a sequential representation for P, say using
nodes with four fields: COEF, EXPX, EXPY, and EXPZ. But this would mean that polynomials in a different number of variables would need a different number of fields, adding another conceptual inelegance to other difficulties we have already seen with sequential representation of polynomials. If we used linear lists, we might conceive of a node of the form
These nodes would have to vary in size depending on the number of variables, causing difficulties in storage management. The idea of using a general list structure with fixed size nodes arises naturally if we consider re-writing P(x,y,z) as
((x10 + 2x8)y3 + 3x8y2)z2 + ((x4 + 6x3)y4 + 2y)z
Every polynomial can be written in this fashion, factoring out a main variable z, followed by a second variable y, etc. Looking carefully now at P(x,y,z) we see that there are two terms in the variable z, Cz2 + Dz, where C and D are polynomials themselves but in the variables x and y. Looking closer at C(x,y), we see that it is of the form Ey3 + Fy2, where E and F are polynomials in x. Continuing in this way we see that every polynomial consists of a variable plus coefficient exponent pairs. Each coefficient is itself a polynomial (in one less variable) if we regard a single numerical coefficient as a polynomial in zero variables.
We can represent P(x,y,z) as a list in the following way using nodes with three fields each, COEF, EXP, LINK, as in section 4.4. Note that each level has a head node indicating the variable that has been factored out. This variable is stored in the COEF field.
The list structure of figure 4.22 uses only fixed size nodes. There is, however, one difficulty which needs to be resolved: how do we distinguish between a coefficient and a pointer to another list? Ultimately, both of these values will be represented as numbers so we cannot readily distinguish between them. The solution is to add another field to each node. This field called TAG, will be zero if the COEF field truly contains a numerical coefficient and a one otherwise. Using the structure of figure 4.22 the polynomial P= 3x2y would be represented as
Notice that the TAG field is set to one in the nodes containing x and y. This is because the character codes for variable names would not really be stored in the COEF field. The names might be too large. Instead a pointer to another list is kept which represents the name in a symbol table. This setting of TAG = 1 is also convenient because it allows us to distinguish between a variable name and a constant.
It is a little surprising that every generalized list can be represented using the node structure:
The reader should convince himself that this node structure is adequate for the representation of any list A. The LINK field may be used as a pointer to the tail of the list while the DATA field can hold an atom in case head (A) is an atom or be a pointer to the list representation of head (A) in case it is a list. Using this node structure, the example lists i-iv have the representation shown in figure 4.23.
Now that we have seen a particular example where generalized lists are useful, let us return to their definition again. Whenever a data object is defined recursively, it is often easy to describe algorithms which work on these objects recursively. If our programming language does not allow recursion, that should not matter because we can always translate a recursive program into a nonrecursive version. To see how recursion is useful, let us write an algorithm which produces an exact copy of a nonrecursive list L in which no sublists are shared. We will assume that each node has three fields, TAG, DATA and LINK, and also that there exists the procedure GETNODE(X) which assigns to X the address of a new node.
The above procedure reflects exactly the definition of a list. We immediately see that COPY works correctly for an empty list. A simple proof using induction will verify the correctness of the entire procedure. Once we have established that the program is correct we may wish to remove the recursion for efficiency. This can be done using some straightforward rules.
(i) At the beginning of the procedure, code is inserted which declares a stack and initializes it to be empty. In the most general case, the stack will be used to hold the values of parameters, local variables, function value, and return address for each recursive call.
(ii) The label L1 is attached to the first executable statement.
Now, each recursive call is replaced by a set of instructions which do the following:
(iii) Store the values of all parameters and local variables in the stack. The pointer to the top of the stack can be treated as global.
(iv) Create the ith new label, Li, and store i in the stack. The value i of this label will be used to compute the return address. This label is placed in the program as described in rule (vii).
(v) Evaluate the arguments of this call (they may be expressions) and assign these values to the appropriate formal parameters.
(vi) Insert an unconditional branch to the beginning of the procedure.
(vii) Attach the label created in (iv) to the statement immediately following the unconditional branch. If this procedure is a function, attach the label to a statement which retrieves the function value from the top of the stack. Then make use of this value in whatever way the recursive program describes.
These steps are sufficient to remove all recursive calls in a procedure. We must now alter any return statements in the following way. In place of each return do:
(viii) If the stack is empty then execute a normal return.
(ix) therwise take the current values of all output parameters (explicitly or implicitly understood to be of type out or inout) and assign these values to the corresponding variables which are in the top of the stack.
(x) Now insert code which removes the index of the return address from the stack if one has been placed there. Assign this address to some unused variable.
(xi) Remove from the stack the values of all local variables and parameters and assign them to their corresponding variables.
(xii) If this is a function, insert instructions to evaluate the expression immediately following return and store the result in the top of the stack.
(xiii) Use the index of the label of the return address to execute a branch to that label.
By following these rules carefully one can take any recursive program and produce a program which works in exactly the same way, yet which uses only iteration to control the flow of the program. On many compilers this resultant program will be much more efficient than its recursive version. On other compilers the times may be fairly close. Once the transformation to iterative form has been accomplished, one can often simplify the program even further thereby producing even more gains in efficiency. These rules have been used to produce the iterative version of COPY which appears on the next page.
It is hard to believe that the nonrecursive version is any more intelligible than the recursive one. But it does show explicitly how to implement such an algorithm in, say, FORTRAN. The non-recursive version does have some virtues, namely, it is more efficient. The overhead of parameter passing on most compilers is heavy. Moreover, there are optimizations that can be made on the latter version, but not on the former. Thus,
both of these forms have their place. We will often use the recursive version for descriptive purposes.
Now let us consider the computing time of this algorithm. The null
list takes a constant amount of time. For the list
A = ((a,b),((c,d),e))
which has the representation of figure 4.24 L takes on the values given in figure 4.25.
The sequence of values should be read down the columns. q, r, s, t, u, v, w, x are the addresses of the eight nodes of the list. From this particular example one should be able to see that nodes with TAG = 0 will be visited twice, while nodes with TAG= 1 will be visited three times. Thus, if a list has a total of m nodes, no more than 3m executions of any statement will occur. Hence, the algorithm is O(m) or linear which is the best we could hope to achieve. Another factor of interest is the maximum depth of recursion or, equivalently, how many locations one will need for the stack. Again, by carefully following the algorithm on the previous example one sees that the maximum depth is a combination of the lengths and depths of all sublists. However, a simple upper bound to use is m, the total number of nodes. Though this bound will be extremely large in many cases, it is achievable, for instance, if
L= (((((a))))).
Another procedure which is often useful is one which determines whether two lists are identical. This means they must have the same structure and the same data in corresponding fields. Again, using the recursive definition of a list we can write a short recursive program which accomplishes this task.
Procedure EQUAL is a function which returns either the value true or false. Its computing time is clearly no more than linear when no sublists are shared since it looks at each node of S and T no more than three times each. For unequal lists the procedure terminates as soon as it discovers that the lists are not identical.
Another handy operation on nonrecursive lists is the function which computes the depth of a list. The depth of the empty list is defined to be zero and in general
Procedure DEPTH is a very close transformation of the definition which is itself recursive.
By now you have seen several programs of this type and you should be feeling more comfortable both reading and writing recursive algorithms. To convince yourself that you understand the way these work, try exercises 37, 38, and 39.
Figure 4.1 Non-Sequential List Representation
Figure 4.2 Usual Way to Draw a Linked List
Figure 4.3a Insert GAT Into DATA(5)
Figure 4.3b Insert Node GAT Into List
Figure 4.4 Delete GAT from List
procedure CREATE2(T)
call GETNODE(I) //get an available node//
T
I; DATA(I) 'MAT' //store information into the node//call GETNODE(I) //get a second available node//
LINK(T)
I // attach first node to the second//LINK(I)
0: DATA(I) 'PAT'end CREATE2
procedure INSERT(T,X)
call GETNODE(I)
DATA(I)
'OAT'if T = 0 then [T
I; LINK(I) 0] //insert into empty list//else [LINK(I)
LINK(X) //insert after X//LINK(X)
I]end INSERT
0 is
procedure DELETE(X, Y, T)
if Y= 0 then T
LINK(T) //remove the first node//else LINK(Y)
LINK(X) //remove an interiornode//
call RET(X) //return node to storage pool//
end DELETE
4.2 LINKED STACKS AND QUEUES
Figure 4.5
T(i) = Top of ith stack 1
i nF(i) = Front of ith queue 1
i mR(i) = Rear of ith queue 1
i mT(i) = 0 1
i nF(i) = 0 1
i mT(i) = 0 iff stack i empty
F(i) = 0 iff queue i empty
procedure ADDS(i, Y)
//add element Y onto stack i//
call GETNODE(X)
DATA(X)
Y //store data value Y into new node//LINK(X)
T(i) //attach new node to top of i-th stack//T(i)
X //reset stack pointer//end ADDS
procedure DELETES(i, Y)
//delete top node from stack i and set Y to be the DATA field of
this node//
if T(i) = 0 then call STACK__EMPTY
X
T(i) //set X to top node of stack i//Y
DATA(X) //Y gets new data//T(i)
LINK(X) //remove node from top of stack i//call RET(X) //return node to storage pool//
end DELETES
procedure ADDQ(i,Y)
//add Y to the ith queue//
call GETNODE(X)
DATA(X)
Y: LINK(X) 0if F(i) = 0 then [F(i)
R(i) X] //the queue was empty//else [LlNK(R(i))
X;R(i) X] //the queue wasnot empty//
end ADDQ
procedure DELETEQ(i, Y)
//delete the first node in the ith queue, set Y to its DATA field//
if F(i) = 0 then call QUEUE__EMPTY
else [X
F(i); F(i) LINK(X)//set X to front node//
Y
DATA(X); call RET(X)] //remove dataand return node//
end DELETEQ
4.3 THE STORAGE POOL
procedure GETNODE(I)
//I is set as a pointer to the next available node//
if AV > n then call NO__MORE__NODES
I
AVAV
AV + 1end GETNODE
procedure INIT(n)
//initialize the storage pool, through the LlNK field, to contain nodes
with addresses 1,2,3, ...,n and set AV to point to the first node
in this list//
for i
1 to n - 1 doLINK(i)
i + 1end
LlNK(n)
0AV
1end INIT
Figure 4.6 Initial Available Space List
procedure GETNODE(X)
//X is set to point to a free node if there is one on AV//
if AV = 0 then call NO__MORE__NODES
X
AVAV
LINK(AV)end GETNODE
procedure RET(X)
//X points to a node which is to be returned to the available space
list//
LINK(X)
AVAV
Xend RET
ptr + 1). These are illegal because we have no way of knowing what data was stored in what node. Therefore, we do not know what is stored either at node one or at node ptr + 1. In short, the only legal questions we can ask about a pointer variable is: 0)?ptr
SAMPLEwhile ptr
5 doprint (DATA (ptr))
ptr
ptr + 1end
4.4 POLYNOMIAL ADDITION
_____________________
| | | |
|COEF | EXP | LINK |
|______|______|_______|
Figure 4.7 Generating the First Three Terms of C = A + B
procedure ATTACH(C,E,d)
//create a new term with COEF = C and EXP = E and attach it
to the node pointed at by d//
call GETNODE(I)
EXP(I)
ECOEF(I)
CLINK(d)
I //attach this node to the end of this list//d
I //move pointer d to the new last node//end ATTACH
procedure PADD(A,B,C)
//polynomials A and B represented as singly linked lists are
summed to form the new list named C//
1 p
A; q B //p,q pointers to next term of A, B//2 call GETNODE(C); d
C //initial node for C, returnedlater//
3 while p
0 and q 0 do //while there are more terms inA and B//
4 case
5 : EXP(p) = EXP(q): //equal exponents//
6 x
COEF(p) + COEF(q)7 if x
0 then call ATTACH(x, EXP(p),d)8 p
LINK(p); q LINK(q) //advance to nextterms//
9 : EXP(p) < EXP(q):
10 call ATTACH(COEF(q),EXP(q),d)
11 q
LINK(q) //advance to next term//12 : else: call ATTACH(COEF(p),EXP(p),d)
13 p
LINK(p) //advance to next term of A//14 end
15 end
16 while p
0 do //copy remaining terms of A//17 call ATTACH(COEF(p),EXP(p),d)
18 p
LINK(p)19 end
20 while q
0 do //copy remaining terms of B//21 call ATTACH(COEF(q),EXP(q),d)
22 q
LINK(q)23 end
24 LINK(d)
0; t C; C LINK(C) //delete extra initialnode//
25 call RET(t)
26 end PADD
0 and em > ... > e1 
0, fn > ... > f1 0. coefficient additions min {m, n}.call READ(A)
call READ(B)
call READ(C)
T
PMUL(A, B)D
PADD(T, C)call PRINT(D)
procedure ERASE(T)
//return all the nodes of T to the available space list avoiding repeated
calls to procedure RET//
if T = 0 then return
p
Twhile LINK (p)
0 do //find the end of T//p
LINK (p)end
LlNK (p)
AV // p points to the last node of T//AV
T //available list now includes T//end ERASE
Figure 4.8 Circular List Representation of A = 3x14 + 2x8 + 1
procedure CERASE(T)
//return the circular list T to the available pool//
if T = 0 then return;
X
LINK (T)LINK(T)
AVAV
Xend CERASE
Figure 4.9 Dashes Indicate Changes Involved in Erasing a Circular List
LINK (A); q LINK(B)A and q B do A do B do C EXP(q) the remaining terms of B can be copied by further executions of the case statement. The same is true if all nodes of B are examined before those of A This implies that there is no need for additional code to copy the remaining terms as in PADD. The final algorithm takes the following simple form.procedure CPADD (A, B, C)
//polynomials A and B are represented as circular lists with head
nodes so that EXP(A) = EXP(B) = -1. C is returned as their sum,
represented as a circular list//
p
LINK (A); q LINK(B)call GETNODE(C); EXP(C)
-1 //set up head node//d
C //last node in C//loop
case
: EXP(p) = EXP(q): if EXP(p)=-1then [LINK(d)
C; return]x
COEF(p) + COEF(q)if x
0 then call ATTACH(x,EXP(p),dp
LINK(p); q LINK(q): EXP(p) < EXP(q): call ATTACH(COEF(q), EXP(q),d)
q
LINK(q): else : call ATTACH(COEF(p), EXP(p),d)
p
LINK(p)end
forever
end CPADD
4.5 MORE ON LINKED LISTS
procedure INVERT(X)
//a chain pointed at by X is inverted so that if X = (a1, ...,am)
then after execution X = (am, ...,a1)//
p
X;q 0while p
0 dor
q;q p //r follows q; q follows p//p
LINK(p) //p moves to next node//LINK(q)
r //link q to previous node//end
X
qend INVERT
1 nodes, the while loop is executed m times and so the computing time is linear or O(m).procedure CONCATENATE(X, Y, Z)
//X = (a1, ...,am), Y = (b1, ...,bn), m,n
0, produces a new chainZ = (a1, ...,am,b1 , ...,bn)//
Z
Xif X = 0 then [Z
Y; return]if Y = 0 then return
p
Xwhile LINK(p)
0 do //find last node of X//p
LINK(p)end
LINK(p)
Y //link last node of X to Y//end CONCATENATE
procedure CONCATENATE(X, Y, Z)
case
: X = 0 :Z
Y: Y = 0 : Z
X: else : p
X; Z Xwhile LINK(p)
0 dop
LINK (p)end
LINK(p)
Yend
end CONCATENATE
procedure INSERT__FRONT(A, X)
//insert the node pointed at by X to the front of the circular list
A, where A points to the last node//
if A = 0 then [A
XLINK (X)
A]else [LINK(X)
LINK (A)LINK(A)
X]end INSERT--FRONT
X to the else clause of INSERT_-_FRONT.procedure LENGTH(A)
//find the length of the circular list A//
i
0if A
0 then [ptr Arepeat
i
i + 1; ptr LINK(ptr)until ptr = A ]
return (i)
end LENGTH
4.6 EQUIVALENCE RELATIONS
and suppose that: x, e.g. x is to be assigned the same location as itself. Thus is reflexive. y then y x, e.g. assigning y the same location as x is the same as assigning x the same location as y. Thus, the relation is symmetric. y and y z then x z, e.g. if x and y are to be assigned the same location and y and z are also to be assigned the same location, then so also are x and z. The relation is transitive., over a set S, is said to be an equivalence relation over S iff it is symmetric, reflexive and transitive over S. y. For example, if we have 12 variables numbered 1 through 12 and the following equivalences were defined via the EQUIVALENCE statement:1
5, 4 2, 7 11, 9 10, 8 5, 7 9, 4 6, 3 12 and 12 1procedure EQUIVALENCE (m,n)
initialize
for k
1 to m doread the next pair (i,j)
process this pair
end
initialize for output
repeat
output a new equivalence class
until done
end EQUIVALENCE
procedure EQUIVALENCE (m,n)
declare SEQ(1:n), DATA(1:2m), LINK(1:2m), BIT(1:n)
initialize BIT, SEQ to zero
for k
1 to m doread the next pair (i,j)
put j on the SEQ(i) list
put i on the SEQ(j) list
end
index
1repeat
if BIT(index) = 0
then [BIT(index)
1output this new equivalence class]
index
index + 1until index > n
end
j, two nodes are used. SEQ(i) points to a list of nodes which contains every number which is directly equivalenced to i by an input relation. i n such that BIT(i) = 0. Each element in the list SEQ(i) is printed. In order to process the remaining lists which, by transitivity, belong in the same class as i a stack of their nodes is created. This is accomplished by changing the LINK fields so they point in the reverse direction. The complete algorithm is now given.procedure EQUIVALENCE (m,n)
//Input: m, the number of equivalence pairs
n, the number of variables
Output: variables 1, ...,n printed in equivalence classes//
declare SEQ(1:n), BIT(1:n)
DATA(1: 2m), LINK(1: 2m);
for i
1 to n do SEQ(i) BIT(i) 0 endav
1for k
1 to m do //phase 1: process all input//read next equivalence pair (i, j)
DATA(av)
j; LlNK(av) SEQ(i) //add j to list i//SEQ(i)
av; av av + 1DATA(av)
i; LINK(av) SEQ(j) //add i to list j//SEQ(j)
av; av av + 1end
index
1repeat //phase 2: output all classes//
if BIT (index) = 0
then [print ('A new class', index)BIT(index)
1 //mark class as output//ptr
SEQ(index); top 0 //initialize stack//loop //find the entire class//
while ptr
0 do //process a list//j
DATA (ptr)if BIT(j) = 0
then [print (j); BIT(j)
1t
LINK (ptr); LINK (ptr) toptop
ptr; ptr t]else ptr
LINK (ptr)end
if top = 0 then exit //stack empty//
ptr
SEQ(DATA(top))top
LINK (top)forever]
index
index + 1until index > n
end EQUIVALENCE
Analysis of Algorithm EQUIVALENCE
4.7 SPARSE MATRICES
0, then there will be a node with VALUE field aij, ROW field i and COL field j. This node will be linked into the circular linked list for row i and also into the circular linked list for column j. It will, therefore, be a member of two lists at the same time .
Figure 4.10 Node Structure for Sparse Matrix Representation
Figure 4.11 6 x 7 Sparse Matrix A
Figure 4.12 Linked Representation of the Sparse Matrix A
Analysis of Algorithm MREAD
procedure MERASE(A)
//return all nodes of A to available space list. Assume that the available
space list is a singly linked list linked through the field RIGHT
with AV pointing to the first node in this list.//
RIGHT(A)
AV; AV A; NEXT VALUE(A)while NEXT
A do //erase circular lists by rows//T
RIGHT(NEXT)RIGHT(NEXT)
AVAV
TNEXT
VALUE(NEXT)end
end MERASE
Analysis of Algorithm MERASE
procedure MREAD(A)
//read in a matrix A and set up its internal representation as
discussed previously. The triples representing nonzero terms
are assumed ordered by rows and within rows by columns.
An auxiliary array HDNODE is used.//
1 read (n,m,r) //m, n are assumed positive. r is the number
of nonzero elements//
2 p
max {m,n}3 for i
1 to p do //get p headnodes for rows andcolumns//
4 call GETNODE(X); HDNODE(i)
X5 ROW(X)
COL(X) 06 RIGHT(X)
VALUE(X) X //these fields point tothemselves//
7 end
8 current_row
1; LAST HDNODE(1)9 for i
1 to r do10 read (rrow, ccol, val) //get next triple//
11 if rrow > current__row //current row is done; close it and
begin another//
12 then [RIGHT(LAST)
HDNODE(current__row)13 current__row
rrow; LAST HDNODE(rrow)]//LAST points to rightmost node//
14 call GETNODE(X)
15 ROW(X)
rrow; COL(X) ccol; VALUE(X) val//store triple into new node//
16 RIGHT(LAST)
X; LAST X //link into row list//17 DOWN(VALUE(HDNODE(ccol)))
X;//link into column list//
18 VALUE(HDNODE(ccol))
X19
20 end
21 //close last row//
if r
0 then RIGHT(LAST) HDNODE(current__row)22 for i
1 to m do //close all column lists//23 DOWN(VALUE(HDNODE(i))) HDNODE(i)
24 end
25 //set up list of headnodes linked through VALUE field//
26 call GETNODE(A): ROW(A)
n; COL(A) m//set up headnode of matrix//
27 for i
1 to p - 1 do VALUE(HDNODE(i)) HDNODE(i + 1)end
28 if p = 0 then VALUE(A)
A29 else [VALUE(HDNODE(p))
AVALUE(A)
HDNODE(1)]30 end MREAD
4.8 DOUBLY LINKED LISTS AND DYNAMIC STORAGE MANAGEMENT
Figure 4.13 Doubly Linked Circular List with Head Node
procedure DDLETE(X, L)
if X = L then call NO__MORE__NODES
//L is a list with at least one node//
RLINK(LLINK(X))
RLINK(X)LLINK(RLINK(X))
LLINK(X)call RET(X)
end DDLETE
procedure DINSERT (P, X)
//insert node P to the right of node X//
LLINK(P)
X //set LLINK and RLINK fields of node P//RLINK(P)
RLINK(X)LLINK(RLINK(X))
PRLINK(X)
Pend DINSERT
Dynamic Storage Management
Figure 4.14 Memory After Allocation to P1-P5
Figure 4.15 Status of Memory After Completion of P2 and P4
N and allocating N words out of this block. Such an allocation strategy is called first fit. The algorithm below makes storage allocations using the first fit strategy. An alternate strategy, best fit, calls for finding a free block whose size is as close to N as possible, but not less than N. This strategy is examined in the exercises.
Figure 4.16 Free List with Head Node Corresponding to figure 4.15
procedure FF(n, p)
//AV points to the available space list which is searched for a node
of size at least n. p is set to the address of a block of size n
that may be allocated. If there is no block of that size then p = 0.
It is assumed that the free list has a head node with SIZE field = 0//
p
LINK(AV); q AVwhile p
0 doif SIZE(p)
n then [SIZE(p) SIZE(p) - nif SIZE(p) = 0 then LINK(q)
LINK(p)else p
p + SIZE(p)return]
q
p; p LINK (p)end
//no block is large enough//
end FF
such that if the allocation of a portion of a node leaves behind a node of size <, then the entire node is allocated. I.e., we allocate more storage than requested in this case. The second problem arises from the fact that the search for a large enough node always begins at the front of the list. As a result of this, all the small nodes tend to collect at the front so that it is necessary to examine several nodes before an allocation for larger blocks can be made. In order to distribute small nodes evenly along the list, one can begin searching for a new node from a different point in the list each time a request is made. To implement this. the available space list is maintained as a circular list with a head node of size zero. AV now points to the last node from which an allocation was made. We shall see what the new allocation algorithm looks like after we discuss what has to be done to free a block of storage.
Figure 4.17 Available Space List When Adjacent Free Blocks Are Not Coalesced.
Figure 4.18 Available Space List When Adjacent Free Blocks Are Coalesced.
Figure 4.19
procedure ALLOCATE (n,p)
//Use next fit to allocate a block of memory of size at least
n, n > 0. The available space list is maintained as described
above and it is assumed that no blocks of size <
are tobe retained. p is set to be the address of the first word in
the block allocated. AV points to a node on the available list.//
1 p
RLINK(AV) //begin search at p//2 repeat
3 if SIZE (p)
n then //block is big enough//4 [diff
SlZE(p) - n5 if diff <
then //allocate whole block//6 [RLINK (LLINK(p))
RLINK(p) //delete nodefrom AV//
7 LLINK(RLlNK(p))
LLINK(p)8 TAG(p)
TAG(p + SlZE(p) - 1) 1 //settags//
9 AV
LLINK(p) //set starting point of nextsearch//
10 return]
11 else //allocate lower n words//
12 [SIZE(p)
diff13 UPLINK (p + diff - 1)
p14 TAG(p + diff - 1)
0 //set upper portion asunused//
15 AV
p //position for next search//16 p
p + diff //set p to point to start of allocatedblock//
17 SlZE(p)
n18 TAG(p)
TAG(p + n - 1) 1//set tags for allocated block//
19 return]]
20 p
RLlNK(p) //examine next node on list//21 until p = RLINK(AV)
22 //no block large enough//
23 p
0;24 end ALLOCATE
procedure FREE(p)
//return a block beginning at p and of size SlZE(p)//
1 n
SlZE(p)2 case
3 :TAG(p - 1) = 1 and TAG(p + n) = 1:
//both adjacent blocks in use//
4 TAG(p)
TAG(p + n - 1) 0 //set up a freeblock//
5 UPLINK (p + n - 1)
p6 LLINK(p)
AV; RLINK (p) RLINK (AV)//insert at right of AV//
7 LLINK (RLlNK(p))
p; RLINK(AV) p8 :TAG(p + n) = 1 and TAG(p - 1) = 0: //only left block
free//
9 q
UPLINK (p - 1 ) //start of left block//10 SIZE(q)
SlZE(q) + n11 UPLINK(p + n - 1)
q; TAG(p + n - 1) 012 :TAG(p + n) = 0 and TAG(p - 1) = 1:
//only right adjacent block free//
13 RLINK(LLINK(p + n))
p //replace blockbeginning//
14 LLINK(RLINK(p + n))
p //at p + n by one//15 LLINK(p)
LLINK(p + n) //beginning at p//16 RLINK(p)
RLINK(p + n)17 SlZE(p)
n + SlZE(p + n)18 UPLINK(p + SIZE(p) - 1)
p19 TAG(p)
020 AV
p21 :else: //both adjacent blocks free//
22 //delete right free block from AV list//
RLINK (LLINK(p + n))
RLINK (p + n)23 LLINK(RLINK(p + n))LLINK(p + n)
24 q
UPLINK(p - 1) //start of left freeblock//
25 SIZE(q)
SIZE(q) + n + SIZE(p + n)26 UPLINK(q + SIZE(q) - 1)
q27 AV
LLINK(p + n)28 end
29 end FREE
Figure 4.20
Figure 4.21 Freeing of Blocks in Boundary Tag System
Figure 4.21 Freeing of Blocks in Boundary Tag System (contd.)
Figure 4.21 Freeing of Blocks in Boundary Tag System (contd.)
Figure 4.21 Freeing of Blocks in Boundary Tag System (contd.)
4.9 GENERALIZED LISTS
0 elements, 
1,...,n, which we write as A = (1, ...,n). The elements of a linear list are restricted to be atoms and thus the only structural property a linear list has is the one of position, i.e. i precedes i+1, 1 i < n. It is sometimes useful to relax this restriction on the elements of a list, permitting them to have a structure of their own. This leads to the notion of a generalized list in which the elements i, 1 i n may be either atoms or lists.1, ..., nwhere the i are either atoms or lists. The elements i, 1 i n which are not atoms are said to be the sublists of A.1, ..., n). A is the name of the list (1, ..., n) and n its length. By convention, all list names will be represented by capital letters. Lower case letters will be used to represent atoms. If n 1, then 1 is the head of A while (2, ..., 2) is the tail of A.(i) D = ( ) the null or empty list, its length is zero.
(ii) A = (a, (b,c)) a list of length two; its first element is
the atom 'a' and its second element is the
linear list (b,c).
(iii) B = (A,A,( )) a list of length three whose first two
elements are the lists A, the third element
the null list.
(iv) C = (a, C) a recursive list of length two. C corresponds
to the infinite list C = (a,(a,(a, ...).
Figure 4.22 Representation of P(x,y,z) using three fields per node
________________________
| | | |
|TAG = 0/1 | DATA | LINK |
|__________|______|______|
Figure 4.23 Representation of Lists i-iv
Recursive Algorithms for Lists
procedure COPY (L)
//L points to a nonrecursive list with no common sublists. COPY
returns a pointer to a new list which is a duplicate of L//
ptr
0if L
0 then[if TAG(L) = 0 then q
DATA(L) //save an atom//else q
COPY(DATA(L)) //recursion//r
COPY(LINK(L)) //copy tail//call GETNODE(ptr) //get a node//
DATA(ptr)
q; LINK(ptr) r //combine head and tail//TAG(ptr)
TAG(L)]return (ptr)
end COPY
procedure COPY(L)
//nonrecursive version//
i
0 //initialize stack index//1: ptr
0if L
0 then[if TAG(L) = 0
then q
DATA(L)else [STACK(i + 1)
q //stack local variables//STACK(i + 2)
rSTACK(i + 3)
ptrSTACK(i + 4)
L //stack parameter//STACK(i + 5)
2 //stack return address//i
i + 5;L
DATA(L); go to 1 //set parameter andbegin//
2: q
STACK(i) //remove function value//i
i - 1]STACK(i + 1)
q; STACK(i + 2) r //stackvariables and//
STACK(i + 3)
ptr; STACK(i + 4) L//parameter for second//
STACK(i + 5)
3; i i +5 //recursive call//L
LINK(L); go to 13: r
STACK(i); i i 1 //remove function value//call GETNODE(ptr)
DATA(ptr)
q; LlNK(ptr) rTAG(ptr)
TAG(L)]if i
0 then [addr STACK(i); L STACK(i - 1)//execute a return//
t
STACK(i - 2); r STACK(i - 3)q
STACK(i - 4);STACK(i - 4)
ptr; ptr t //store functionvalue//
i
i - 4; go to addr] //branch to 2 or 3//return (ptr)
end COPY
Figure 4.24 Linked Representation for A
Levels of Continuing Continuing
recursion Value of L Levels L Levels L
1 q 2 r 3 u
2 s 3 u 4 v
3 t 4 w 5 o
4 o 5 x 4 v
3 t 6 o 3 u
2 s 5 x 2 r
1 q 4 w 3 o
2 r
1 q
Figure 4.25 Values of Parameter in Execution of COPY(A)
procedure EQUAL(S,T)
//S and T are nonrecursive lists, each node having three fields: TAG,
DATA and LINK. The procedure returns the value true if the
lists are identical else false//
ans
falsecase
:S = 0 and T = 0: ans
true:S
0 and T 0:if TAG(S) = TAG(T)
then [if TAG(S) = 0
then ans
DATA (S) = DATA(T)else ans
EQUAL(DATA(S),DATA(T))if ans then
ans
EQUAL(LINK(S),LINK(T))]end
return (ans)
end EQUAL
procedure DEPTH(S)
//S is a nonrecursive list having nodes with fields TAG, DATA an
LINK. The procedure returns the depth of the list//
max
0if S = 0 then return (max) //null list has zero depth//
ptr
Swhile ptr
0 doif TAG(ptr) = 0 then ans
0els