## Doubly-linked Lists, Queues, and Heaps

Wednesday, November 7, 2007

## Doubly-linked Lists and Queues

Factor has had doubly-linked lists for years now, but they were not well-documented or polished. Now, they’re documented and have replaced the queues library.

An example of a dlist usage:

```
IN: scratchpad <dlist> "red" over push-front "blue" over push-front dup pop-back .
"red"
```

You can add/remove nodes of a dlist with `push-front`

, `push-back`

,
`pop-front`

, `pop-back`

, `delete-node`

, and search with `dlist-find`

,
`dlist-contains?`

.

Finding the length of a dlist is O(1) since it stores the length as
`dlist-length`

, a tuple slot.

## Heaps

Heaps have been updated to allow for `<min-heap>`

and `<max-heap>`

data
structures. Adding elements to a heap is achieved with
`heap-push ( value key heap -- )`

, while popping elements is
`heap-pop ( heap -- value key )`

.

Factor’s green threads implementation had been using a hack for the
sleep-queue: each time a new entry was added it would modify a
non-growable array, which would then be sorted by the smallest timeout.
Adding a sequence of sleep continuations would take O(n^2 log n) time!
Running `10000 [ [ 100 sleep ] in-thread ] times`

should spawn 10000
threads and sleep for 100 ms in each one, and with the old sleep-queue
implementation it takes over a minute on my Macbook. Now it’s just O(n
log n), which takes a second or two.