파이썬 자료구조

1. 리스트(list)

• 인덱스 접근 []: O(1)
• append(): O(1)
• pop() (맨 끝 요소 제거): O(1)
• pop(i) (임의 위치 i에서 제거): O(n)
• insert(i, x): O(n)
• del del list[i]:
  • 마지막 요소 제거: O(1)
  • 임의 위치에서 제거: O(n)
• remove(x): O(n) (값을 찾기 위한 선형 탐색 필요)
• index(x): O(n)
• sort(): O(nlog⁡n)
• reverse(): O(n)
• len(): O(1)
• 슬라이싱 list[start:end]: O(k) (슬라이싱되는 길이에 비례)

2. 딕셔너리(dict)

• 인덱스 접근 d[key]: O(1)
• 삽입 및 업데이트 d[key] = value: O(1)
• 삭제 del d[key]: O(1)
• get(key): O(1)
• pop(key): O(1)
• keys(): O(n) (모든 키를 반환)
• values(): O(n) (모든 값을 반환)
• items(): O(n) (키-값 쌍을 반환)
• len(): O(1)

3. 세트(set)

• 삽입 s.add(x): O(1)
• 삭제 s.remove(x): O(1)
• 탐색 x in s: O(1)
• 교집합 s1 & s2: O(min(len(s1),len(s2)))
• 합집합 s1 | s2: O(len(s1)+len(s2))
• 차집합 s1 - s2: O(len(s1))
• 대칭차집합 s1 ^ s2: O(len(s1)+len(s2))

4. 튜플(tuple)

• 인덱스 접근 t[i]: O(1)
• count(x): O(n)
• index(x): O(n)
• len(): O(1)

튜플은 불변(immutable) 자료구조로, 리스트와 유사하지만 요소를 변경할 수 없다는 점에서 리스트와 다르다.

5. deque (collections.deque)

• append() (끝에 요소 추가): O(1)
• appendleft() (앞에 요소 추가): O(1)
• pop() (끝에서 요소 제거): O(1)
• popleft() (앞에서 요소 제거): O(1)
• extend(iterable): O(k)(길이에 비례)
• extendleft(iterable): O(k)
• rotate(n): O(n) (n번 회전)
• len(): O(1)