From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: kai.grossjohann@gmx.net (Kai =?iso-8859-1?q?Gro=DFjohann?=) Newsgroups: gmane.emacs.help Subject: Re: LISP: Very Very Basic Question. Date: Wed, 09 Apr 2003 15:59:49 +0200 Organization: University of Duisburg, Germany Sender: help-gnu-emacs-bounces+gnu-help-gnu-emacs=m.gmane.org@gnu.org Message-ID: <84u1d793fu.fsf@lucy.is.informatik.uni-duisburg.de> References: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: main.gmane.org 1049897316 5482 80.91.224.249 (9 Apr 2003 14:08:36 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Wed, 9 Apr 2003 14:08:36 +0000 (UTC) Original-X-From: help-gnu-emacs-bounces+gnu-help-gnu-emacs=m.gmane.org@gnu.org Wed Apr 09 16:08:34 2003 Return-path: Original-Received: from monty-python.gnu.org ([199.232.76.173]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 193GFe-0001QH-00 for ; Wed, 09 Apr 2003 16:08:34 +0200 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.10.13) id 193GCy-0001yn-03 for gnu-help-gnu-emacs@m.gmane.org; Wed, 09 Apr 2003 10:05:48 -0400 Original-Path: shelby.stanford.edu!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.icl.net!newsfeed.fjserv.net!newsfeed.freenet.de!feed.news.nacamar.de!fu-berlin.de!uni-berlin.de!p50877b4c.dip.t-dialin.NET!not-for-mail Original-Newsgroups: gnu.emacs.help Original-Lines: 44 Original-NNTP-Posting-Host: p50877b4c.dip.t-dialin.net (80.135.123.76) Original-X-Trace: fu-berlin.de 1049896907 10428994 80.135.123.76 (16 [73968]) Mail-Copies-To: never User-Agent: Gnus/5.090018 (Oort Gnus v0.18) Emacs/21.3.50 (gnu/linux) Cancel-Lock: sha1:GlVoDGUSmXEviiiF2fyxC8K1L5c= Original-Xref: shelby.stanford.edu gnu.emacs.help:111818 Original-To: help-gnu-emacs@gnu.org X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1b5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Help: List-Post: List-Subscribe: , List-Archive: List-Unsubscribe: , Errors-To: help-gnu-emacs-bounces+gnu-help-gnu-emacs=m.gmane.org@gnu.org Xref: main.gmane.org gmane.emacs.help:8319 X-Report-Spam: http://spam.gmane.org/gmane.emacs.help:8319 Gurucharan 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.