Only if you eagerly shift all elements on every operation. If you allocate extra space, and only shift every N operations (N being the max size of the list), it

Only if you eagerly shift all elements on every operation. If you allocate extra space, and only shift every N operations (N being the max size of the list), it’s O(n/n), eg O(1) amortized. As mentioned already, you can represent it as a circular buffer to save a bit of memory. But this cost analysis also means that a simple array can be much faster than a linked list for almost all operations in theory (excludes random insert given an insert token, which is not an index). I believe there’s also experimental evidence of this showing that an array is almost always preferable to a linked list - even in the cases were a linked list is often taught as the obvious choice (such as a queue). Yep, surprised me quite a bit too.