Append an item to the end of the list?

Question

To insert an item at position 0 in scheme I can do the following:

(define 1-to-3 (cons 1 (cons 2 (cons 3 nil))))
(cons 100 1-to-3)
; (100 1 2 3)

Is there a built-in way to insert an element at the end of a list (i.e., append it to the list)?

Answer 1

Use append

There is no built-in way to add an item to the end of a list in standard Scheme. If this is something that you really need to do, but infrequently, you can use append:

;;; Using append: linear in the length of the list `xs`.
(define (append-item xs x)
  (append xs (list x)))

> (append-item '(1 2 3 4) 5)
(1 2 3 4 5)

Pick a Better Data Structure

If you need to add a lot of items to the ends of lists, append will become expensive since it has linear time complexity. The specific use case will guide your choices here; if the goal is to build a list from the end instead of from the front then it may be best to cons up the list and reverse it, as discussed by @Sylwester. If instead you need to be able to add and remove elements from both ends of a list, you might consider a double-ended queue. You can roll your own, or you may be able to use a preexisting library such as SRFI 117 or SRFI 134.

There is no way to get the last pair of a list without either walking the list, maintaining an index, or maintaining a pointer to the last pair of the list in Scheme. You can walk a list directly (but have linear time complexity); you can get constant time complexity by maintaining state (e.g., an index or tail pointer). When you start down this path, you will likely want to create some sort of data structure that abstracts the details. A deque is one example of such a data structure, but as @WillNess has observed, that may be more data structure than you need. A simpler data structure could be created, but the details would depend on an actual use case.

Mutation on a List

You can use mutation to add an element to the end of a list, but this is not idiomatic in Scheme, and it is probably a bad idea, anyway. (Although you might find mutation used in an implementation of a deque or similar data structure). You could mutate the last pair in the input list, using set-cdr! to attach a list containing the new element, like this:

;;; Using `set-cdr!`: this is still linear in the length of `xs`, since it
;;; requires `length`.
(define (append-item! xs x)
  (set-cdr! (list-tail xs (- (length xs) 1)) (list x))
  xs)

> (append-item! (list 1 2 3 4) 5)
(1 2 3 4 5)
> (append-item! (list 1 2 3 4) 5)
(1 2 3 4 5)
> (define xs (list 1 2 3 4))
> (append-item! xs 5)
(1 2 3 4 5)
> xs
(1 2 3 4 5)

This is a bad idea because: 1) you should not attempt to modify list literals in Scheme, which means that you have to pay attention to the provenance of lists given to append-item!, and 2) it is linear in the length of its input list anyway.

Answer 2

Appending a single element to a list is linear in the list size, so it is not a "common" operation.

One can use last and (setf car) though:

(defparameter *l* (list 1 2 3))
==> *L*
* (setf (cdr (last *l*)) (list 4))
==> (4)
* *l*
==> (1 2 3 4)

If you really want to append at the end, you might want to use vector-push-extend instead (which works with extensible arrays rather than lists).

Answer 3

The reason is that a list is a singly linked list. Such structures can remove or add to the beginning in O(1), while doing the same to the end means recreating the list or at least iterating it and mutate the tail.

If you are builing a list it is much better to build it in reverse and then do a single reverse on the result. eg.

(define (add-1 lst)
  (define (helper lst acc)
    (if (null? lst)
        (reverse acc)
        (helper (cdr lst) (cons (+ 1 (car lst)) acc))))

  (helper lst '()))

Now the end result of this is O(n) while if I instead used (append acc (list (+ 1 (car lst)))) and not use reverse the result will be the same, but it would create a new fresh list with 0...n elements and all but the last one will need garbage collection. The time complexity is O(n^2) because append is O(n) and it is done for each element. As the lists grow larger the append version will perform very poorly very quickly.

Answer 4

Here is an example way that you could implement this:

(define (list-append lst elem)
  (if (null? lst)
      (cons elem nil) ; for empty element, extend by the list of elem
      (cons (car lst) (list-append (cdr lst) elem))))

(list-append (list-append 1-to-3 77) 200)
; (1 2 3 77 200)