AlgoVerse

The available-space list

Keep a pool's free nodes in a linked list: getting a node takes one off its front and returning one puts it back in front; both O(1).

When a linked list's nodes come from a fixed-size pool (an array), we need to know which nodes are free. The free nodes themselves are chained through their link field into an available-space list starting at avail:

Read the full explanation ↓
Input:
n=6PDF export

A positive number gets a node and −k returns node k. Node 2, once returned, is the first one handed out again.

  1. def available_space(ops):
  2. # A pool of 6 nodes numbered 1..6; each row is [node, value, link], and link 0 means null.
  3. n = 6
  4. pool = [[i, "·", i + 1 if i < n else 0] for i in range(1, n + 1)]
  5. avail = 1
  6. used = []
  7. for op in ops:
  8. if op > 0:
  9. if avail == 0:
  10. continue
  11. node = avail
  12. avail = pool[node - 1][2]
  13. pool[node - 1][1] = op
  14. pool[node - 1][2] = "-"
  15. used.append(node)
  16. else:
  17. k = -op
  18. if k not in used:
  19. continue
  20. used.remove(k)
  21. pool[k - 1][1] = "·"
  22. pool[k - 1][2] = avail
  23. avail = k
  24. return used

Invariant: Every node is either in used or on the free list (from avail), and none is on both.

Start

avail—
used—

The table is still empty.

Local variables

Orange = changed in this step

ops list

405060-27080

Call stack

  1. available_space()line 1
Step 1 of 55
Black = store, return_node · Orange = key stepget_node: 0/5 · store: 0/5 · return_node: 0/1
    Explanation

    The idea

    When a linked list's nodes come from a fixed-size pool (an array), we need to know which nodes are free. The free nodes themselves are chained through their link field into an available-space list starting at avail:

    • get a node (GetNode): take the first node of the free list; avail moves on;
    • return a node (RetNode): put the node at the front of the free list.

    Both are O(1); the free list behaves like a stack.

    The input

    A positive number means "get a node and store this number in it", and −k means "return node k". The pool has 6 nodes numbered 1 to 6, and a link of 0 means null.

    What to watch in the trace

    • The table is the pool: each node's value and link. Read the free list from avail by following the links.