-
Notifications
You must be signed in to change notification settings - Fork 0
002 — Arrays and Strings
The array is the first data structure you ever meet, and it's also the one you'll use the most. Strings ride along in this chapter because in Swift, a String is not a simple array of characters — and that distinction bites people constantly in interviews.
Picture a parking garage with numbered spots: 0, 1, 2, 3, ... all the way to n - 1. Every spot is the exact same size, and they're all lined up right next to each other with no gaps.
- 🚗 If someone hands you spot number
42and asks "what car is parked there," you drive straight there. No searching. - 🧱 The spots being contiguous (right next to each other, no gaps) is exactly why that direct lookup works — the garage attendant just does math:
garage_start_address + (42 × spot_width). - 🚧 Now try to insert a new car at spot
0. Every other car has to shift over one spot to make room. Spot1's car moves to2, spot2's car moves to3, and so on. That's a lot of repainting numbers.
That trade-off — instant access by position, expensive insertion in the middle — is the entire personality of an array.
An array is a contiguous block of memory holding elements of the same type, indexed from 0. Because the memory is contiguous and every element is the same size, the address of element i is just arithmetic — no searching required. That's what makes array[i] O(1).
Swift's Array is a value type with copy-on-write: assigning or passing an array copies a reference cheaply until one of the copies is mutated, at which point Swift copies the actual buffer. It also grows dynamically — when you append past current capacity, Swift allocates a new, larger buffer (typically doubling) and copies everything over.
A Swift String, however, is a collection of Characters — and a Character is an extended grapheme cluster, which can be made of multiple Unicode scalars (think "é" as e + a combining accent, or a flag emoji made of two scalars). Because characters can be variable-width, Swift can't jump straight to "the 5th character" the way it can jump to array[5]. That's why String uses String.Index instead of Int, and why s.count is O(n) — Swift has to walk the string counting grapheme cluster boundaries.
Reach for an array when:
- You need fast random access by position.
- You know the data is roughly ordered/sequential (a list of scores, a row of grid cells, a buffer of recent events).
- You're building another data structure on top of it (stacks, heaps, hash table buckets all commonly use arrays underneath).
Reach for a String, carefully, when:
- You're handling text — but budget for the fact that indexing and length are not
O(1)the way they are in C or naive-Unicode languages. If you need repeated random access into text, convert to[Character]once (O(n)up front) and then index that array (O(1)per access after).
Array — contiguous, indexed memory:
index: 0 1 2 3 4
┌─────┬─────┬─────┬─────┬─────┐
value: │ 10 │ 25 │ 7 │ 42 │ 3 │
└─────┴─────┴─────┴─────┴─────┘
▲ ▲
arr[0] arr[4]
O(1) jump straight to any index
Insertion at the front — everyone shifts right:
insert 99 at index 0:
before: │ 10 │ 25 │ 7 │ 42 │ 3 │
shift → → → →
after: │ 99 │ 10 │ 25 │ 7 │ 42 │ 3 │
String — variable-width grapheme clusters, no Int index:
"café"
Unicode scalars: c a f e ́(combining accent)
Characters: [c] [a] [f] [é] ← 4 Characters, 5 scalars
▲
"é" is ONE Character made of TWO scalars —
you can't compute its byte offset with simple math.
// Array
var scores = [10, 25, 7, 42, 3]
scores.append(99) // O(1) amortized — add to the end
scores.insert(1, at: 0) // O(n) — everything shifts right
let first = scores[0] // O(1) — direct index
let found = scores.contains(42) // O(n) — linear scan, no shortcuts
scores.removeLast() // O(1)
scores.remove(at: 0) // O(n) — everything shifts left
// String
let word = "café"
print(word.count) // O(n) — walks grapheme clusters
// Random access into text: convert once, index many times
let letters = Array(word) // O(n) one-time conversion
let thirdLetter = letters[2] // O(1) after conversionInterviews sometimes ask you to build the growable-array mechanism yourself — allocate a fixed buffer, and double it when it fills up. Here's a minimal, correct version using UnsafeMutablePointer, implemented as a class: since the buffer is manually allocated, a reference type keeps allocation and teardown symmetric — one deinit frees exactly what init/grow() allocated. A struct wrapping a raw pointer would silently alias its buffer across "copies" (mutating one would mutate the other, breaking Swift's value semantics) and could never define a deinit, so the buffer would leak. Note that, unlike Swift's Array, this type is a reference type: let b = a does not create an independent copy — a and b point at the same buffer, and mutating through one is visible through the other.
final class DynamicArray<T> {
private var buffer: UnsafeMutablePointer<T>
private var capacity: Int
private(set) var count = 0
init(initialCapacity: Int = 2) {
capacity = max(initialCapacity, 1)
buffer = UnsafeMutablePointer<T>.allocate(capacity: capacity)
}
deinit {
buffer.deinitialize(count: count)
buffer.deallocate()
}
func append(_ value: T) {
if count == capacity {
grow()
}
buffer.advanced(by: count).initialize(to: value)
count += 1
}
subscript(index: Int) -> T {
precondition(index >= 0 && index < count, "Index out of range")
return buffer[index]
}
private func grow() {
let newCapacity = capacity * 2
let newBuffer = UnsafeMutablePointer<T>.allocate(capacity: newCapacity)
newBuffer.moveInitialize(from: buffer, count: count) // move existing elements
buffer.deallocate()
buffer = newBuffer
capacity = newCapacity
}
}Every time grow() runs, capacity doubles — so most append calls are O(1), and the occasional resize gets "spread out" over many cheap calls. That's the amortized O(1) you'll see in the table below.
| Operation | Big-O | Why |
|---|---|---|
Access by index (arr[i]) |
O(1) |
Contiguous memory — address is computed by arithmetic, no search. See Big-O Notation. |
| Append at end |
O(1) amortized |
Usually just writes to the next free slot; occasionally triggers a resize that copies everything (O(n)), but that cost is spread across many appends. |
| Insert at front / arbitrary index | O(n) |
Every element after the insertion point must shift over by one. |
| Remove at front / arbitrary index | O(n) |
Every element after the removed one must shift back by one. |
| Search (unsorted) | O(n) |
No shortcuts — worst case you check every element. |
String.count |
O(n) |
Swift must walk grapheme cluster boundaries; characters are variable-width. |
String index into [Character] (pre-converted) |
O(1) |
Once converted to [Character], it's a plain array — direct index. |
An array is a numbered row of parking spots — grab any spot instantly, but shove a new car into the middle and everyone behind it has to scoot over.
Given let word = "résumé", explain why word[2] does not compile in Swift, what you'd need to write instead to get the third Character, and why repeatedly doing that inside a loop would be a performance trap compared to converting word to [Character] once first.
⬅️ Previous: Big-O Notation · Next: Hash Maps and Hash Sets ➡️