# ListStructure

리비젼 5 과 현재 리비젼 간의 차이

요약: Rollback to 2008-09-05 00:16 UTC

차이를 찾지 못함.

Original article by KaiGrossjohann:

The basic data structure is a cons cell. It is a pair consisting of a car and a cdr. The car and the cdr can be numbers or strings etc, or pointers to other cons cells.

For example, (1 . 2) is a cons cell where the car is 1 and the cdr is 2.

You can build binary trees from cons cells:

`    ((1 . 2) . (3 . 4))`

This corresponds to the following tree:

```        *
/ \
*   *
/ \ / \
1 2 3 4```

There is a special value nil which means “empty”, other languages use the term “null”.

A list is a degenerated binary tree, where the cars contain the list elements, and the cdr points to the rest of the list. And nil means the empty list. So (1 . nil) is a one-element list, and (1 . (2 . nil)) is a two-element list, and (1 . (2 . (3 . nil))) is a three-element list. The three-element list as a tree:

```        *
/ \
1   *
/ \
2   *
/ \
3   nil```

In Lisp code, you would create such a list using one of the following idioms.

Generate a list using the `‘list’` function:

`    (list 1 2 3) => (1 2 3)`

The following expression is equivalent:

`    (cons 1 (cons 2 (cons 3 nil))) => (1 2 3)`

A constant list using a quote:

`    '(1 2 3) => (1 2 3)`

Thus, you can add items to the front of the list using cons. Here’s an equivalent expression:

`    (cons 1 '(2 3)) => (1 2 3)`

For ways to modify lists, see ListModification.

CategoryCode