리스트(list) 완전 해부 — 동적 배열과 시간 복잡도

🎯 이 강의에서 배우는 것

파이썬 리스트는 단순한 자료구조가 아닙니다. 내부적으로 동적 배열(dynamic array)로 구현되어 있습니다. 각 연산의 시간 복잡도를 알아야 성능 문제를 진단할 수 있습니다. O(1) 연산과 O(n) 연산의 차이가 백만 개 데이터에서 수백만 배 속도 차이를 만듭니다.

🏗️ 동적 배열의 내부 구조

import sys
import ctypes

# 파이썬 리스트의 내부 구조:
# - 연속된 메모리 블록에 "포인터(객체 주소)" 저장
# - 각 포인터는 8바이트(64비트 시스템)
# - 실제 객체는 힙 메모리 어딘가에 별도 저장

lst = [1, "hello", 3.14, True]  # 타입 혼합 가능 — 포인터만 저장하기 때문!

# 리스트 크기 (구조 자체의 크기 — 요소 크기 아님)
print(sys.getsizeof([]))         # 56 bytes (빈 리스트)
print(sys.getsizeof([1]))        # 64 bytes (+8 bytes per pointer)
print(sys.getsizeof([1, 2, 3]))  # 80 bytes

# 동적 배열: 용량(capacity)과 크기(size)가 다름
# 크기가 꽉 차면 더 큰 배열을 할당하고 포인터를 복사
# 과할당(over-allocation) 전략: 재할당 비용 분산

def show_capacity():
    lst = []
    old_size = sys.getsizeof(lst)
    print(f"len=0, bytes={old_size}")
    for i in range(20):
        lst.append(i)
        new_size = sys.getsizeof(lst)
        if new_size != old_size:
            print(f"len={len(lst)}, bytes={new_size} ← 재할당!")
            old_size = new_size
        else:
            print(f"len={len(lst)}, bytes={new_size}")

show_capacity()
# 용량이 0→4→8→16→25... 순으로 증가하는 것을 확인

⏱️ 시간 복잡도 — 연산별 완전 분석

import timeit

# ✅ O(1) 연산 — 상수 시간
lst = list(range(1000))

# 인덱싱: 포인터 배열의 인덱스 i에 직접 접근 → O(1)
print(lst[0])          # 첫 번째
print(lst[-1])         # 마지막
print(lst[500])        # 중간

# append: 대부분 O(1), 재할당 시 O(n) — 분할 상환 O(1)
lst.append(1000)

# pop(): 마지막 요소 제거 → O(1)
last = lst.pop()       # 이동 없음

# len(): O(1) — 별도 카운터 저장
print(len(lst))

# ❌ O(n) 연산 — 선형 시간
big_list = list(range(100_000))

# insert(0, x): 맨 앞에 삽입 — 모든 요소를 한 칸씩 이동
t = timeit.timeit(lambda: big_list.insert(0, -1), number=1)
print(f"insert(0): {t:.6f}초")

# pop(0): 맨 앞 제거 — 모든 요소를 앞으로 이동
t = timeit.timeit(lambda: big_list.pop(0), number=1)
print(f"pop(0): {t:.6f}초")

# in 연산자: 순차 탐색 → O(n)
t = timeit.timeit(lambda: 99999 in big_list, number=100)
print(f"in 연산: {t:.6f}초")

# 딕셔너리/셋의 in은 O(1) — 해시 테이블
big_set = set(big_list)
t = timeit.timeit(lambda: 99999 in big_set, number=100)
print(f"set in 연산: {t:.6f}초")  # 훨씬 빠름!

✂️ 슬라이싱 완전 이해

lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 기본: lst[start:stop:step]  — stop은 미포함
print(lst[2:5])     # [2, 3, 4]
print(lst[:3])      # [0, 1, 2]  (처음부터)
print(lst[7:])      # [7, 8, 9]  (끝까지)
print(lst[:])       # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (전체 복사)

# 음수 인덱스
print(lst[-3:])     # [7, 8, 9]  (뒤에서 3개)
print(lst[:-3])     # [0, 1, 2, 3, 4, 5, 6]  (뒤에서 3개 제외)

# step: 간격
print(lst[::2])     # [0, 2, 4, 6, 8]  (2 간격)
print(lst[1::2])    # [1, 3, 5, 7, 9]  (홀수 인덱스)
print(lst[::-1])    # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] (역순!)
print(lst[8:1:-2])  # [8, 6, 4, 2]  (8부터 2까지 -2 간격)

