Why Python's list does not have shift/unshift methods?

Question

I am wondering why the default list in Python does not have any shift, unshift methods. Maybe there is an obvious reason for it like the way the lists are ordered in memory.

So currently, I know that I can use append to add an item at the end of a list and pop to remove an element from the end. However, I can only use list concatenation to imitate the behavior of a missing shift or unshift method.

>>> a = [1,2,3,4,5] >>> a = [0] + a  # Unshift / Push >>> a [0,1,2,3,4,5] >>> a = a[1:]  # Shift / UnPush >>> a [1,2,3,4,5] 

Did I miss something?

Answer 1

Python lists were optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation. Actually, the "list" datatype in CPython works differently as to what many other languages might call a list (e.g. a linked-list) - it is implemented more similarly to what other languages might call an array, though there are some differences here too.

You may be interested instead in collections.deque, which is a list-like container with fast appends and pops on either end.

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

The missing methods you appear to be asking about are provided under the names appendleft and popleft:

appendleft(x)

Add x to the left side of the deque.

popleft()

Remove and return an element from the left side of the deque. If no elements are present, raises an IndexError.

Of course there is a trade-off, and indexing or inserting/removing near the middle of the deque is slow. In fact deque.insert(index, object) wasn't even possible before Python 3.5, you would need to rotate, insert/pop, and rotate back. You also lose slicing, so if you needed that you'll have to write something annoying with e.g. itertools.islice instead.

For further discussion of the advantages and disadvantages of deque vs list data structures, see How are deques in Python implemented, and when are they worse than lists?