One class of multiply linked structures is the *binary tree* and its variations. The classes of tree-like structures are themes of Chapters 8 and 9. Trees are a special case of the *graph*, described and traversed in Chapter 10. However, some multiply linked structures can be managed with a combination of the structures discussed in previous chapters.

Several sections of Chapter 6 give different examples of multiply linked structures or applications of them. Doubly linked lists are introduced in section 6.1. Linkage patterns of interwoven lists called *n-braids* are introduced in section 6.2. The adjacency matrix and graph models that form much of the basis for design and analysis of general data structures are introduced in section 6.3. A survey of sparse matrix structures in section 6.4 provides the background for discussion of two structures for them: Main Diagonal Circulation in Part II, section N, and Orthogonal Lists in section 6.5. Both models use circular 2-braids. The doubly linked lists of section 6.1 are used in the sparse-matrix model and in modeling dynamic memory allocation in section 6.5.

Relatively simple combinations of list structures can be used to construct alternates to the hash table structure of Part II, section B. These combinations are discussed in Part II, section L.

Most of the algorithms that walk a general list structure use stacks, either implicitly (to support *recursion*--see Chapter 7) or explicitly, in analogy with the maze-walk of Part II, section H. An algorithm that walks a general list without using stacks is introduced in section 7.7 and discussed in Part II, section M.

Linearly linked lists can be altered by fast operations when the INSERT and DELETE operations are proscribed, as they are in the STACK and QUEUE structures. In contrast, if additions and deletions are to be made at arbitrary positions within a list, then the fundamental operations become *O(n)* instead of *O*(1) because a search is required to locate an interior node.

When a node to be deleted from a linearly linked list has been located, its removal requires a pointer to both of its immediate neighbors in the list--its predecessor as well as its successor. The same requirement makes some operations, such as the *DeleteTail* procedure of section 3.3.4, awkward. In an operation on a linear list where the predecessor of a node is required, the predecessor must be located with a search. One way to enhance access to neighboring nodes within a list is to weave two linked lists together to form a doubly linked list, as shown in Figure 6.1 :

