Cost of list functions in Python

Question

Based on this older thread, it looks like the cost of list functions in Python is:

• Random access: O(1)
• Insertion/deletion to front: O(n)
• Insertion/deletion to back: O(1)

Can anyone confirm whether this is still true in Python 2.6/3.x?

Answer 1

That's correct, inserting in front forces a move of all the elements to make place.

collections.deque offers similar functionality, but is optimized for insertion on both sides.

Answer 2

Take a look here. It's a PEP for a different kind of list. The version specified is 2.6/3.0.

Append (insertion to back) is O(1), while insertion (everywhere else) is O(n). So yes, it looks like this is still true.

Operation...Complexity
Copy........O(n) 
Append......O(1)
Insert......O(n) 
Get Item....O(1)
Set Item....O(1)
Del Item....O(n) 
Iteration...O(n)
Get Slice...O(k)
Del Slice...O(n)
Set Slice...O(n+k)
Extend......O(k) 
Sort........O(n log n)
Multiply....O(nk)

Answer 3

Python 3 is mostly an evolutionary change, no big changes in the datastructures and their complexities.

The canonical source for Python collections is TimeComplexity on the Wiki.

Answer 4

Fwiw, there is a faster (for some ops... insert is O(log n)) list implementation called BList if you need it. BList