list - 在列表中间添加或删除元素（方案）

Question

是否可以在 Scheme 的链表中间添加或删除元素？我似乎想不出用 car/cdr/cons 做到这一点的方法，但我认为一定有办法做到这一点。

如果我有一个列表'(1 3 5 6)，并且我需要在 5 和 6 之间输入 4，这可行吗？

Answer 1

在给定位置添加元素是在先前的答案中完成的。删除给定位置的元素是类似的：

(define (delete-at k lst)
  (cond ((null? lst)
         '())
        ((zero? k)
         (cdr lst))
        (else
         (cons (car lst)
               (delete-at (sub1 k) (cdr lst))))))

Answer 2

这里有两个版本：

; list-insert : value index list -> list
;   return list where the ith element is x
(define (list-insert x i xs)
  (if (= i 0)
      (cons x xs)
      (cons (first xs) (list-insert x (- i 1) (rest xs)))))

(define (list-insert/version2 x i xs)
  (define-values (before after) (split-at xs i))
  (append before (list x) after))

(list-insert/version2 'x 2 '(a b c d))
(list-insert          'x 2 '(a b c d))

两个版本都会分配一个新列表。对于大型列表，它将变得低效。