[python] What's the idiomatic syntax for prepending to a short python list?

list.append() is the obvious choice for adding to the end of a list. Here's a reasonable explanation for the missing list.prepend(). Assuming my list is short and performance concerns are negligible, is

list.insert(0, x)

or

list[0:0] = [x]

idiomatic?

What's the idiomatic syntax for prepending to a short python list?

You don't usually want to repetitively prepend to a list in Python.

If it's short, and you're not doing it a lot... then ok.

list.insert

The list.insert can be used this way.

list.insert(0, x)

But this is inefficient, because in Python, a list is an array of pointers, and Python must now take every pointer in the list and move it down by one to insert the pointer to your object in the first slot, so this is really only efficient for rather short lists, as you ask.

Here's a snippet from the CPython source where this is implemented - and as you can see, we start at the end of the array and move everything down by one for every insertion:

for (i = n; --i >= where; )
    items[i+1] = items[i];

If you want a container/list that's efficient at prepending elements, you want a linked list. Python has a doubly linked list, which can insert at the beginning and end quickly - it's called a deque.

deque.appendleft

A collections.deque has many of the methods of a list. list.sort is an exception, making deque definitively not entirely Liskov substitutable for list.

>>> set(dir(list)) - set(dir(deque))
{'sort'}

The deque also has an appendleft method (as well as popleft). The deque is a double-ended queue and a doubly-linked list - no matter the length, it always takes the same amount of time to preprend something. In big O notation, O(1) versus the O(n) time for lists. Here's the usage:

>>> import collections
>>> d = collections.deque('1234')
>>> d
deque(['1', '2', '3', '4'])
>>> d.appendleft('0')
>>> d
deque(['0', '1', '2', '3', '4'])

deque.extendleft

Also relevant is the deque's extendleft method, which iteratively prepends:

>>> from collections import deque
>>> d2 = deque('def')
>>> d2.extendleft('cba')
>>> d2
deque(['a', 'b', 'c', 'd', 'e', 'f'])

Note that each element will be prepended one at a time, thus effectively reversing their order.

Performance of list versus deque

First we setup with some iterative prepending:

import timeit
from collections import deque

def list_insert_0():
    l = []
    for i in range(20):
        l.insert(0, i)

def list_slice_insert():
    l = []
    for i in range(20):
        l[:0] = [i]      # semantically same as list.insert(0, i)

def list_add():
    l = []
    for i in range(20):
        l = [i] + l      # caveat: new list each time

def deque_appendleft():
    d = deque()
    for i in range(20):
        d.appendleft(i)  # semantically same as list.insert(0, i)

def deque_extendleft():
    d = deque()
    d.extendleft(range(20)) # semantically same as deque_appendleft above

and performance:

>>> min(timeit.repeat(list_insert_0))
2.8267281929729506
>>> min(timeit.repeat(list_slice_insert))
2.5210217320127413
>>> min(timeit.repeat(list_add))
2.0641671380144544
>>> min(timeit.repeat(deque_appendleft))
1.5863927800091915
>>> min(timeit.repeat(deque_extendleft))
0.5352169770048931

The deque is much faster. As the lists get longer, I would expect a deque to perform even better. If you can use deque's extendleft you'll probably get the best performance that way.

Lets go over 4 methods

1. Using insert()

>>> 
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l.insert(0, 5)
>>> l
[5, 0, 1, 2, 3, 4]
>>> 

2. Using [] and +

>>> 
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l = [5] + l
>>> l
[5, 0, 1, 2, 3, 4]
>>> 

3. Using Slicing

>>> 
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l[:0] = [5]
>>> l
[5, 0, 1, 2, 3, 4]
>>> 

4. Using collections.deque.appendleft()

>>> 
>>> from collections import deque
>>> 
>>> l = list(range(5))
>>> l
[0, 1, 2, 3, 4]
>>> l = deque(l)
>>> l.appendleft(5)
>>> l = list(l)
>>> l
[5, 0, 1, 2, 3, 4]
>>> 

If someone finds this question like me, here are my performance tests of proposed methods:

Python 2.7.8

In [1]: %timeit ([1]*1000000).insert(0, 0)
100 loops, best of 3: 4.62 ms per loop

In [2]: %timeit ([1]*1000000)[0:0] = [0]
100 loops, best of 3: 4.55 ms per loop

In [3]: %timeit [0] + [1]*1000000
100 loops, best of 3: 8.04 ms per loop

As you can see, insert and slice assignment are as almost twice as fast than explicit adding and are very close in results. As Raymond Hettinger noted insert is more common option and I, personally prefer this way to prepend to list.

In my opinion, the most elegant and idiomatic way of prepending an element or list to another list, in Python, is using the expansion operator * (also called unpacking operator),

# Initial list
l = [4, 5, 6]

# Modification
l = [1, 2, 3, *l]

Where the resulting list after the modification is [1, 2, 3, 4, 5, 6]

I also like simply combining two lists with the operator +, as shown,

# Prepends [1, 2, 3] to l
l = [1, 2, 3] + l

# Prepends element 42 to l
l = [42] + l

I don't like the other common approach, l.insert(0, value), as it requires a magic number. Moreover, insert() only allows prepending a single element, however the approach above has the same syntax for prepending a single element or multiple elements.

If you can go the functional way, the following is pretty clear

new_list = [x] + your_list

Of course you haven't inserted x into your_list, rather you have created a new list with x preprended to it.