Ex-3.23

I'm implementing the deque using a doubly linked list of nodes, where node is a simple data structure that has two pointers, prev-ptr & next-ptr, pointing to previous node & next node in the list respectively and node contains data value for the item queued.

;node data structure
;node is basically a triplet so that we can store
;next as well as previous in the doubly linked list
;while pair stores 2 things only
(define (make-node prev value next)
  (cons prev (cons value next)))
(define (set-prev-ptr! node item)
  (set-car! node item))
(define (set-next-ptr! node item)
  (set-cdr! (cdr node) item))
(define (set-value! node item)
  (set-car! (cdr node) item))
(define (prev-ptr node)
  (car node))
(define (next-ptr node)
  (cddr node))
(define (value node)
  (cadr node))

;deque
;deque is again pair of front pointer
;and rear pointer
(define (front-ptr deque) (car deque))
(define (rear-ptr deque) (cdr deque))
(define (set-front-ptr! deque item) (set-car! deque item))
(define (set-rear-ptr! deque item) (set-cdr! deque item))

(define (make-deque)
  (cons nil nil))
(define (empty-deque? dq)
  (null? (front-ptr dq)))
(define (front-deque dq)
  (if (empty-deque? dq)
      (error "FRONT-DEQUE! deque is empty")
      (value (front-ptr dq))))
(define (rear-deque dq)
  (if (empty-deque? dq)
      (error "REAR-DEQUE! deque is empty")
      (value (rear-ptr dq))))
(define (front-insert-deque! dq item)
  (let ((new-node (make-node nil item nil)))
    (cond ((empty-deque? dq)
           (set-front-ptr! dq new-node)
           (set-rear-ptr! dq new-node))
          (else
           (set-next-ptr! (rear-ptr dq) new-node)
           (set-prev-ptr! new-node (rear-ptr dq))
           (set-rear-ptr! dq new-node)))))
(define (rear-insert-deque! dq item)
  (let ((new-node (make-node nil item nil)))
    (cond ((empty-deque? dq)
           (set-front-ptr! dq new-node)
           (set-rear-ptr! dq new-node))
          (else
           (set-next-ptr! new-node (front-ptr dq))
           (set-prev-ptr! (front-ptr dq) new-node)
           (set-front-ptr! dq new-node)))))
(define (delete-front-deque! dq)
  (cond
   ((empty-deque? dq)
    (error "DELETE-FRONT-DEQUE! deque is empty"))
   (else 
    (set-front-ptr! dq (next-ptr (front-ptr dq)))
    ;if front-ptr is nil that means there was
    ;only one item in dq
    (if (not (null? (front-ptr dq)))
        (set-prev-ptr! (front-ptr dq) nil)
        (set-rear-ptr! dq nil)))))
(define (delete-rear-deque! dq)
  (cond
   ((empty-deque? dq)
    (error "DELETE-REAR-DEQUE! deque is empty"))
   (else
    (set-rear-ptr! dq (prev-ptr (rear-ptr dq)))
    ;if rear-ptr is nil that means there was
    ;only one item in dq
    (if (not (null? (rear-ptr dq)))
        (set-next-ptr! (rear-ptr dq) nil)
        (set-front-ptr! dq nil)))))

;for debugging
(define (print-deque-forward dq)
  (define (print-deque-aux node)
    (display (value node))
    (display " ")
    (if (not (null? (next-ptr node)))
        (print-deque-aux (next-ptr node))))
  (if (not (empty-deque? dq))
      (begin
        (print-deque-aux (front-ptr dq))
        (newline))))
(define (print-deque-backward dq)
  (define (print-deque-aux node)
    (display (value node))
    (display " ")
    (if (not (null? (prev-ptr node)))
        (print-deque-aux (prev-ptr node))))
  (if (not (empty-deque? dq))
      (begin
        (print-deque-aux (rear-ptr dq))
        (newline))))