# (lispref.info)Rearrangement

Prev: Setcdr Up: Modifying Lists
```
Functions that Rearrange Lists
------------------------------

Here are some functions that rearrange lists "destructively" by
modifying the CDRs of their component cons cells.  We call these
functions "destructive" because the original lists passed as arguments
to them are chewed up to produce a new list that is subsequently
returned.

- Function: nconc &rest LISTS
This function returns a list containing all the elements of LISTS.
Unlike `append' (Note: Building Lists.), the LISTS are *not*
copied.  Instead, the last CDR of each of the LISTS is changed to
refer to the following list.  The last of the LISTS is not
altered.  For example:

(setq x '(1 2 3))
=> (1 2 3)
(nconc x '(4 5))
=> (1 2 3 4 5)
x
=> (1 2 3 4 5)

Since the last argument of `nconc' is not itself modified, it is
reasonable to use a constant list, such as `'(4 5)', as is done in
the above example.  For the same reason, the last argument need
not be a list:

(setq x '(1 2 3))
=> (1 2 3)
(nconc x 'z)
=> (1 2 3 . z)
x
=> (1 2 3 . z)

A common pitfall is to use a quoted constant list as a non-last
argument to `nconc'.  If you do this, your program will change
each time you run it!  Here is what happens:

(nconc '(foo) x))           ;   `foo' to the front of its arg.

=> (lambda (x) (nconc (quote (foo)) x))

(setq xx (add-foo '(1 2)))    ; It seems to work.
=> (foo 1 2)

(setq xy (add-foo '(3 4)))    ; What happened?
=> (foo 1 2 3 4)

(eq xx xy)
=> t

=> (lambda (x) (nconc (quote (foo 1 2 3 4) x)))

- Function: nreverse LIST
This function reverses the order of the elements of LIST.  Unlike
`reverse', `nreverse' alters its argument destructively by
reversing the CDRs in the cons cells forming the list.  The cons
cell which used to be the last one in LIST becomes the first cell
of the value.

For example:

(setq x '(1 2 3 4))
=> (1 2 3 4)
x
=> (1 2 3 4)
(nreverse x)
=> (4 3 2 1)
;; The cell that was first is now last.
x
=> (1)

To avoid confusion, we usually store the result of `nreverse' back
in the same variable which held the original list:

(setq x (nreverse x))

Here is the `nreverse' of our favorite example, `(a b c)',
presented graphically:

-------------        -------------        ------------
| car  | cdr  |      | car  | cdr  |      | car | cdr  |
|   a  |  nil |<--   |   b  |   o  |<--   |   c |   o  |
|      |      |   |  |      |   |  |   |  |     |   |  |
-------------    |   --------- | -    |   -------- | -
|             |      |            |
-------------        ------------

- Function: sort LIST PREDICATE
This function sorts LIST stably, though destructively, and returns
the sorted list.  It compares elements using PREDICATE.  A stable
sort is one in which elements with equal sort keys maintain their
relative order before and after the sort.  Stability is important
when successive sorts are used to order elements according to
different criteria.

The argument PREDICATE must be a function that accepts two
arguments.  It is called with two elements of LIST.  To get an
increasing order sort, the PREDICATE should return `t' if the
first element is "less than" the second, or `nil' if not.

The destructive aspect of `sort' is that it rearranges the cons
cells forming LIST by changing CDRs.  A nondestructive sort
function would create new cons cells to store the elements in their
sorted order.  If you wish to sort a list without destroying the
original, copy it first with `copy-sequence'.

The CARs of the cons cells are not changed; the cons cell that
originally contained the element `a' in LIST still has `a' in its
CAR after sorting, but it now appears in a different position in
the list due to the change of CDRs.  For example:

(setq nums '(1 3 2 6 5 4 0))
=> (1 3 2 6 5 4 0)
(sort nums '<)
=> (0 1 2 3 4 5 6)
nums
=> (1 2 3 4 5 6)

Note that the list in `nums' no longer contains 0; this is the same
cons cell that it was before, but it is no longer the first one in
the list.  Don't assume a variable that formerly held the argument
now holds the entire sorted list!  Instead, save the result of
`sort' and use that.  Most often we store the result back into the
variable that held the original list:

(setq nums (sort nums '<))

Note: Sorting, for more functions that perform sorting.  See
`documentation' in Note: Accessing Documentation, for a useful
example of `sort'.

See `delq', in Note: Sets And Lists, for another function that
modifies cons cells.

```

automatically generated by info2www