Data structure

Junior

Essence

A data structure is a way to organise data in memory so that the operations you need (insert, search, delete, traverse) are fast. Choosing one is choosing a trade-off: an array gives O(1) access by index but O(n) search; a hash table gives O(1) search but no ordering.

What Swift ships with

• Array — a contiguous buffer. Index O(1), append amortised O(1), insert(at: 0)/remove(at:) O(n), contains/firstIndex O(n).
• Dictionary — a key → value hash table. Lookup, insert, delete O(1) on average. Keys must be Hashable. Order is not guaranteed.
• Set — a hash table of unique values. contains, insert, remove O(1) on average; union, intersection O(n).
• String — a collection of Character (grapheme clusters), so count is O(n) and there is no Int subscript.
• ContiguousArray, ArraySlice, Substring — views without copying.
• In the swift-collections package: Deque, OrderedSet, OrderedDictionary, Heap.

All of them are value types with copy-on-write: assignment shares the buffer, and a real copy happens only on the first mutation of one of the copies.

var numbers = [3, 1, 2]
numbers.append(4)            // amortised O(1)
numbers.insert(0, at: 0)     // O(n) — shifts every element
_ = numbers.contains(2)      // O(n)

var ages: [String: Int] = ["Ann": 30]
ages["Bob"] = 25             // O(1) on average
_ = ages["Ann"]              // O(1) on average

let ids: Set = [1, 2, 3]
_ = ids.contains(2)          // O(1) on average

What you may be asked to implement

Stack, queue, linked list and tree are not in the standard library and often come up in live coding:

struct Stack<Element> {
    private var items: [Element] = []
    mutating func push(_ x: Element) { items.append(x) }
    mutating func pop() -> Element? { items.popLast() }
    var top: Element? { items.last }
}

final class ListNode<T> {
    var value: T
    var next: ListNode?
    init(_ value: T, next: ListNode? = nil) {
        self.value = value; self.next = next
    }
}

What the interviewer looks for

• Can you state the complexity of Array/Dictionary/Set operations and explain why contains on an array inside a loop is O(n²).
• Do you understand that removeFirst() on an array is O(n), and that a queue needs a Deque or two stacks.
• Do you know why linked lists are rare on iOS (cache misses, per-node heap allocations) — an array is almost always faster.