In this chapter, we examine the representation of dynamic sets by simple data structures that use pointers. Although many complex data structures can be fashioned using pointers, we present only the rudimentary ones: stacks, queues, linked lists, and rooted trees. We also discuss a method by which objects and pointers can be synthesized from arrays.

Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is prespecified. In a * stack*, the element deleted from the set is the one most recently inserted: the stack implements a

The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP. These names are allusions to physical stacks, such as the spring-loaded stacks of plates used in cafeterias. The order in which plates are popped from the stack is the reverse of the order in which they were pushed onto the stack, since only the top plate is accessible.

As shown in Figure 11.1, we can implement a stack of at most *n* elements with an array *S* [1..*n*]. The array has an attribute *top*[*S*] that indexes the most recently inserted element. The stack consists of elements *S*[1..*top*[*S*]], where *S*[1] is the element at the bottom of the stack and *S*[*top*[*S*]] is the element at the top.

When *top* [*S*] = 0, the stack contains no elements and is * empty*. The stack can be tested for emptiness by the query operation STACK-EMPTY. If an empty stack is popped, we say the stack

The stack operations can each be implemented with a few lines of code.

STACK-EMPTY(S)

1iftop[S] = 0

2then returnTRUE

3else returnFALSE

PUSH(S, x)

1top[S]top[S] + 1

2S[top[S]]x

POP(S)

1ifSTACK-EMPTY(S)

2then error"underflow"

3elsetop[S]top[S] - 1

4returnS[top[S] + 1]

We call the INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE; like the stack operation POP, DEQUEUE takes no element argument. The FIFO property of a queue causes it to operate like a line of people in the registrar's office. The queue has a * head* and a

In our procedures ENQUEUE and DEQUEUE, the error checking for underflow and overflow has been omitted. (Exercise 11.1-4 asks you to supply code that checks for these two error conditions.)

ENQUEUE(Q, x)

1Q[tail[Q]]x

2iftail[Q] =length[Q]

3thentail[Q] 1

4elsetail[Q]tail[Q] + 1

DEQUEUE(Q)

1xQ[head[Q]]

2ifhead[Q] =length[Q]

3thenhead[Q] 1

4elsehead[Q]head[Q] + 1

5returnx

Figure 11.2 shows the effects of the ENQUEUE and DEQUEUE operations. Each operation takes *O*(1) time.

Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.

Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a * deque* (double-ended queue) allows insertion and deletion at both ends. Write four

Show how to implement a queue using two stacks. Analyze the running time of the queue operations.

Show how to implement a stack using two queues. Analyze the running time of the stack operations.

A * linked list* is a data structure in which the objects are arranged in a linear order. Unlike an array, though, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets, supporting (though not necessarily efficiently) all the operations listed on page 198.

As shown in Figure 11.3, each element of a **doubly linked list**** *** L* is an object with a

A list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not. If a list is * singly linked*, we omit the

The procedure LIST-SEARCH(*L, k*) finds the first element with key *k* in list *L* by a simple linear search, returning a pointer to this element. If no object with key *k* appears in the list, then NIL is returned. For the linked list in Figure 11.3(a), the call LIST-SEARCH(*L*, 4) returns a pointer to the third element, and the call LIST-SEARCH(*L*, 7) returns NIL.

LIST-SEARCH(L,k)

1xhead[L]

2whilexNIL andkey[x]k

3doxnext[x]

4returnx

Given an element *x* whose *key* field has already been set, the LIST-INSERT procedure "splices" *x* onto the front of the linked list, as shown in Figure 11.3(b).

LIST-INSERT(L, x)

1next[x]head[L]

2ifhead[L] NIL

3thenprev[head[L]]x

4head[L]x

5prev[x] NIL

The running time for LIST-INSERT on a list of *n* elements is *O*(1).

The procedure LIST-DELETE removes an element *x* from a linked list *L*. It must be given a pointer to *x*, and it then "splices" *x* out of the list by updating pointers. If we wish to delete an element with a given key, we must first call LIST-SEARCH to retrieve a pointer to the element.

LIST-DELETE(L,x)

1ifprev[x] NIL

2thennext[prev[x]]next[x]

3elsehead[L]next[x]

4ifnext[x] NIL

5thenprev[next[x]]prev[x]

LIST-DELETE'(L,x)

1next[prev[x]]next[x]

2prev[next[x]]prev[x]

A * sentinel* is a dummy object that allows us to simplify boundary conditions. For example, suppose that we provide with list

LIST-SEARCH'(L,k)

1xnext[nil[L]]

2whilexnil[L] andkey[x]k

3doxnext[x]

4returnx

LIST-INSERT'(L,x)

1next[x]next[nil[L]]

2prev[next[nil[L]]]x

3next[nil[L]]x

4prev[x]nil[L]

Figure 11.4 shows the effects of LIST-INSERT' and LIST-DELETE' on a sample list.

Can the dynamic-set operation INSERT be implemented on a singly linked list in *O*(1) time? How about DELETE?

Implement a stack using a singly linked list *L*. The operations PUSH and POP should still take *O*(1) time.

Implement a queue by a singly linked list *L*. The operations ENQUEUE and DEQUEUE should still take *O*(1) time.

