10.3 Implementing pointers and objects

10.3-1

Draw a picture of the sequence $\langle 13, 4, 8, 19, 5, 11 \rangle$ stored as a doubly linked list using the multiple-array representation. Do the same for the single-array representation.

  • A multiple-array representation with $L = 2$,

    $$ \begin{array}{|r|c|c|c|c|c|c|c|} \hline index & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline next & & 3 & 4 & 5 & 6 & 7 & \diagup \\ \hline key & & 13 & 4 & 8 & 19 & 5 & 11 \\ \hline prev & & \diagup & 2 & 3 & 4 & 5 & 6 \\ \hline \end{array} $$

  • A single-array version with $L = 1$,

    $$ \begin{array}{|r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline index & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ \hline key & 13 & 4 & \diagup & 4 & 7 & 1 & 8 & 10 & 4 & 19 & 13 & 7 & 5 & 16 & 10 & 11 & \diagup & 13 \\ \hline \end{array} $$

10.3-2

Write the procedures $\text{ALLOCATE-OBJECT}$ and $\text{FREE-OBJECT}$ for a homogeneous collection of objects implemented by the single-array representation.

1
2
3
4
5
6
ALLOCATE-OBJECT()
    if free == NIL
        error "out of space"
    else x = free
        free = A[x + 1]
        return x
1
2
3
FREE-OBJECT(x)
    A[x + 1] = free
    free = x

10.3-3

Why don't we need to set or reset the $prev$ attributes of objects in the implementation of the $\text{ALLOCATE-OBJECT}$ and $\text{FREE-OBJECT}$ procedures?

We implement $\text{ALLOCATE-OBJECT}$ and $\text{FREE-OBJECT}$ in the hope of managing the storage of currently non-used object in the free list so that one can be allocated for reusing. As the free list acts like a stack, to maintain this stack-like collection, we merely remember its first pointer and set the $next$ attribute of objects. There is no need to worry the $prev$ attribute, for it hardly has any impact on the resulting free list.

10.3-4

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 to implement the procedures $\text{ALLOCATE-OBJECT}$ and $\text{FREE-OBJECT}$ so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. ($\textit{Hint:}$ Use the array implementation of a stack.)

1
2
3
4
5
ALLOCATE-OBJECT()
    if STACK-EMPTY(F)
        error "out of space"
    else x = POP(F)
        return x
1
2
3
4
5
6
7
8
FREE-OBJECT(x)
    p = F.top - 1
    p.prev.next = x
    p.next.prev = x
    x.key = p.key
    x.prev = p.prev
    x.next = p.next
    PUSH(F, p)

10.3-5

Let $L$ be a doubly linked list of length $n$ stored in arrays $key$, $prev$, and $next$ of length $m$. Suppose that these arrays are managed by $\text{ALLOCATE-OBJECT}$ and $\text{FREE-OBJECT}$ procedures that keep a doubly linked free list $F$. Suppose further that of the $m$ items, exactly $n$ are on list $L$ and $m - n$ are on the free list. Write a procedure $\text{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, \ldots, n$ and adjusts the free list $F$ so that it remains correct, occupying array positions $n + 1, n + 2, \ldots, m$. The running time of your procedure should be $\Theta(n)$, and it should use only a constant amount of extra space. Argue that your procedure is correct.

We represent the combination of arrays $key$, $prev$, and $next$ by a multible-array $A$. Each object of $A$'s is either in list $L$ or in the free list $F$, but not in both. The procedure $\text{COMPACTIFY-LIST}$ transposes the first object in $L$ with the first object in $A$, the second objects until the list $L$ is exhausted.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
COMPACTIFY-LIST(L, F)
    TRANSPOSE(A[L.head], A[1])
    if F.head == 1
        F.head = L.head
    L.head = 1
    l = A[L.head].next
    i = 2
    while l != NIL
        TRANSPOSE(A[l], A[i])
        if F == i
            F = l
        l = A[l].next
        i = i + 1
1
2
3
4
5
TRANSPOSE(a, b)
    SWAP(a.prev.next, b.prev.next)
    SWAP(a.prev, b.prev)
    SWAP(a.next.prev, b.next.prev)
    SWAP(a.next, b.next)