Re: Appending to a list

[Stefan Monnier <monnier@iro.umontreal.ca>]

>> `push` is what I would use:
>>     (push "Swift" bird)
>
> This does not append.

Indeed, and it's a feature: append costs O(n), both in immediate CPU
time and in memory allocations (which can increase memory use or at
least increase the time spent in the GC) where `n` is the length of the
list to which you append.  So if you do that O(n) times, you get an
overall O(n²) complexity.

IOW, in most cases you're really better off with pushing to the
beginning of the list, and if the order doesn't suit you, then use
`reverse` afterwards, which will still be O(n) overall rather than
O(n²).

>> No need to use `setq` here.
>>
>> `push` won't check if the element is already in the list, though. You can use
>> `cl-pushnew` in that case, but be sure to load the library it's in:
>>
>>     (require 'cl-lib)
>>     (cl-pushnew "Swift" bird)
> Isn't that the same as
> (add-to-list bird "Swift" t)

Not quite:

- your `t` at the end makes `add-to-list` add to the rear of the
  list whereas `cl-pushnew` adds it to the front.
- `add-to-list` would require you to quote the variable symbol, as in:

      (add-to-list 'bird "Swift" t)

- `add-to-list` cannot operate on a lexically scoped `bird` variable.

- `add-to-list` cannot operate on generalized variables, whereas
  `cl-pushnew` (just like `push`) will be happy with things like

      (cl-pushnew "Swift" (gethash "birds" table))

- `cl-pushnew` by default compares with `eql` whereas here you'd likely
  want to compare with `equal`, like `add-to-list` does, so you'd need:

      (cl-pushnew "Swift" bird :test #'equal)

BTW `push` is significantly faster than either of `add-to-list` or
`cl-pushnew` since it doesn't need to check in O(n) time if the
element is already on the list.


        Stefan