Structure Sharing in Lisp vs. Other Programming Languages

2025-07-04

Lisp lists share structure and Javascript and Python list classes don’t.

This is a fundamental difference between how Lisp and imperative languages handle list data structures.The fundamental difference comes down to data structure design and memory model:

LISP: Linked Cons Cells with Sharing

Structure: Lists are chains of cons cells (pairs):

(a b c d) = [a|•]→[b|•]→[c|•]→[d|null]

Sharing: When you cons onto a list, you reuse the existing structure:

(setq base '(c d e)) ; [c|•]→[d|•]→[e|null]

(setq list1 (cons 'b base)) ; [b|•]→↑ (points to base)

(setq list2 (cons 'a base)) ; [a|•]→↑ (points to same base)

Key insight: list1 and list2 literally share the same memory for (c d e)!

JavaScript/Python: Contiguous Arrays

Structure: Arrays are contiguous blocks of memory:

[a, b, c, d] = [a][b][c][d] (sequential memory)

No sharing: Prepending requires copying the entire array:

const base = ['c', 'd', 'e']; // [c][d][e]

const list1 = ['b', ...base]; // [b][c][d][e] (NEW copy)

const list2 = ['a', ...base]; // [a][c][d][e] (ANOTHER copy)

Why the Difference?

1. Memory Model:

   • Lisp: Pointer-based (can share references)

   • Arrays: Index-based (must be contiguous)

2. Mutability:

1. Lisp: Traditionally immutable (safe to share)

2. Arrays: Mutable (sharing would be dangerous)

3. Performance Trade-offs:

1. Lisp: O(1) prepend, O(n) random access

2. Arrays: O(n) prepend, O(1) random access

Practical Impact

Lisp advantages:

• Building 1000 variations of a base list: only 1000 new cells needed

• Memory efficient for functional programming patterns

• Fast prepend operations

Array advantages:

• Fast random access by index

• Cache-friendly (data locality)

• Better for numerical/scientific computing

This is why functional languages (Lisp, Haskell, Clojure) use linked structures, while imperative languages (JavaScript, Python, Java) use arrays. Each optimizes for different use patterns!

See Also

Email: ptcomputingsimplicity@gmail.com

References: https://guitarvydas.github.io/2024/01/06/References.html

Blog: guitarvydas.github.io

Videos: https://www.youtube.com/@programmingsimplicity2980

Discord: https://discord.gg/65YZUh6Jpq

Leanpub: [WIP] https://leanpub.com/u/paul-tarvydas

Twitter: @paul_tarvydas

Substack: paultarvydas.substack.com