# 슬라이싱 할당 — 크기가 달라도 됨
a = [1, 2, 3, 4, 5]
a[1:3] = [20, 30, 40]   # 2개를 3개로 교체
print(a)   # [1, 20, 30, 40, 4, 5]

a[2:4] = []   # 요소 삭제
print(a)   # [1, 20, 5]

# 슬라이싱은 새 리스트 생성 — 복사
original = [1, 2, 3]
copy = original[:]   # 얕은 복사
copy[0] = 99
print(original)   # [1, 2, 3] — 변경 없음
print(copy)       # [99, 2, 3]

📚 리스트 메서드 완전 정리

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# 추가
lst.append(10)          # 끝에 추가, O(1)
lst.extend([11, 12])    # 이터러블 요소들을 끝에 추가, O(k)
lst.insert(0, 99)       # 인덱스 0에 삽입, O(n)

# 제거
lst.remove(99)          # 첫 번째 99 삭제, O(n). 없으면 ValueError
popped = lst.pop()      # 마지막 요소 꺼내기, O(1)
popped_i = lst.pop(0)   # 인덱스 0 요소 꺼내기, O(n)
del lst[0:2]            # 슬라이스 삭제, O(n)
lst.clear()             # 전체 삭제

# 검색
lst = [3, 1, 4, 1, 5]
idx = lst.index(1)      # 첫 번째 1의 인덱스. 없으면 ValueError
cnt = lst.count(1)      # 1이 등장하는 횟수
is_in = 4 in lst        # O(n) 선형 탐색

# 정렬/뒤집기
lst.sort()              # 오름차순 정렬 (in-place), 반환 None
lst.sort(reverse=True)  # 내림차순
lst.sort(key=abs)       # key 함수 지정
lst.reverse()           # 순서 뒤집기 (in-place), 반환 None
print(lst[::-1])        # 뒤집은 새 리스트 (원본 유지)

# 복사
shallow = lst.copy()    # 얕은 복사 (lst[:] 와 동일)

📊 Timsort — 파이썬 정렬 알고리즘

import timeit

# Timsort: Tim Peters가 2002년 개발
# - 실제 데이터의 패턴(이미 정렬된 구간)을 활용
# - 최선 O(n): 이미 정렬된 경우
# - 평균/최악 O(n log n): 일반적인 경우
# - 안정 정렬(stable): 동일한 키 값의 순서 보존
# - 공간 O(n)

import random

# 이미 정렬된 데이터는 훨씬 빠름
sorted_data = list(range(100_000))
random_data = sorted_data.copy()
random.shuffle(random_data)

t_sorted = timeit.timeit(lambda: sorted(sorted_data), number=10)
t_random  = timeit.timeit(lambda: sorted(random_data), number=10)
print(f"정렬된 데이터: {t_sorted:.3f}초")
print(f"무작위 데이터: {t_random:.3f}초")
# 이미 정렬된 데이터가 훨씬 빠름

# 안정 정렬 확인
data = [(1, 'b'), (2, 'a'), (1, 'a'), (2, 'b')]
data.sort(key=lambda x: x[0])
print(data)   # [(1, 'b'), (1, 'a'), (2, 'a'), (2, 'b')]
# 같은 숫자 안에서 원래 순서(b가 a보다 먼저였음) 유지됨

⚠️ 자주 하는 실수

• 루프 안에서 insert(0, x) 반복: 맨 앞에 반복 삽입하면 O(n²)로 느려집니다. append() 후 reverse()하거나, collections.deque를 사용하세요.
• 리스트 안에서 특정 요소 자주 검색: x in lst는 O(n)입니다. 자주 검색한다면 셋(set)이나 딕셔너리로 변환하여 O(1) 조회를 하세요.
• list.sort() 반환값 사용: result = lst.sort()는 None입니다. 원본을 정렬하고 싶으면 lst.sort(), 새 리스트가 필요하면 sorted(lst)를 사용하세요.

📝 정리 및 다음 강의 예고

• 리스트는 포인터 배열 — 타입 혼합이 가능하고, 인덱싱·append·pop이 O(1)입니다.
• insert(i)·pop(i)·remove()는 O(n) — 요소 이동이 필요합니다. 맨 앞 삽입/삭제가 잦으면 deque를 사용하세요.
• 슬라이싱은 새 리스트 생성 — 복사에 사용합니다. step=-1로 역순.
• Timsort: 안정 정렬, O(n log n). 이미 정렬된 데이터에서 O(n).

다음 강의: 리스트 심화 — 얕은 복사와 깊은 복사의 차이, 중첩 리스트 함정, 메모리 효율적인 리스트 사용법을 배웁니다.