NSMutableArray: Mutating Ordered Collections and Their Cost

Learn the core mutation API of NSMutableArray — adding, inserting, removing, replacing, and sorting elements — and reason correctly about the time complexity of each operation so you can choose the right approach for large or performance-sensitive arrays.

NSArray, which you have already used extensively, is immutable: once created, its contents and length are fixed for the lifetime of the object. That immutability is a feature — it lets you hand an NSArray to another object without worrying that object will change it behind your back — but plenty of real programs need a list that grows, shrinks, and reorders itself as the program runs: a table view's data source, a queue of pending network requests, a running list of search results. NSMutableArray is Foundation's answer: a subclass of NSArray that adds a full set of mutation methods while keeping everything NSArray already gave you — fast indexed access, fast-enumeration, objectAtIndex:, and so on. Because NSMutableArray is a subclass, every NSMutableArray is a valid NSArray, and you can pass one anywhere an NSArray is expected — which is precisely the source of the aliasing gotcha this lesson closes with.

Creating a Mutable Array

You create an NSMutableArray much like an NSArray, but with mutable-specific initializers. [NSMutableArray array] gives you an empty mutable array ready to grow; [NSMutableArray arrayWithCapacity:10] also gives you an empty array, but hints to Foundation that you expect roughly ten elements, letting it pre-allocate backing storage and avoid repeated reallocation as you add items. The capacity hint does not cap the array — you can still add an eleventh, a hundredth, a thousandth object — it is purely a performance hint, and getting it wrong costs you nothing but a little wasted or re-allocated memory.

You can also derive a mutable array from an existing immutable one with [someArray mutableCopy], which returns a new, independent NSMutableArray containing the same elements (each element itself is not copied, only the array structure is — the elements are retained, not deep-copied). This is the standard way to take a fixed NSArray you were handed and get a working copy you can freely mutate without disturbing the original.

Adding and Inserting Elements

addObject: appends a single object to the end of the array, growing its count by one. It is the most common mutation you will write, and Foundation's backing storage is designed to make repeated addObject: calls efficient in the common case, even though — as the complexity section below explains — no individual call carries a guaranteed constant-time promise from the documentation.

insertObject:atIndex: places an object at a specific index, shifting every element from that index onward one slot to the right to make room. [array insertObject:@"urgent" atIndex:0] inserts at the front, pushing every existing element back by one position. Passing an index equal to array.count is equivalent to appending; passing an index greater than array.count, or a negative index, raises an NSRangeException and crashes your program, so bounds-checking matters here just as it does for objectAtIndex:.

There is also addObjectsFromArray:, which appends every element of another array in order, and insertObjects:atIndexes:, which inserts multiple objects at multiple positions described by an NSIndexSet in a single call — useful when a batch of insertions needs to happen atomically from the caller's point of view, without an intermediate state where only some elements have been added.

Removing and Replacing Elements

removeObject: searches the array for the first element that is equal (via isEqual:) to the object you pass, and removes it if found; if no matching element exists, it does nothing — it does not raise an exception. removeObjectAtIndex: instead removes whatever is at a specific index, and — like insertObject:atIndex: — raises an NSRangeException if that index is out of bounds. removeAllObjects empties the array entirely in one call, which is both clearer and faster than looping and removing one element at a time.

replaceObjectAtIndex:withObject: swaps out the object at a given index for a new one, without changing the array's length or shifting any other elements. This is the method to reach for when you know exactly which slot needs a new value — for example, updating one row's data after an edit — rather than removing the old value and re-inserting the new one, which would do unnecessary shifting work for no benefit.

All of the removal and insertion methods that take an index are strict about bounds. A very common source of crashes in table-view and collection-view code is an off-by-one error where the data source array and the number of visible rows briefly disagree during an update; always double-check that the index you pass is < array.count before calling a by-index mutator, or use the NSObject-provided safety of removeObject: when you have the value but not a trusted index.

Sorting an NSMutableArray In Place

Unlike NSArray's sortedArrayUsingSelector: and sortedArrayUsingComparator: — which return a brand-new sorted array and leave the receiver untouched — NSMutableArray adds in-place variants: sortUsingSelector: and sortUsingComparator: reorder the receiver's own elements and return nothing. [people sortUsingSelector:@selector(compare:)] sorts people in place using whatever compare: method the element class implements, while [people sortUsingComparator:^NSComparisonResult(Person *a, Person *b) { return [a.lastName compare:b.lastName]; }] sorts using an inline block, which is usually the more readable choice when the comparison logic is specific to one call site.

