https://wikidocs.net/1015
list
| Operation | Example | Big-O | Notes |
|---|
| Index | l.index(v) | O(N) | |
| Length | len(l) | O(1) | |
| Append | l.append(5) | O(1) | |
| Pop | l.pop() | O(1) | l.pop(-1) 과 동일 |
| Clear | l.clear() | O(1) | l = [] 과 유사 |
| Slice | l[a:b] | O(b-a) | l[:] : O(len(l)-0) = O(N) |
| Extend | l.extend(...) | O(len(...)) | 확장 길이에 따라 |
| Construction | list(...) | O(len(...)) | 요소 길이에 따라 |
| ==, != | l1 == l2 | O(N) | 순서도 같아야 동일 |
| Insert | l.insert(i, v) | O(N) | |
| Delete | del l[i] | O(N) | |
| Remove | l.remove(…) | O(N) | |
| Containment | x {not} in l | O(N) | 검색 |
| Copy | l.copy() | O(N) | l[:] 과 동일 - O(N) |
| Pop | l.pop(i) | O(N) | pop(): O(1) |
| Extreme value | min(l)/max(l) | O(N) | 검색 |
| Reverse | l.reverse() | O(N) | |
| Iteration | for v in l: | O(N) | |
| Sort | l.sort(key=, reverse=) | O(N Log N) | sorted(l)도 비슷 |
| Multiply | l * k | O(k N) | [1,2,3] * 3 » O(N**2) |
dict
| Operation | Example | Big-O | Notes |
|---|
| Index | d[k] | O(1) | |
| Store | d[k] = v | O(1) | |
| Length | len(d) | O(1) | |
| Delete | del d[k] | O(1) | |
| setdefault | d.setdefault(k, [insertVifNotExist]) | O(1) | get/set한 값 반환, default: None |
| Pop | d.pop(k) | O(1) | |
| Pop item | d.popitem() | O(1) | |
| Clear | d.clear() | O(1) | d = {} or = dict() 유사 |
| View | d.keys() | O(1) | d.values() 동일 |
| Construction | dict(…) | O(len(…)) | |
| Iteration | for k in d: | O(N) | |
# c++ map처럼 사용
tot += d.setdefault(k, 0)
deque
from collections import deque
# 생성
d = deque(list)
# append, appendleft
d.append(6)
d.appendleft('hi')
# pop, popleft
x = d.pop()
x = d.popleft() # O(1), x = l.pop(0) # O(N)
# rotate
d = rotate(2) # 양수: 시계, 음수: 반시계
>>> [4, 5, 1, 2, 3]
