The amortized cost of prepend (unshift in ruby) is O(1) (since Ruby 2). Of course that means at some point you'll get O(n) prepend.

[1] https://stackoverflow.com/questions/8353026/what-is-the-run-...