Write a procedure that merges two singly linked, sorted lists into one singly linked, sorted list without using sentinels. Then, write a similar procedure using a sentinel with key to mark the end of each list. Compare the simplicity of code for the two procedures.

How do we implement pointers and objects in languages, such as Fortran, that do not provide them? In this section, we shall see two ways of implementing linked data structures without an explicit pointer data type. We shall synthesize objects and pointers from arrays and array indices.

To insert a key into a dynamic set represented by a doubly linked list, we must allocate a pointer to a currently unused object in the linked-list representation. Thus, it is useful to manage the storage of objects not currently used in the linked-list representation so that one can be allocated. In some systems, a * garbage collector* is responsible for determining which objects are unused. Many applications, however, are simple enough that they can bear responsibility for returning an unused object to a storage manager. We shall now explore the problem of allocating and freeing (or deallocating) homogeneous objects using the example of a doubly linked list represented by multiple arrays.

We keep the free objects in a singly linked list, which we call the * free list*. The free list uses only the

ALLOCATE-OBJECT( )

1iffree= NIL

2then error"out of space"

3elsexfree

4freenext[x]

5returnx

FREE-OBJECT(x)

1next[x]free

2freex

It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first *m* index locations in the multiple-array representation. (This is the case in a paged, virtual-memory computing environment.) Explain how the procedures ALLOCATE-OBJECT and FREE-OBJECT can be implemented so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (*Hint*: Use the array implementation of a stack.)

Let *L* be a doubly linked list of length *m* stored in arrays *key, prev*, and *next* of length *n*. Suppose that these arrays are managed by ALLOCATE-OBJECT and FREE-OBJECT procedures that keep a doubly linked free list *F*. Suppose further that of the *n* items, exactly *m* are on list *L* and *n - m* are on the free list. Write a procedure COMPACTIFY-LIST (*L, F*) that, given the list *L* and the free list *F*, moves the items in *L* so that they occupy array positions 1, 2, . . . , *m* and adjusts the free list *F* so that it remains correct, occupying array positions *m +* 1,* m + *2,* . . . , n*. The running time of your procedure should be (*m*), and it should use only a constant amount of extra space. Give a careful argument for the correctness of your procedure.

The methods for representing lists given in the previous section extend to any homogeneous data structure. In this section, we look specifically at the problem of representing rooted trees by linked data structures. We first look at binary trees, and then we present a method for rooted trees in which nodes can have an arbitrary number of children.

Fortunately, there is a clever scheme for using binary trees to represent trees with arbitrary numbers of children. It has the advantage of using only *O*(*n*) space for any *n*-node rooted tree. The * left-child, right-sibling representation* is shown in Figure 11.10. As before, each node contains a parent pointer

1. *left-child*[*x*] points to the leftmost child of node *x*, and

2. *right-sibling*[*x*] points to the sibling of *x* immediately to the right.

Draw the binary tree rooted at index 6 that is represented by the following fields.

index key left right

----------------------

1 12 7 3

2 15 8 NIL

3 4 10 NIL

4 10 5 9

5 2 NIL NIL

6 18 1 4

7 7 NIL NIL

8 14 6 2

9 21 NIL NIL

10 5 NIL NIL

The left-child, right-sibling representation of an arbitrary rooted tree uses three pointers in each node: *left-child, right-sibling*, and *parent*. From any node, the parent and all the children of the node can be reached and identified. Show how to achieve the same effect using only two pointers and one boolean value in each node.

unsorted, sorted, unsorted, sorted,

singly singly doubly doubly

linked linked linked linked

---------------------------------------------------------

SEARCH(L,k)

INSERT(L,x)

DELETE(L,x)

SUCCESSOR(L,x)

PREDECESSOR(L,x)

MINIMUM(L)

MAXIMUM(L)

11-2 Mergeable heaps using linked lists

A * mergeable heap* supports the following operations: MAKE-HEAP (which creates an empty mergeable heap), INSERT, MINIMUM, EXTRACT-MIN, and UNION. Show how to implement mergeable heaps using linked lists in each of the following cases. Try to make each operation as efficient as possible. Analyze the running time of each operation in terms of the size of the dynamic set(s) being operated on.

* c. *Lists are unsorted, and dynamic sets to be merged are disjoint.

11-3 Searching a sorted compact list

Exercise 11.3-4 asked how we might maintain an *n*-element list compactly in the first *n* positions of an array. We shall assume that all keys are distinct and that the compact list is also sorted, that is, *key*[*i*]* < key*[*next*[*i*]] for all *i* = 1, 2, . . . , *n* such that *next*[*i*] NIL. Under these assumptions, we expect that the following randomized algorithm can be used to search the list much faster than linear time.

COMPACT-LIST-SEARCH(L,k)

1ihead[L]

2nlength[L]

3whileiNIL andkey[i] <k

4dojRANDOM(l,n)

5ifkey[i] <key[j] andkey[j] <k

6thenij

7inext[i]

8ifkey[i] =k

9then returni

10returnNIL

* b.* Argue that the expected running time of COMPACT-LIST-SEARCH is

* c.* Show that . (

* e.* Prove that E[

* f.* Show that COMPACT-LIST-SEARCH runs in expected time.