3.23 Exercise 3.23
In order to make a deque with O(1) insertion and deletion operations,
we need to use a new data structure: A doubly-linked list. This allows us
to add and remove from the deque at both ends in constant time. Otherwise,
for example, it would be impossible to remove the item at the rear of
the queue without traversing through the entire deque to get a pointer
to the item before it.
I’ve chosen to represent a doubly-linked list as a list of lists. Each inner
list represents a node, and has three values: The value of the node, the
pointer to the next item in the list, and the pointer to the previous
item in the list. Nodes on the ends of the deque will have nil pointers
in one (or both) of these places.
I’ve chosen to implement a deque as a mutable object with pointers to the
front and rear, like in the last example. The code is not especially difficult,
but it is a bit longer than usual examples.
There are a few things to note about it, in particular the special cases that
occur when adding nodes to an empty deque or removing the last node. However,
there is a symmetry between the operations that occur at the front and rear
ends of the deque.
| (define (make-deque) | | (let ((front-ptr '())) | | (let ((rear-ptr front-ptr)) | | (define (set-next-ptr from to) | | (set-car! (cdr from) to)) | | (define (set-prev-ptr from to) | | (set-car! (cddr from) to)) | | (define (empty-deque?) | | (null? front-ptr)) | | (define (front-deque) | | (if (empty-deque?) | | (error "FRONT-DEQUE called on empty deque") | | (car front-ptr))) | | (define (rear-deque) | | (if (empty-deque?) | | (error "REAR-DEQUE called on empty deque") | | (car rear-ptr))) | | (define (front-insert-deque! item) | | (let ((new-item (list item front-ptr nil))) | | (if (empty-deque?) | | (begin | | (set! front-ptr new-item) | | (set! rear-ptr new-item)) | | (begin | | (set-prev-ptr front-ptr new-item) | | (set! front-ptr new-item))))) | | (define (rear-insert-deque! item) | | (let ((new-item (list item nil rear-ptr))) | | (if (empty-deque?) | | (begin | | (set! front-ptr new-item) | | (set! rear-ptr new-item)) | | (begin | | (set-next-ptr rear-ptr new-item) | | (set! rear-ptr new-item))))) | | (define (front-delete-deque!) | | (if (empty-deque?) | | (error "FRONT-DELETE-DEQUE! called on empty deque") | | (begin | | (set! front-ptr (cadr front-ptr)) | | (if (null? front-ptr) | | (set! rear-ptr front-ptr) | | (set-prev-ptr front-ptr nil))))) | | (define (rear-delete-deque!) | | (if (empty-deque?) | | (error "REAR-DELETE-DEQUE! called on empty deque") | | (begin | | (set! rear-ptr (caddr rear-ptr)) | | (if (null? rear-ptr) | | (set! front-ptr rear-ptr) | | (set-next-ptr rear-ptr nil))))) | | (define (dispatch m) | | (cond ((eq? m 'empty-deque?) empty-deque?) | | ((eq? m 'front-deque) front-deque) | | ((eq? m 'rear-deque) rear-deque) | | ((eq? m 'front-insert-deque!) front-insert-deque!) | | ((eq? m 'rear-insert-deque!) rear-insert-deque!) | | ((eq? m 'front-delete-deque!) front-delete-deque!) | | ((eq? m 'rear-delete-deque!) rear-delete-deque!) | | (else | | (error "unknown message" m)))) | | dispatch))) |
|
At this point, I think it should be mentioned that I dislike using the
calling conventions for these mutable data objects. I prefer dealing
with functions that take objects as parameters. However, it isn’t difficult
to create those functions on top of an object like this.
| (define (empty-deque? dq) | | ((dq 'empty-deque?))) |
|
| (define (front-deque dq) | | ((dq 'front-deque))) |
|
| (define (rear-deque dq) | | ((dq 'rear-deque))) |
|
| (define (front-insert-deque! dq item) | | ((dq 'front-insert-deque!) item)) |
|
| (define (rear-insert-deque! dq item) | | ((dq 'rear-insert-deque!) item)) |
|
| (define (front-delete-deque! dq) | | ((dq 'front-delete-deque!))) |
|
| (define (rear-delete-deque! dq) | | ((dq 'rear-delete-deque!))) |
|