Complexity Analysis of General Data Structures for Common Operations:

Linked list 

Indexing 
Θ(n) 
Θ(1) 
Θ(1) 
Θ(log n) 
Θ(log n) 
Insert/delete at beginning 
Θ(1) 
N/A 
Θ(n) 
Θ(log n) 
Θ(1) 
Insert/delete at end 
Θ(1) 
N/A 
Θ(1) amortized 
Θ(log n) 
Θ(log n) updating 
Insert/delete in middle 
search time + 
N/A 
Θ(n) 
Θ(log n) 
Θ(log n) updating 
Wasted space (average) 
Θ(n) 
0 
Θ(n)^{[2]} 
Θ(n) 
Θ(n) 
Complexity Analysis of Python’s Data Structures for Common Operations:
list
Internally, a list is represented as an array
Operation 
Average Case 

Copy 
O(n) 
O(n) 
Append[1] 
O(1) 
O(1) 
Insert 
O(n) 
O(n) 
Get Item 
O(1) 
O(1) 
Set Item 
O(1) 
O(1) 
Delete Item 
O(n) 
O(n) 
Iteration 
O(n) 
O(n) 
Get Slice 
O(k) 
O(k) 
Del Slice 
O(n) 
O(n) 
Set Slice 
O(k+n) 
O(k+n) 
Extend[1] 
O(k) 
O(k) 
O(n log n) 
O(n log n) 

Multiply 
O(nk) 
O(nk) 
x in s 
O(n) 

min(s), max(s) 
O(n) 

Get Length 
O(1) 
O(1) 
collections.deque
A deque (doubleended queue) is represented internally as a doubly linked list
Operation 
Average Case 
Amortized Worst Case 
Copy 
O(n) 
O(n) 
append 
O(1) 
O(1) 
appendleft 
O(1) 
O(1) 
pop 
O(1) 
O(1) 
popleft 
O(1) 
O(1) 
extend 
O(k) 
O(k) 
extendleft 
O(k) 
O(k) 
rotate 
O(k) 
O(k) 
remove 
O(n) 
O(n) 
dict
Operation 
Average Case 
Amortized Worst Case 
Copy[2] 
O(n) 
O(n) 
Get Item 
O(1) 
O(n) 
Set Item[1] 
O(1) 
O(n) 
Delete Item 
O(1) 
O(n) 
Iteration[2] 
O(n) 
O(n) 
Reference:
http://wiki.python.org/moin/TimeComplexity
http://en.wikipedia.org/wiki/Linked_list