Schemeで双方向リスト
今日の帰宅車内ハック。といっても武蔵野線は混んでいて座れなかったのでりんかい線の中だけなのですけど。先日作った双方向リストに見やすい表示機能をつけて、Dancing Linksのremoveとrestoreを実装しました。 肝心の双方向リストのソースコードがなくなっていてうちひしがれかけたのですけど、改めて書いてみるとすんなり書けてしまいました。やっぱり最初に作るときが一番大変ですが、一度できるとできたときの「Aha!」によって重要なところは脳に刻み込まれるのでソースがなくなってももう一度作ることができるわけです。そんなことはどうでもいいか。
(define (doublyLinkedList x prev)
(if (null? x)
()
(let ((c (cons (car x) (cons () prev))))
(set-car! (cdr c) (doublyLinkedList (cdr x) c))
c)))
(define dl (doublyLinkedList '(1 2 3 4 5) ()))
(define (getPrev x)
(cdr (cdr x)))
(define (getNext x)
(car (cdr x)))
(define (print x)
(define (_print x)
(if (null? x)
(display ")")
(begin
(display " ")
(display (car x))
(_print (getNext x)))))
(display "(")
(display (car x))
(_print (getNext x)))
(print dl) ;-> (1 2 3 4 5)
(print (getNext dl)) ;-> (2 3 4 5)
(define (getNth x i)
(if (= i 0)
x
(getNth (getNext x) (- i 1))))
(define three (getNth dl 2))
(print three) ; -> (3 4 5)
(define (setRight x y)
(set-car! (cdr x) y))
(define (setLeft x y)
(set-cdr! (cdr x) y))
(define (remove x)
(let
((right (getNext x))
(left (getPrev x)))
(setRight left right)
(setLeft right left)))
(remove three)
(print dl) ;-> (1 2 4 5)
(define (restore x)
(let
((right (getNext x))
(left (getPrev x)))
(setRight left x)
(setLeft right x)))
(restore three)
(print dl) ;-> (1 2 3 4 5)
