Re: beginnerquestion (nconc)

[Yuri Khan <yuri.v.khan@gmail.com>]

On Fri, Mar 17, 2017 at 12:58 PM, Stefan Huchler <stefan.huchler@mail.de> wrote:

> I am a bit anoyed by push and reverse lists its not very straightforward
> solution to create lists in loops, I found in the doku the nconc macro,
> which looks like some sort of push that puts sequences at the end
> instead of the beginning.

You are probably annoyed because you are familiar with list
implementations in other languages where appending an element is a
cheap operation. For example, with a doubly linked list, appending at
either end is constant time.

However, Lisp uses singly linked lists. Appending at the start is a
matter of allocating a single cons cell and setting its cdr to point
to the old head of the list. However, appending at the end requires
traversing the whole list to find its last cell, and then adding a new
cell there. That’s what nconc does. So if your list is 1000 items
long, populating it from beginning to end takes roughly 500000
operations. Populating from the end to beginning and then reversing
will only take on the order of 3000 operations.

Also, the empty list is a special case. It is represented as nil and
does not *have* a last cell that nconc could modify. That’s why nconc
does not work on the empty list.