Sorting in place is the right choice when nothing else in the program holds a reference to the old, unsorted ordering and needs it preserved — for example, an array that only exists to back one table view. When other code depends on the original order surviving, prefer the non-mutating NSArray sort methods, or explicitly mutableCopy before sorting, so you do not silently reorder data another part of the program is still relying on.

Complexity: Appending vs. Inserting and Removing

NSMutableArray is backed by a contiguous, array-like storage buffer (its exact internal representation is a private implementation detail of Foundation, and has changed between OS releases, but the complexity characteristics you should design around have stayed stable). Appending with addObject: is amortized close to O(1): most calls just write into already-allocated space and bump the count, and on the occasional call where the buffer is full, Foundation reallocates a larger buffer and copies existing elements over — an O(n) operation — but it does so rarely enough, and grows the buffer aggressively enough, that the average cost per addObject: call, taken over many calls, stays small and roughly constant.

Inserting or removing at the front or in the middle is a different story: insertObject:atIndex:0 must shift every one of the array's existing elements one slot to the right to make room, which is O(n) work — proportional to the array's current length — for a single insertion. removeObjectAtIndex:0 is symmetric: removing the first element requires shifting every remaining element one slot to the left, again O(n). The deeper in the middle of the array you insert or remove, the more elements have to shift, but even a middle insertion still touches, on average, roughly half the array — still O(n), just with a smaller constant.

This matters enormously once an array holds thousands or millions of elements. A loop that repeatedly calls insertObject:atIndex:0 to prepend N items to a growing array does O(n) work on each of N insertions, for O(n²) total work — a program that feels instant at 100 elements can become visibly slow at 100,000. Conceptually, this is exactly the trade-off a linked list is built to avoid: a linked-list-style structure can insert or remove at any node it already has a reference to in true O(1) time, because nothing needs to shift — only a couple of pointers are rewritten — at the cost of losing O(1) indexed access (objectAtIndex: on a linked list means walking from the front). NSMutableArray deliberately makes the opposite trade-off: it optimizes for indexed access and end-appending, at the cost of expensive front/middle mutation. Knowing which side of that trade-off your algorithm needs is part of choosing the right data structure, and is a theme this course returns to whenever a new collection type is introduced.

• addObject: (append at end) — amortized ~O(1). • insertObject:atIndex: / removeObjectAtIndex: at the front or middle — O(n), because elements must shift. • objectAtIndex: (indexed read) — O(1), same as NSArray. • A linked-list-style structure inverts this trade-off: O(1) insert/remove given a node reference, but no O(1) indexed access.

The Same copy-vs-Mutable-Property Gotcha

This course already covered a dangerous aliasing bug with NSMutableString: if a class stores a caller-supplied NSMutableString directly in an instance variable instead of copying it, the caller can keep a reference to that same mutable object and change its contents later, silently altering what the class thinks it owns. The exact same hazard applies to NSMutableArray, for exactly the same reason — NSMutableArray is a reference type, and assigning it to an ivar or property copies the pointer, not the contents.

If a ShoppingCart class declares @property (nonatomic, strong) NSArray *items; and its initializer does self.items = suppliedArray; without copying, and the caller happens to pass in an NSMutableArray (which, remember, is a valid NSArray thanks to subclassing), the caller can later call addObject: or removeObjectAtIndex: on that same array instance and change what cart.items contains — even though items is declared as if it were an immutable NSArray, and even though ShoppingCart never touched it after the initializer ran. The fix is identical to the NSMutableString case: declare the property copy rather than strong (@property (nonatomic, copy) NSArray *items;), which makes the synthesized setter invoke copy on whatever is assigned, producing an independent immutable NSArray no outside caller can subsequently mutate.

Core NSMutableArray Mutation Methods

NSMutableArray *list = [NSMutableArray array];

[list addObject:@"first"];
[list insertObject:@"zero" atIndex:0];
[list removeObject:@"first"];
[list removeObjectAtIndex:0];
[list replaceObjectAtIndex:0 withObject:@"replacement"];
[list sortUsingSelector:@selector(compare:)];
[list sortUsingComparator:^NSComparisonResult(id a, id b) {
    return [a compare:b];
}];

Code Examples

This walks through the everyday mutation vocabulary: arrayWithCapacity: pre-sizes storage, three addObject: calls build the initial list, insertObject:atIndex:0 pushes a new item to the front (an O(n) shift of the three existing elements), removeObjectAtIndex: deletes by position, and replaceObjectAtIndex:withObject: swaps a value in place without touching the array's length.

[tasks insertObject:@"Stand-up meeting" atIndex:0];

sortUsingComparator: reorders people in place using an inline block that compares each pair of Person objects by name; because it mutates the receiver rather than returning a new array, the loop afterward sees the sorted order directly in people with no separate variable needed.

