[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: LISP: Very Very Basic Question.
From: |
Kai Großjohann |
Subject: |
Re: LISP: Very Very Basic Question. |
Date: |
Wed, 09 Apr 2003 15:59:49 +0200 |
User-agent: |
Gnus/5.090018 (Oort Gnus v0.18) Emacs/21.3.50 (gnu/linux) |
Gurucharan <gurucharan.murudeshwar@wipro.com> writes:
> Can anyone explain the way in which the LISP "list"
>
> is implemented internally ?
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 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
--
A preposition is not a good thing to end a sentence with.