https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

List

                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Index         | l[i]         | O(1)         |
Store         | l[i] = 0     | O(1)         |
Length        | len(l)       | O(1)         |
Append        | l.append(5)  | O(1)         | mostly: ICS-46 covers details
Pop          | l.pop()      | O(1)         | same as l.pop(-1), popping at end
Clear         | l.clear()    | O(1)         | similar to l = []

Slice         | l[a:b]       | O(b-a)         | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)
Extend        | l.extend(...)| O(len(...))   | depends only on len of extension
Construction  | list(...)    | O(len(...))   | depends on length of ... iterable

check ==, !=  | l1 == l2     | O(N)          |
Insert        | l[a:b] = ... | O(N)         | 
Delete        | del l[i]     | O(N)         | depends on i; O(N) in worst case
Containment   | x in/not in l| O(N)         | linearly searches list 
Copy          | l.copy()     | O(N)         | Same as l[:] which is O(N)
Remove        | l.remove(...)| O(N)         | 
Pop          | l.pop(i)     | O(N)         | O(N-i): l.pop(0):O(N) (see above)
Extreme value | min(l)/max(l)| O(N)         | linearly searches list for value
Reverse          | l.reverse()  | O(N)         |
Iteration     | for v in l:  | O(N)          | Worst: no return/break in loop

Sort          | l.sort()     | O(N Log N)    | key/reverse mostly doesn't change
Multiply      | k*l          | O(k N)        | 5*l is O(N): len(l)*l is O(N**2)

Deque (like a doubly Linked List in Java) https://docs.python.org/2/library/collections.html

# Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.

append(x)
appendleft(x)
count(x)
extend(l)
extendleft(l)
pop()
popLeft()
remove(x)
reverse()
rotate(step)