[people sortUsingComparator:^NSComparisonResult(Person *a, Person *b) {

Because items is declared copy, both the synthesized setter and the explicit [items copy] in the initializer produce an independent NSArray at the moment it is stored. The caller's later mutation of basket (which is an NSMutableArray, and therefore a valid argument for an NSArray *-typed parameter) has no effect on what cart already snapshotted, closing the exact aliasing hole a strong property would leave open.

Common mistake: Declaring the property strong and storing the caller's array directly (self.items = items;) lets any caller who happens to pass an NSMutableArray keep mutating cart.items after the fact, silently changing the cart's contents from outside the class.

NSMutableArray<NSString *> *tasks = [NSMutableArray arrayWithCapacity:4];
[tasks addObject:@"Write report"];
[tasks addObject:@"Review PR"];
[tasks addObject:@"Deploy build"];

[tasks insertObject:@"Stand-up meeting" atIndex:0];
NSLog(@"%@", tasks);
// ("Stand-up meeting", "Write report", "Review PR", "Deploy build")

[tasks removeObjectAtIndex:1]; // removes "Write report"
[tasks replaceObjectAtIndex:0 withObject:@"Daily sync"];
NSLog(@"%@", tasks);
// ("Daily sync", "Review PR", "Deploy build")

NSMutableArray<Person *> *people = [NSMutableArray arrayWithObjects:
    [[Person alloc] initWithName:@"Zara" age:41],
    [[Person alloc] initWithName:@"Amir" age:29],
    [[Person alloc] initWithName:@"Mina" age:35],
    nil];

[people sortUsingComparator:^NSComparisonResult(Person *a, Person *b) {
    return [a.name compare:b.name];
}];

for (Person *p in people) {
    NSLog(@"%@", p.name);
}
// Amir
// Mina
// Zara

@interface ShoppingCart : NSObject
@property (nonatomic, copy) NSArray<NSString *> *items; // copy, not strong
@end

@implementation ShoppingCart
- (instancetype)initWithItems:(NSArray<NSString *> *)items {
    if (self = [super init]) {
        _items = [items copy]; // belt-and-suspenders in a designated initializer
    }
    return self;
}
@end

// Caller code:
NSMutableArray<NSString *> *basket = [NSMutableArray arrayWithObjects:@"Bread", @"Milk", nil];
ShoppingCart *cart = [[ShoppingCart alloc] initWithItems:basket];
[basket addObject:@"Eggs"]; // does NOT affect cart.items — it holds its own copy

Why Front-Insertion Is O(n)

Appending at the end never requires this shift, which is why addObject: stays cheap while insertObject:atIndex:0 gets more expensive as the array grows.

Before insertObject:@"X" atIndex:0
[ A ][ B ][ C ][ D ]

Every element shifts right one slot to make room:
[ _ ][ A ][ B ][ C ][ D ]

Then X fills the freed slot:
[ X ][ A ][ B ][ C ][ D ]

Four elements had to move for one insertion —
the larger the array, the more elements shift.

Important Rules

Prefer addObject: (end-appending) over insertObject:atIndex: at the front whenever order allows it — it avoids the O(n) shift entirely.

removeObject: is safe on a value that may not be present; by-index methods (removeObjectAtIndex:, insertObject:atIndex:) crash on an out-of-bounds index.

sortUsingSelector: / sortUsingComparator: mutate the receiver in place; use NSArray's non-mutating sort methods when the original order must be preserved elsewhere.

Declare a property that stores an array as copy, not strong, whenever a caller might hand you an NSMutableArray you must not let them keep mutating.

For algorithms that repeatedly insert or remove at the front of a large collection, reconsider the data structure — NSMutableArray is the wrong tool for that access pattern.

Table View Data Sources

Almost every scrolling list in a Cocoa or Cocoa Touch app is backed by an NSMutableArray that holds the model objects for each row. When a user deletes a row, the app calls removeObjectAtIndex: on that backing array before or alongside animating the row out of the table; when new data arrives from a network response, the app typically builds a fresh NSMutableArray from the response and either replaces the data source wholesale or calls addObjectsFromArray: to append incoming pages, then reloads the affected rows. Understanding that removeObjectAtIndex: and insertObject:atIndex: are O(n) is part of why large data sources are paginated rather than loaded and re-sorted from scratch on every user interaction.

for (int i = 0; i < n; i++) { [array insertObject:items[i] atIndex:0]; } for (int i = 0; i < n; i++) { [array addObject:items[i]]; } // then reverse once if front-order is required

Repeatedly inserting at index 0 makes every one of the n insertions do O(n) shifting work, for O(n²) total — a loop that is fast for a handful of items becomes painfully slow once the array holds thousands. Appending and reversing once (or appending in already-correct order) does the same job in O(n) total.

@property (nonatomic, strong) NSArray *items; // items = callerSuppliedMutableArray;

@property (nonatomic, copy) NSArray *items;

A strong array property stores whatever pointer it is given. If the caller passed an NSMutableArray — which is a valid NSArray — they retain the ability to mutate it after storing it, silently changing your object's state from outside. A copy property snapshots an independent, genuinely immutable array at assignment time.

[array removeObjectAtIndex:array.count]; // one past the end if (index < array.count) { [array removeObjectAtIndex:index]; } removeObjectAtIndex: (like insertObject:atIndex: beyond count, and objectAtIndex:) raises NSRangeException and crashes the program for any index that is not strictly less than the array's current count. Always validate the index against the array's live count immediately before the call, especially in code that runs after other mutations may have changed that count.

What is the time complexity of insertObject:atIndex:0 on an NSMutableArray with n elements? A. O(1) B. O(log n) C. O(n) D. O(n^2)

C. O(n) — Inserting at the front requires shifting every one of the array's n existing elements one slot to the right to make room, which is O(n) work proportional to the array's current length.

Which method removes an object by value, doing nothing if that value is not present in the array? A. removeObjectAtIndex: B. removeObject: C. replaceObjectAtIndex:withObject: D. removeAllObjects

B. removeObject: — removeObject: searches for an equal object and removes the first match if one exists; if no element matches, it simply does nothing rather than raising an exception. removeObjectAtIndex: instead operates by position and crashes on an invalid index.

Why should a property that stores an array typically be declared copy rather than strong? A. copy properties use less memory than strong properties B. Because a caller could pass an NSMutableArray, which is a valid NSArray, and keep mutating it after you store it unless you snapshot an independent copy C. strong properties are not allowed to hold NSArray values D. copy is required by the Objective-C compiler for any collection type

B. Because a caller could pass an NSMutableArray, which is a valid NSArray, and keep mutating it after you store it unless you snapshot an independent copy — NSMutableArray is a subclass of NSArray, so a strong-typed NSArray property can legally hold a mutable array. Without copy, the caller retains a reference to that same mutable object and can change it later, silently altering your stored value.

Which of the following best describes the complexity trade-off NSMutableArray makes compared to a linked-list-style structure? A. NSMutableArray is slower than a linked list for every operation B. NSMutableArray optimizes for O(1) indexed access and end-appending, at the cost of O(n) insertion/removal at the front or middle; a linked list inverts that trade-off C. NSMutableArray and a linked list have identical complexity for all operations D. NSMutableArray has O(1) front insertion but O(n) indexed access

B. NSMutableArray optimizes for O(1) indexed access and end-appending, at the cost of O(n) insertion/removal at the front or middle; a linked list inverts that trade-off — NSMutableArray's contiguous storage gives fast indexed reads and cheap end-appending, but front/middle mutation requires shifting elements — O(n). A linked-list-style structure can insert/remove at a known node in O(1) but must walk from the front for indexed access, the opposite trade-off.

What does sortUsingComparator: do differently from NSArray's sortedArrayUsingComparator:? A. sortUsingComparator: only works on strings B. sortUsingComparator: mutates the receiver in place and returns void, rather than returning a new sorted array C. They are identical in every respect D. sortUsingComparator: is only available on iOS, not macOS

B. sortUsingComparator: mutates the receiver in place and returns void, rather than returning a new sorted array — sortUsingComparator: (and sortUsingSelector:) are NSMutableArray-only methods that reorder the receiver's own elements in place and return nothing, whereas NSArray's sortedArrayUsingComparator: leaves the receiver untouched and returns a brand-new sorted array.

Write a method -(void)removeDuplicatesFromMutableArray:(NSMutableArray *)array that removes duplicate objects from a mutable array in place, keeping only the first occurrence of each value, without crashing and without mutating the array while iterating over it directly.

• (void)removeDuplicatesFromMutableArray:(NSMutableArray *)array { NSMutableSet *seen = [NSMutableSet set]; NSMutableIndexSet *toRemove = [NSMutableIndexSet indexSet]; [array enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { if ([seen containsObject:obj]) { [toRemove addIndex:idx]; } else { [seen addObject:obj]; } }]; [array removeObjectsAtIndexes:toRemove]; }

Enumerating an array with a fast-enumeration for-in loop while also calling a mutation method on that same array from inside the loop is unsafe. Build a separate NSMutableSet (or NSMutableArray) of values already seen, and a separate list of indices or objects to remove, then perform the removals after the enumeration finishes — the same 'collect first, mutate after' pattern used to avoid the NSMutableDictionary enumeration crash later in this module.