(define (make-node entry prev next)
  (cons entry (cons prev (cons next '()))))

(define (entry node)
  (car node))

(define (prev node)
  (car (cdr node)))

(define (next node)
  (car (cdr (cdr node))))

(define (set-prev! node value)
  (set-car! (cdr node) value))

(define (set-next! node value)
  (set-car! (cdr (cdr node)) value))

(define (front-ptr dq) (car dq))
(define (rear-ptr dq) (cdr dq))
(define (set-front-ptr! dq ptr) (set-car! dq ptr))
(define (set-rear-ptr! dq ptr) (set-cdr! dq ptr))

(define (make-deque) (cons '() '()))

(define (empty-deque? dq) (null? (front-ptr dq)))

(define (front-deque dq)
  (cond ((empty-deque? dq)
         (error "FRONT called with an empty deque" dq))
        (else
         (entry (front-ptr dq)))))

(define (rear-deque dq)
  (cond ((empty-deque? dq)
         (error "REAR called with an empty deque" dq))
        (else
         (entry (rear-ptr dq)))))

(define (front-insert-deque! dq item)
  (let ((new-node (make-node item '() '())))
    (cond ((empty-deque? dq)
           (set-front-ptr! dq new-node)
           (set-rear-ptr! dq new-node)
           dq)
          (else
           (let ((front (front-ptr dq)))
             (set-next! new-node front)
             (set-prev! front new-node)
             (set-front-ptr! dq new-node)
             dq)))))

(define (front-delete-deque! dq)
  (cond ((empty-deque? dq)
         (error "DELETE called with an empty deque" dq))
        ((eq? (front-deque dq)
              (rear-deque dq))
         (set-front-ptr! dq '())
         (set-rear-ptr! dq '()))
        (else
         (let ((front (front-ptr dq))
               (neighbor (next (front-ptr dq))))
           (set-next! front '())
           (set-prev! neighbor '())
           (set-front-ptr! dq neighbor))))
  dq)

(define (rear-insert-deque! dq item)
  (let ((new-node (make-node item '() '())))
    (cond ((empty-deque? dq)
           (set-front-ptr! dq new-node)
           (set-rear-ptr! dq new-node))
          (else
           (let ((rear (rear-ptr dq)))
             (set-next! rear new-node)
             (set-prev! new-node rear)
             (set-rear-ptr! dq new-node)))))
  dq)

(define (rear-delete-deque! dq)
  (cond ((empty-deque? dq)
         (error "DELETE called with an empty deque" dq))
        ((eq? (front-deque dq)
              (rear-deque dq))
         (set-front-ptr! dq '())
         (set-rear-ptr! dq '()))
        (else
         (let ((rear (rear-ptr dq))
               (neighbor (prev (rear-ptr dq))))
           (set-prev! rear '())
           (set-next! neighbor '())
           (set-rear-ptr! dq neighbor))))
  dq)