Collection types: lists, vectors, maps, sets

The persistent-data-structures lesson introduced the four core collections as a family. This page drills into each one: what it costs, what it guarantees, when to reach for it, and what its sorted/unsorted constructors look like. Pick the type whose abstract operations match how the data is going to be read — then performance follows for free.

Lists — front-loaded, sequential

A list is a singly-linked sequence: O(1) at the front, O(n) anywhere else. Lists are what the reader produces for (…) — they're the syntax of the language as well as a data structure.

Notice c‌o‌n‌jclojure.core/conjAdd an element to a collection (vector: append, list: prepend).view on clojuredocs → adds to the front of a list. This is the only collection where c‌o‌n‌jclojure.core/conjAdd an element to a collection (vector: append, list: prepend).view on clojuredocs → doesn't append at "the natural end."

Use a list when you'd say "treat this like a stack" — you push and pop at one end and never index in the middle.

Vectors — random access, append-friendly

A vector is the default ordered collection. [1 2 3] is a vector; so is (vector 1 2 3) and (vec '(1 2 3)). Internally it's a trie that gives O(log32 n) indexing, update, and append — fast enough to call O(1) for practical sizes.

peek / pop on a vector work at the tail — vectors are the right choice if you need stack semantics with random access.

Maps — keyed lookup

Maps come in two flavors: hash-maps (the default; unordered) and sorted-maps (ordered by key comparator).

Sorted maps preserve key order on iteration, which is invaluable when you want stable output or range queries:

subseq is the headline feature of sorted maps — it returns a seq of entries whose keys satisfy a comparator condition, in O(log n).

Sets — membership

#{} is a set literal. Sets answer "is this in here?" in (essentially) O(1) and remove duplicates automatically. Like maps, sets come in unordered (hash-set, the default) and sorted-set forms.

(s x) returns x if present, else nil — sets and maps are both callable as functions of their keys. That trick lets you use them directly as predicates:

Sorted sets give you the same subseq range-query power as sorted maps:

Picking the right type

Two practical heuristics: default to vectors for ordered data and maps for everything else; reach for sorted variants only when you actually need stable iteration order or range queries (subseq / rsubseq).

Check yourself

? quiz

What does `(conj '(1 2 3) 0)` return, and why?

• a)(1 2 3 0) — conj always appends at the end.
• b)(0 1 2 3) — because lists prepend with conj.
• c)[0 1 2 3] — conj coerces lists to vectors.
• d)An error — conj only works on vectors and maps.

Exercise

Given the data below, build (in one expression) a sorted-map from city → population so that iterating it yields cities in alphabetical order. Then use subseq to return only the entries whose key is between "m" and "r" (inclusive of "m", exclusive of "r").