Array.removeFirst() is O(n)

Hi there,

Recently I'm preparing interviews so I'm practising Swift.

While for some code challenge, it requires to use Stack or Queue.

I notice Swift Array.removeFirst() is declared as O(n) because it adopts RangeReplaceableCollection.

But I'm kind of confused and curious, is it really O(n) or O(1) if we just remove the first element. Besides, removeFirst(k) is also O(n), while Collection protocol says it's just O(1) if RandomAccessCollection is adopted.

So it's kind of tricky to understand, because Array adopts all of above protocols, but the performance for same API seems becoming worse..?

Also, will Swift also provides Stack and Queue if removeFirst is required to be O(1)?

1 Like

It's really O(n). Array.removeFirst will remove the first element from the Array and then compact the Array: it will copy all the other elements down one place. Array.removeFirst(k) is also O(n) for the same reason.

The Collection documents are missing an important note about removeFirst() and removeFirst(k), which you can see if you actually try to use them on a brand new collection. Here, we can do it ourselves:

struct X: Collection {
    var startIndex: Int {
        return 0
    }

    var endIndex: Int {
        return 10
    }

    subscript(index: Int) -> String {
        return String(index)
    }

    func index(after i: Int) -> Int {
        return i + 1
    }
}

var x = X()
x.removeFirst()

The last line (x.removeFirst()) prints an error when you try to compile it:

Referencing instance method 'removeFirst()' on 'Collection' requires the types 'X' and 'Slice<X>' be equivalent

This constraint is not visible in the documentation, but it's the only time a Collection can implement these things. Thus, their proposed complexity constraints only apply in this case. Array and its slice type are not the same, and so the Collection implementation of removeFirst does not apply here. Instead, the one that applies is RangeReplaceableCollection.removeFirst(), which is documented to be O(n).

The cheapest way to make removeFirst be O(1) is to use ArraySlice instead of Array. On that type, removeFirst actually is O(1), as ArraySlice does not promise to compact the storage. Unfortunately, this type can potentially cause you some nasty memory usage patterns depending on how you use it.

Note that Array is a great stack: stacks are LIFO, meaning that the stack operations on Array genuinely are O(1), as they are append and removeLast. Array is simply not a good queue. The Swift standard library has no good queue type today. There are some in the OSS ecosystem (e.g. SwiftNIO's CircularBuffer).

4 Likes

Thanks! @lukasa Yeah I was working some binary tree practice, and using Stack is super nasty for some puzzles, and have to use removeFirst instead.

Please allow me to ask a silly question, that if removeLast is O(1), what's the underlying data struct behind Array? e.g. for LinkedList removeFirst or insertFirst is O(1) operation. I was wondering how Array is implemented behind the scenes

Array is a flat buffer of memory. In Java this would be roughly equivalent to ArrayList.

1 Like
Terms of Service

Privacy Policy

Cookie Policy