Re: LISP: Very Very Basic Question.

[kai.grossjohann@gmx.net (Kai Großjohann)]

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.