Exercise 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 ALLOCATE-OBJECT and FREE-OBJECT procedures that keep a doubly linked free list $L$. Suppose further that of the $m$ items, exactly $n$ are on the list $L$ and $m - n$ 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, \ldots, n$ and adjust 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.

I'll use this approach:

  1. We traverse the free list and mark each element by putting a special value in its prev pointer (it is not used by the free list)
  2. We start two pointers, one from the beginning of the memory and one from the end. We increment the left pointer until it reaches an empty cell and decrement the right until it reaches a non-empty cell. We move the right cell to the left position and leave a forwarding address in the next field. This terminates when the two pointers catch up. At this point the "active" memory is in the beginning of the array and the free - in the end. We take note of the threshold.
  3. We linearly scan the first part of the array and update all the pointers that point beyond the threshold, by using the forwarding address in next.
  4. Finally, we organize the memory beyond the threshold in a free list.

C code

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef int list_t;
typedef int obj_t;

int empty_list = -1;

int   prev[MAX_SIZE];
int   next[MAX_SIZE];
obj_t keys[MAX_SIZE];

int free_list;

void init_storage() {
    int i;
    for (i = 0; i < MAX_SIZE - 1; i++)
        next[i] = i + 1;

    next[i] = -1;
    free_list = 0;
}

list_t allocate_object() {
    if (free_list == -1) {
        fprintf(stderr, "Storage depleted\n");
        exit(1);
    }

    list_t new = free_list;
    free_list = next[free_list];
    return new;
}

void free_object(list_t list) {
    next[list] = free_list;
    free_list = list;
}

list_t cons(obj_t key, list_t list) {
    list_t new = allocate_object();

    next[new] = list;
    prev[new] = empty_list;
    keys[new] = key;

    if (list != empty_list) {
        prev[list] = new;
    }

    return new;
}

void delete(list_t list) {
    if (prev[list] != empty_list) {
        next[prev[list]] = next[list];
    }

    if (next[list] != empty_list) {
        prev[next[list]] = prev[list];
    }

    free_object(list);
}

obj_t get(list) {
    if (list == empty_list) return -1;
    return keys[list];
}

list_t next_obj(list) {
    if (list == empty_list) return -1;
    return next[list];
}

list_t compatify_list(list_t list) {
    list_t left, right, i;

    if (free_list == empty_list) {
        return list;
    }

    i = free_list;
    while (i != empty_list) {
        prev[i] = -2;
        i = next[i];
    }

    left  = 0;
    right = MAX_SIZE - 1;
    while (1) {
        while (prev[left] != -2)
            left++;

        while (prev[right] == -2)
            right--;

        if (left >= right) break;

        prev[left] = prev[right];
        next[left] = next[right];
        keys[left] = keys[right];

        next[right] = left;

        right--;
        left++;
    }

    right++;

    for (int i = 0; i < right; i++) {
        if (prev[i] >= right) {
            prev[i] = next[prev[i]];
        }

        if (next[i] >= right) {
            next[i] = next[next[i]];
        }
    }

    if (list >= right) {
        list = next[list];
    }

    for (i = right; i < MAX_SIZE - 1; i++) {
        next[i] = i+1;
    }
    next[i] = -1;

    free_list = right;

    return list;
}