FundamentalsFundamentals

Strings & Immutability

An immutable (in most languages) sequence of characters stored as an array, with its own family of matching and counting algorithms.

Learn String →
i
0
m
1
m
2
u
3
t
4
a
5
b
6
l
7
e
8
1/27"immutable" is laid out exactly like an array of 9 characters: a contiguous run of slots, each reachable by index. The one extra rule is that no slot may ever be overwritten, and every cost on the following steps falls out of that single restriction.
Character already consumed / storedCharacter being written nowCharacter copied by this operationSlice being takenResult of the operationUntouched
PseudocodeLearn String →
1s = "immutable"              # a fixed run of characters
2s[i]                         # read: one offset, no copy
3s[i:j]                       # slice: a brand-new string
4result = ""                  # the trap
5for c in s:
6  result = result + c        # allocate |result|+1, copy |result| chars
7parts = []                   # the fix
8for c in s: parts.append(c)  # amortized O(1), copies nothing
9result = "".join(parts)      # one allocation, each char copied once
Variables
length9
charsCopied0
Complexity
access O(1)
search O(n + m)
insert O(n)
delete O(n)
Speed