procedureDeleteTail(dList) {O(1)

ifEmptythen return endif

eTail.Forth{NILoru

UpTail.Back

ifUp=e

thenHeade{singleton response

elseUp.Forthe

endif

DISPOSE(Tail)

TailUp

end{DeleteTail

The deletion of a node from the middle of such a list is relatively straightforward. To remove an already located *p*, the deletion procedure might follow the schema in Figure 6.2.

The relinking can be done with:

procedureUnDouble(dList,p) {O(1)

ifEmptythen return endif

Upp.Back

Downp.Forth

eTail.Forth{NILor u

ifDown=e

thenDeleteTail(dList)

return

endif

ifUp=e

thenDeleteHead(dList)

return

endif

Up.ForthDown

Down.BackUp

DISPOSE(p)

end{UnDouble

p=p.Forth.Back=p.Back.Forth

*Program **PG6.1 is appropriate at this point.*

Double links are especially efficient in circular lists, such as that in Figure 6.3. There is no distinguishable *position* in such a list, although *Q* is the distinguished *node*. It can be convenient to let *Q* float from node to node in a sequence of "search and process" operations, pointing to the last (distinguished) node associated with an operation. Because such a ring has no natural head or tail, treating it as a stack or queue requires care.

*Exercises **E6.1 and E6.2 are appropriate at this point.*

The doubly linked assumption can be relaxed for more general linked lists, as shown in Figure 6.4. The *Forth* list defines the sequence 1,2,3,4. The *Back* list defines the sequence 4,2,3,1. The independence of the *Back* and *Forth* linearly linked lists reintroduces the need to search for predecessors. The structure in Figure 6.4 is fundamentally two *interwoven* lists, a 2-*braid*, not a doubly linked list. A 2-braid can be used to simultaneously sequence one set of nodes in two ways. In general, an interweaving of n linear lists on one set of nodes (an *n-braid*) can be used to sequence the nodes in n ways without duplicating the nodes.

*RingIn*(*b,p,q*) inserts node *p* as the successor to node *q* into braid *b*, shown in Figure 6.5.

*RingOut*(*b,q*) deletes the successor of node *q* from braid *b*, shown in Figure 6.6.

*Problem **P6.1 is appropriate at this point.*

The systems to which combinations of data structures can be applied are sometimes complex. Two models that are powerful simplifiers and organizers are commonly applied to such systems to make them accessible to analysis and design. These two models are the *matrix *and the *graph*. They are introduced very briefly here as necessary background for discussions in later parts of the book.

The algorithmic definitions of the matrix operations ADDITION and MULTIPLICATION are:

functionAddMatrix(A,B) {O(n)^{2}

fori=1ton

forj=1tom

C[i,j]A[i,j] +B[i,j]

nextj

nexti

returnC

end{AddMatrix

functionMultiMatrix(A,B) {O(n)^{3}

fori=1ton

forj=1tom{C[i,j] =A[i,p] XB[p,j]

Sum0

fork=1top

SumSum+A[i,k] *B[k,j]

nextk

C[i,j]Sum

nextj

nexti

returnC

end{MultiMatrix

Tables can be used to describe many systems, physical and conceptual. It is uncanny and satisfying that matrix operations often model the *behavior *of such systems. As an example, many systems can be modeled geometrically as a *graph: *informally, a collection of nodes joined by edges, as in Figure 6.7.

Number the nodes (as done in Figure 6.7) and associate both a row and a column of table G* with each node.*

* *If there is an edge connecting node *i* with node *j*, then *G*[*i,j*] 1, otherwise *G*[*i,j*] 0*.*

Figure 6.8 shows the graphs from Figure 6.7 in tabulated form.

One way to interpret these tables is that they select the pairs of nodes connected by a one-step path. A *chain* in a graph is a sequence of edges that lead from one node to another. Technically, if an edge is defined by the pair of nodes it connects, like {1,2} for the edge *e *in (*a*), then a chain is a sequence {*N*_{1},*N*_{2}}, {*N*_{2},*N*_{3}}, . . . , {*N _{n-}*1,

Chapter 10 deals with graph representations as data structures. In this chapter, it is the mathematical nature of a matrix that determines the structure used to represent it; and that structure differs from those used in Chapter 10.

*Exercise E6.3, problem P6.2, and program PG6.2 are appropriate at this point.*

There is no need to restrict the linkage patterns of data elements to linear structures or even to combinations of linear structures. For example, four nodes may be linked as in Figure 6.10.

A simpler geometrical model for this pattern is a *digraph *(directed graph), which differs from a graph precisely because the edges possess direction, as shown in Figure 6.11.

Like a graph, a digraph model has an adjacency matrix, although a digraph matrix is not symmetric about the main diagonal (*M*[*i*,*i*], 1i*Max*) in contrast to the adjacency matrix of a graph. An entry of 1 in *M*[*i*,*j*] for a digraph signifies a *directed* arc (an *edge*) from node *i* to node *j.* An edge is thus an *ordered* pair, (i,j). For the example above, the adjacency matrix *M* is shown in Figure 6.12.

Since edges in a digraph are directional, so are sequences that follow them from one vertex to another. The analog of a graph chain is a digraph *path.* It is still true that *M ^{k}*[

The design of fundamental operations like INSERT and DELETE become very application-dependent and sometimes difficult in a general list. A search through a digraph structure appears to be forbidding; nevertheless it is required in some applications. Hence there *are* algorithms for visiting each node of a general list, and a node may be processed in any desired way during the visit. One such algorithm is to be found in Part II, section M. A different visitation algorithm for general lists is the subject of section 7.7, where it serves as an example of a recursive algorithm. The traverse of a (restructured) general list can also be patterned very closely after the treatment of graphs in Chapter 10.

In many applications of graphs modeled by matrices and in other applications involving matrices, *most* of the entries are zero. Such a matrix is called a *sparse matrix.* A workable pair of definitions is that an *N* by *N* matrix is sparse if it contains *O(N)* nonzero entries and *dense* if it contains *O(N ^{2})* nonzero entries.

A number of data structures can be used to represent a sparse matrix:

**1. **SST (Sparse and Static Table). This structure is intrinsically static; not only is its storage allocation fixed, but it is also designed for a specific subset of the cells of the large (virtual) matrix it represents. It is excellent for some sparse table storage, as indicated in section 2.4, but difficult at best to adapt to the general situation of a changing (but still sparse) matrix.

olumn list. This structure is detailed in Part II, section N.

**3. **AM (Adjacency Matrix) and AL (Adjacency List). These are the structures of choice tor supporting a graph traverse, and they are explored in Chapter 10.

**4. **HT (Hash Table). The indices of a cell in a large table can be used to form a hashed address in a smaller table. This approach depends on the discussions of hashing in Part II, sections B and L . It is the basis of PJ6. 1.

**5. **OL (Orthogonal Lists). A circular list of row headers and a circular list of column headers form the framework of row and column (circular) lists. Each cell in the array is braided into one row and one column list. This approach is discussed in section 6.5.

For all of these structures, the user is generally a procedure that accesses the matrix as a table, as would those of section 6.3 when applied to sparse matrices. The desired service is provided by STORE*(i,j,x)* and RETRIEVE(*i,j).*

**Note:** It may be possible to rewrite procedures that access a sparse matrix to make them "more efficient," but *don't.* The result tends to be logical spaghetti, which is hard to debug. Leave if for another course.

In all of these structures, deletion is awkward, and deletion can occur as the result of STORE**.** When an assignment is made to sparse matrix *M***,** as done by *M[i,j] ** x, *several possibilities must be distinguished:

*An existing node is to be updated:*

M[i,j] 0 andx0

A new node is to be inserted into *M*:

M[i,j] 0 andx0

A node is to be deleted from M:

M[i,j] 0 andx= 0

In the case of MDC and OL**,** deletion and insertion are made into both row and column braids with the *RingIn* and *RingOut* procedures of section 6.2.

An example of a very small but relatively sparse matrix is:

This matrix may be represented by an interwoven collection of circular lists in which there are (2*n*+1) header nodes and precisely as many cell nodes as needed for nonzero entries. Every node is braided into a row braid and a column braid, and the headers are distinguished by having either a row or a column index that is illegal, as in Figure 6.14, where 0 is the illegal index.

*Exercise **E6.4 is appropriate at this point.*

General procedures such as *RingIn *and *RingOut *(section 6.2) are applicable to the OL structure if node records use indexed braid pointers and dimension identifiers (for row and column):

Both STORE and RETRIEVE involve finding the correct header, then the predecessor of the node to be accessed. Header location for row or column *dex *is an adaptation of *LT *(section 3.3.2):

functionFindBraid(Other,dex) {0(n)

b(OtherMOD2) +1

HeadOL.Braid[Other]

whileHeadOLdo

ifHead.Dim[b] =dex

then exit endif

HeadHead.Braid[Other]

endwhile

returnHead

end{FindBraid

The appropriate row and column can then be located by:

RowFindBraid(2,i)

ColFindBraid(1,j)

A very similar routine locates the predecessor of the node with a given index in the other direction, within a given braid:

functionFindPred(Head,b,dex) {O(n)

PredHead

sHead.Braid[b]

Other(bMOD 2) +1

whilesHeaddo

ifs.Dim[Other]dex

then exit endif

Preds

ss.Braid[b]

endwhile

returnPred

end{FindPred

With these tools available, RETRIEVE is straightforward: the node in the position where *M*[*i,j*] is expected is located as *p*. If *M*[*i,j*] is not present, *p ** .Braid*[*1*] will not have the correct column index:

functionRetrieve(i,j) {O(n)

RowFindBraid(2,i)

RowPredFindPred(Row,1,j)

pRowPred.Braid[1]

ifp.Dim[2]j

then return0

else returnp.Value

endif

end{Retrieve

STORE is more complex, since it may involve inserting or deleting a node. One version, tuned for clarity but not for efficiency, is:

procedureStore(i,j,x) {O(n)

RowFindBraid(2,i)

ColFindBraid(1,j)

RowPredFindPred(Row,1,j)

ColPredFindPred(Col,2,i)

pRowPred.Braid[1]

ifx=0

then ifp.Dim[2] =j{M[i,j]is in the matrix

thenRingOut(1,RowPred)

RingOut(2,ColPred)

DlSPOSE(p)

endif

elseifp.Dim[2] =j{M[i,j]is in the matrix

thenp.Valuex

elseNEW(n)

n.Valuex

n.Dim[1]i

n.Dim[2]j

RingIn(1,RowPred,n)

RingIn(2,ColPred,n)

endif

endif

end{Store

*Program PG6.3 is appropriate at this point.*

At the lowest level, the main store of a computing system is a large array, part of it preempted by housekeeping procedures necessary for interface of the system to the outside world and to working programs. The operating system, called on by compiler-generated instructions, is asked to provide storage on demand from the main store each time a program is activated and each time a utility routine such as *NEW* is executed.

In practice, memory is soon broken into segments occupied by active programs, separated by segments of free storage. The blocks of free storage are linked together by *Mem* in a circular list called *Avail,* like the one in Figure 6.15. The release of each of the active blocks 1,3,5,6, and 7 differs somewhat from the release of the others.

The guiding principle for release is that when a block is freed, it is to be joined with any contiguous free blocks, enlarging them. The newly freed block is not to be joined to free blocks separated from it by active programs. This is one of several possible strategies, one that allows "quick release."

The catch to this strategy is that "contiguous" means adjoining, in *absolute location,* to blocks that are not on the *Avail* list. Blocks are adjoining on the availability list because of the sequence of entries into and exits from *Avail,* not because of their absolute location.

The property of being contiguous is bidirectional in memory, and so a natural way to link together all blocks, free and active, is as a doubly linked list, *Store,* illustrated in Figure 6.16. *Mem* is exogenous; it uses nodes that are records that point to memory blocks, although an operating system could store the linkage and other information in the blocks themselves (because it has the use of machine instructions that access any cell in any available way).

If block 3 is deactivated, then blocks 2,3, and 4 are collapsed into one block, say block 2, and the resulting structure is depicted in Figure 6.17.

BlockType= RECORD

id: ARRAY[1..20]OF CHAR

Back:BlockType{Store

Forth:BlockType{Store

Next:BlockType{Avail

Start: INTEGER

Size: INTEGER

END {BlockType

6.6.1 The Release of an Active Block (optional)

6.6.2 The Activation of a Program (optional)

Upp.Back

Downp.Forth

the possibilities are delineated in Table 6.1. A straightforward implementation of this organization will produce a nest of **if . . . then . . . else** constructs. An alternative way to orchestrate the release operation is to define simpler subtasks and then structure the way they work together to solve the overall task.

Up= NILDown= NIL Availwas empty and now is to contain a single node,p.

DownNILDown.next= NIL Downis active; it

cannot be joined top,

and sopis added as a

new node toAvail.

Down.NextNIL Downis free; it is

already inAvail,and so

it can be updated to engulfp.

UpNILDown= NILUp.Next= NIL Upis active; it cannot be

joined top,and sopis

added as a new node toAvail.

Up.NextNIL Upis free; it is already

inAvail,and so it can be

updated to engulfp.

DownNILUp.Next= NIL Upis active; it cannot be

joined top.However,Down

may be either free or active,

and two cases result.

Up.NextNIL Up is free; it is already

inAvail,and so it can be

updated to engulfp.

However,Downmay be either

free or active, and two cases

result.

When the special cases are taken care of, *UnLeash* becomes:

procedureUnLeash(p)

Upp .Back

Downp.Forth

ifUpNIL

then ifUp.NextNIL

thenJoin(Store,p) {joinptoUp

UnDouble(Store,p)

pUp

elseFree(p)

endif

elseFree(p)

endif

ifDownNIL

then ifDown.NextNIL {join(new) ptoDown

thenBind(Down)

UnDouble(Store,p)

endif

endif

end{UnLeash

The details of *Join,* *Free,* and *Bind* are left to the problems.

*Problems **P6.3 and P6.4 are appropriate at this point.*

**1.** There is a block *p* in *Avail* for which *p* .*Size* = *s*.

**2.** There are blocks in *Avail* with size at least as large as *s *(but not necessarily an exact fit).

The shifting-and-collapsing operation implied in possibility 3 is called *garbage collection*. It is not always clear just when garbage collection should be done and how. Automatic garbage collection can be incorporated into the release operation so that, on release, all programs are shifted: only one free block ever exists. Analysis reveals that this is a wasteful overhead in most systems. The assumption here is that it is to be done if no single block is of size *s* or greater, but the sum of all free sizes is greater than *s*.

*best-fit*: Search all of *Avail*, and return *p*, where (*p* *.Size* - *s*) 0 is minimal.

*worst-fit*: Search all of *Avail*, and return *p*, where *p* *.Size* - *s* is maximal and at least 0.

*Problems **P6.5-P6.7 are appropriate at this point.*

Garbage collection in practice involves difficulties outside the scope of this book. For one thing, *programs* are moved, and they must execute after being moved. If the active blocks are treated as though they can be moved simply by updating the fields of their records, then garbage collection is a relatively straight-forward shifting operation. It is convenient to shift active blocks upward in memory, leaving a single free block at the bottom of storage. Hence *Avail* can be ignored during the shift and then reinitialized as a single node.

Writing a simulation of memory management that explores the effect of activation strategies and the effect of the distributions of program size and execution times is a substantial project as a class assignment. It is, however, a minor task compared to writing an operating system.

*Projects PJ6.1-PJ6.3 are appropriate at this point.*

Control traffic flows over links in one direction only, and so it is sometimes useful to trade space for the convenience of multiple-link paths. The most straightforward multiple-path structure is the doubly linked list, but lists may be interwoven in almost any pattern to form *n-braids*. Deletion and insertion in interwoven lists requires more care than in singly linked lists; the doubly linked list is intermediate in this respect.

The *adjacency matrix*, the *graph*, and the *digraph* are models with great power to simplify, synthesize, and organize. All three correspond to data structures of wide application and provide background for understanding them.

Matrices (and other tables) commonly waste space because many cells contain a standard value (such as zero). A number of structures are available for dealing with this situation and are treated in section 2.7; Part II, sections B, L, and N; section 6.4; Chapter 10; and PJ6.1. The *Orthogonal List* structure is detailed in section 6.4. This structure and the one detailed in Part II, section N, represent cells of the matrix as nodes braided into circular lists.

One (simplified) model of the dynamic allocation of memory in a computing system is a doubly linked list of blocks that contain either active programs or available storage. The available storage blocks are also on an interwoven circular list. Activating and deactivating programs presents a number of interesting problems not restricted to management of the structures themselves.

Exercises immediate applications of the text material

**E6.1** Write an insertion procedure for a doubly linked list, as discussed in section 6.1.

**E6.2** Write the procedures for both insertion and deletion in a doubly linked *circular* list.

**E6.3** Determine the number of two-step and the number of three-step paths for graphs (*a*) and (*b*) of section 6.3, and verify by calculating the products *G _{a}*

**E6.4** Draw the graphs (*a*) and (*b*) of section 6.3 as sparse matrix lists.

Problems not immediate, but requiring no major extensions of the text material

**P6.1** Write procedures *Ringln* and *RingOut* of section 6.2 for nodes in an *n*-braid.

**P6.2** Deterrnine the timing functions of *AddMatrix* and *MultiMatrix* of section 6.3.

**P6.3** Write the procedure *Join* of section 6.6.1.

**P6.4** Write the procedure *UnDouble* of section 6.6.1.

**P6.5** Write a first-fit strategy procedure *Firstfit* for locating storage in *Avail* as described in section 6.6.2. Return *NIL* if no free block is large enough.

**P6.6** Write a best-fit strategy procedure *Bestfit* for locating storage in Avail as described in section 6.6.2. Return *NIL* if no free block is large enough.

**P6.7** Write a worst-fit strategy procedure *WorstFit* for locating storage in *Avail* as described in section 6.6.2. Return *NIL* if no free block is large enough.

Programs for trying it yourself

**PG6.1** Write a program that inputs a sequence of paired names and test scores and puts them together in a two-link record. The records are to be linked so that they are in order alphabetically by one sequence of links, and in order by score in another sequence of links. Display the records in alphabetic order, on a line with their score successor, and then vice versa.

**PG6.2** Write a program that will accept a sequence of edges (pairs of nodes), and calculate the number of *k*-fold paths from node *i* to node *j* for any specified *i, j,* and *k*.

**PG6.3** Write a program designed around an entry loop that allows a user to insert and retrieve values from an *n* x *n* Orthogonal List form of a sparse matrix (as described in section 6.5).

Projects for fun; for serious students

**PJ6.1** (Assumes knowledge of Part II, sections B and L.) Investigate the hashing of a table *T*[1 . . 30,1 . . 30] into *HT*[1 . . 10,1 . . 10] . The values in *T* are all to be either 0 or 1. Start with a loading of *HT* of 20 percent and determine the mean number of collisions generated by random retrievals and by random assignments, half of which are zero. Determine the loading after 20, 40, . . ., 100 assignments. Repeat this experiment for greater initial loading of *HT*.

**PJ6.2** Write an emulation of memory management as described in section 6.6. The user should be able to activate or deactivate programs by name on command.

**PJ6.3** Write a simulation of memory management as described in section 6.6. The user should be able to specify several control parameters and the mean and standard deviations for program sizes. Control parameters should include the number of activations and deletions, fitting strategy, and the "closeness" factor.