Por la importancia dentro de LISP del tipo de datos LISTA, citamos inextenso el apartado 2.4 de CLTL2,

Un CONS es una estructura de información que contiene doscomponentes llamados el CAR y el CDR. La utilización fundamental de losCONSES es como representación de LISTAS.

Una LISTA se define recursivamente ya sea como la listavacía o como un CONS cuyo componente CDR es una lista. Una lista es, porconsiguiente, una cadena de CONSES enlazados por sus componentes CDR yterminada por un NIL, la lista vacía. Los componentes CAR de los consesson conocidos como los elementos de la lista. Para cada elemento de la listahay un CONS. La lista vacía no tiene ningún elemento.

Para comprender mejor lo anterior, adelantaremos la mención de lafunción básica de construcción de listas, que es lafunción CONS (que se explica en el apartadoFUNCIONES DE CONSTRUCCIÓN DELISTAS). Expresado en términos de esta función, la anteriordefinición de una lista como una cadena de CONSES sería:

Una LISTA se expresa mediante la escritura de los elementos dela lista ordenados, separados por espacios en blanco (caracteres de espacio,tabulador o retorno) y rodeados por paréntesis. Por ejemplo:

 (a b c)          ;Una lista de tres símbolos
 (2.0 (a 1) "*")   ;Una lista de tres cosas diferentes: un número real
                  ;otra lista y un carácter asterisco

La lista vacía puede por lo tanto ser expresada como (), ya que setrata de una lista sin elementos.

Una lista punteada (dotted list) es una cuyo último cons no tiene NILcomo su CDR, sino otro objeto de información (que tampoco será unCONS, ya que entonces el CONS anteriormente mencionado no hubiera sido elúltimo CONS de la lista).

Tal tipo de lista se conoce como "punteada" debido ala notación especial que se emplea en ella: los elementos de la lista seescriben, al igual que antes, entre paréntesis, pero ... antes delparéntesis derecho se escriben un punto (rodeado por espacios en blanco)y entonces el CDR del último CONS. Como caso especial, un CONS aisladose expresa escribiendo el CAR y el CDR entre paréntesis y separados porun punto rodeado de espacios (par punteado). Por ejemplo:

(a . 4)      ;Un cons cuyo car es el símbolo a 
             ;y cuyo cdr es un entero 
(a b c . d)  ;Una lista punteada con tres elementos cuyo cons final 
             ;tiene el símbolo d en su cdr

Con frecuencia se utiliza el término lista para hacer referenciatanto a verdaderas listas como a listas punteadas. Cuando resulta importante ladistinción, se utilizará el término "verdaderalista" para referirnos a una lista terminada por NIL. La mayoría delas funciones que se dice operan sobre listas esperan recibir verdaderas listascomo argumento.

Por ejemplo, si en el ejemplo de concatenación de CONSES anteriorel elemento de la derecha del último CONS no hubiera sido NIL (lo quehubiera incluido un par punteado en la lista), el pasar esta lista comoargumento a una función de tratamiento de listas hubiera producido endeterminados casos un error:

A veces se utiliza el término árbol para referirsea algunos CONS y todos los demás CONSES accesibles a él de maneratransitiva a través de enlaces de CAR y CDR hasta alcanzar objetosNO-CONS; éstos NO-CONSES son conocidos como las hojas del árbol.

Representación de LISTAS como árboles.
Tomado de: Cortés y Sierra, LISP. Editorial Marcombo, Barcelona.1987.

Las listas, las listas punteadas y los árboles no sontipos de datos mutuamente excluyentes; no son más que puntos de vistaútiles en torno a las estructuras de CONSES. Hay aún otrostérminos tales como LISTA DE ASOCIACIÓN. Ninguno de éstosson verdaderos tipos de datos LISP.
Los CONSES constituyen un tipo de dato, y NIL es el único objeto de tipoNULL. El tipo de dato LISTA significa en LISP la unión de los tipos dedatos CONS y NULL, y por ello engloba tanto las listas verdaderas como laslistas punteadas.

FORMATOS DE LISTAS:

Además de lo apuntado más arriba, es conveniente distinguirentre los siguientes tres formatos de listas:

• LISTAS DE UN NIVEL

  Contienen sólo átomos.

• LISTAS ANIDADAS

  Contienen a su vez otras listas que se dicen ‘anidadas’. Estas listas anidadas suelen ser conocidas como sub-listas. El número de niveles de anidación no está restringido ni en su profundidad ni en su complejidad. El nivel más externo lo llamamos nivel superior o primer nivel. A los elementos que conforman este nivel los llamamos elementos de primer nivel.

• LISTAS DE ASOCIACIÓN (A-LIST)

  Son listas anidadas que se utilizan con frecuencia como estructura de datos en LISP. Una A-LIST es una lista de pares (CONSES) en que cada par constituye una asociación. El CAR de uno de estos pares se conoce como la CLAVE y el CDR constituye el DATO. Una ventaja de la representación como A-LIST es la posibilidad de incrementarla añadiéndole nuevas entradas al principio de la lista. Más aún, como la función de búsqueda ASSOC recorre la A-LIST de manera ordenada, las nuevas entradas pueden "enmascarar" las más antiguas de manera que la información puede ser modificada de forma no destructiva.

• LA LISTA VACÍA (NIL)

  Como se dijo antes, es la que no contiene ningún elemento. Se indicacomo () y recibe un nombre particular, el de NIL.
  La lista vacía tiene un status peculiar en LISP. Es a la vez unátomo y una lista. Como símbolo representa el valor lógicode FALSO:

_$ ()
nil
_$ (atom nil)
T
_$ (listp nil)
T

• CIERTO Y FALSO

  Su negación (not nil) sería el símbolo T que representa lacondición lógica de CIERTO.
  El símbolo T es también una constante en el sentido deque sólo se representa a sí mismo.
  En Visual LISP, nil y T así como otros elementos que incluyen losoperadores aritméticos (+, -. etc.) son símbolos protegidos.Cualquier intento de asignarle otro valor producirá un mensaje deadvertencia:
  
  
  
  Este mensaje aparece como la opción por defecto y pide si se deseaentrar en un bucle de interrupción (break loop). Si se escoge No, elvalor del símbolo es modificado. Si se selecciona Sí, seinterrumpe el procesamiento y se entra en un ciclo de interrupción deVisual LISP, lo que se conoce por el aspecto del símbolo del evaluador,por ejemplo: _1_$.
  
  
  El control se ha trasladado a la consola de Visual LISP. Para asignar valor alsímbolo y continuar el procesamiento se deberá pular elbotón Continuar  en la barra deherramientas de Visual LISP. Para abortar el procesamiento se pulsaráReset  .