LISP - List vs Vectors

Lisp - Choosing the Right Sequence: List vs. Vector

Common Lisp offers two fundamental sequence types for storing collections of elements: lists and vectors. While they can often be used interchangeably, their underlying implementation leads to significant differences in performance and suitability for different tasks. Choosing the correct one is a key aspect of writing efficient Lisp code.

The List: A Chain of Links

A list is implemented as a linked list of cons cells. Each cell holds an element (car) and a pointer to the next cell (cdr). Think of it as a train, where each car only knows about the one immediately behind it.

• Implementation: Linked cons cells.
• Memory Storage: Elements can be scattered anywhere in memory (non-contiguous).
• Access: Sequential. To get to the 100th element, Lisp must traverse the first 99. This is O(n) complexity.
• Modification: Extremely efficient at the front. Adding (push) or removing an element at the beginning is an O(1) operation.

The Vector: A Numbered Shelf

A vector is a one-dimensional array. Think of it as a numbered shelf or a set of mailboxes in a lobby. You can go directly to any position if you know its number (index).

• Implementation: A single block of memory, like an array.
• Memory Storage: Stored in a contiguous block of memory.
• Access: Random Access. Accessing any element by its index using aref is immediate. This is O(1) complexity.
• Modification: Can be less efficient if it involves resizing the vector. However, Lisp provides adjustable vectors and fill-pointers to make appending efficient in practice.

Head-to-Head Comparison

Feature	List	Vector
Analogy	A chain or train	A numbered shelf or array
Access Time (Nth element)	Slow, O(n) - (nth n list)	Fast, O(1) - (aref vec n)
Prepending an element	Fast, O(1) - (push item list)	Slow, O(n) - requires creating a new vector
Memory Layout	Non-Contiguous	Contiguous
Best Use Case	Stacks, dynamic growth from the front, symbolic processing.	Fast random lookups, numerical data, fixed-size or append-heavy collections.

Performance in Practice: A Concrete Example

Let’s demonstrate the access time difference. The time macro shows us how long an expression takes to execute.

;; main.lisp
(let* ((size 100000)
       (long-list (loop for i from 1 to size collect i))
       (long-vector (coerce long-list 'vector)))

  (format t "--- Accessing the last element (~Dth) ---~%" (1- size))

  (format t "Time to access in List:~%")
  (time (nth (1- size) long-list))

  (format t "~%Time to access in Vector:~%")
  (time (aref long-vector (1- size))))

Typical Output

--- Accessing the last element (99999th) ---
Time to access in List:
Evaluation took:
  0.000 seconds of real time
  ... (some small amount of time)

Time to access in Vector:
Evaluation took:
  0.000 seconds of real time
  ... (a much smaller amount of time, effectively instantaneous)

While both might seem fast for this size, the difference in CPU cycles and memory access patterns is huge. For a list, the time grows linearly with the index, while for a vector, it remains constant.

How to Choose

• Choose a LIST when…
  • You frequently add or remove elements from the front of the sequence (e.g., implementing a stack).
  • The code naturally maps to recursive patterns (car/cdr).
  • The size of the collection is highly dynamic and unpredictable.
• Choose a VECTOR when…
  • You need to access elements by index quickly and frequently.
  • The size of the collection is known beforehand or changes infrequently.
  • You are working with numerical data that benefits from contiguous memory layout (better cache performance).
  • You need to build a collection by appending. Use an adjustable vector with a fill-pointer for high efficiency.

Pro-Tip: Beyond Lists and Vectors

Don’t forget other data structures! If you need key-value mapping, a hash table is almost always superior to a list of pairs (an association list).