- 내부 구현: C언어 배열 기반으로, 용량이 부족하면 1.5~2배 크기로 자동 재할당된다
- 인덱스 접근: \(O(1)\), 끝 추가/삭제: \(O(1)\) (분할 상환)
- 중간 삽입/삭제: \(O(N)\) — 뒤 원소를 밀거나 당겨야 하기 때문이다 ::: 각 메서드의 시간 복잡도를 이해하면 불필요한 성능 저하를 방지할 수 있다.
- 파이썬의 리스트는 동적 배열로, 배열과 스택의 기능을 동시에 제공한다.
- 대부분의 알고리즘 구현에서 기본 자료구조로 사용된다.
- 각 메서드의 시간 복잡도를 이해하면 불필요한 성능 저하를 방지할 수 있다.
- append와 pop은 \(O(1)\) 이지만 insert와 remove는 \(O(N)\) 이므로 용도를 구별해야 한다.
\(O(1)\) 그룹 (1~6번): 배열의 동적 특성 — 끝에서만 작업하면 매우 빠르다. 사실상 스택(Stack)으로 활용 가능하다.
\(O(N)\) 그룹 (9~16번): 배열의 한계 — 중간을 건드리면 뒤의 원소를 전부 이동해야 한다. 앞에서 꺼내는 큐(Queue) 용도로 쓰면 성능 저하가 발생하므로
collections.deque를 사용해야 한다.1~6: 파이썬의 list는 동적 배열의 특징이 있다. 시간 복잡도는 모두 \(O(1)\) 이다.
- 3~4: 사실상 stack의 기능과 동일
- 7~11
- 12~16
- 17~21
- 스택 대용:
append()와pop()만 사용하면 완전한 LIFO 스택으로 동작한다. - BFS/DFS: 방문 노드 순서를 저장하는 컨테이너로 활용한다.
- 행렬 표현: 2차원 리스트로 행렬(matrix) 연산을 구현한다.
- 슬라이딩 윈도우: 슬라이싱(
arr[i:j])으로 구간을 추출한다. - 배치 데이터 처리: 데이터 파이프라인에서 미니배치를 리스트로 구성한다.
1 개요
파이썬 리스트(List)는 동적 배열로, 배열과 스택의 기능을 동시에 제공한다.
::: {.callout-note} ## 정의: Python list
Python의 list는 동적 배열(Dynamic Array)로, 배열의 빠른 인덱스 접근과 연결 리스트의 유연한 크기 조절을 결합한 자료구조다.
2 왜 필요한가
3 파이썬 리스트 메서드 시간 복잡도
|——–|——————|—————–|———————–|—————————————————————-| | 1 | Indexing | \(O(1)\) | arr[i] | 특정 i th 인덱스의 값 반환 | | 2 | Storing | \(O(1)\) | arr[i] = 1 | 특정 i th 인덱스에 값 (=1) 할당 | | 3 | Append | \(O(1)\) | arr.append(5) | 리스트의 가장 뒤에 데이터 추가 | | 4 | Pop | \(O(1)\) | arr.pop() | 리스트의 가장 뒤에서 원소 꺼내기 | | 5 | Length | \(O(1)\) | len(arr) | 리스트의 길이 얻기 | | 6 | Clear | \(O(1)\) | arr.clear() | 리스트 내 모든 원소 제거하기 | | 7 | Slicing | \(O(b-a)\) | arr[a:b] | 리스트에서 인덱스 a부터 b-1까지의 원소만 꺼내 새 리스트 만들기 | | 8 | Extend | \(O(len(other))\) | arr.extend(list2) | 기존 리스트, list1에 다른 리스트, list2를 이어 붙이기 | | 9 | Insertion | \(O(N)\) | arr.insert(index, x)| 특정 인덱스에 데이터 x를 삽입하기, 즉 i th index를 뒤로 밀고 추가 | | 10 | Delete | \(O(N)\) | del arr[index] | 특정 인덱스의 데이터 삭제하기 | | 11 | Construction | \(O(len(other))\) | arr = list(other) | 다른 자료구조의 원소들을 이용해 리스트로 만들기 | | 12 | In | \(O(N)\) | x in arr | 데이터 x가 리스트에 존재하는지 확인 | | 13 | Not in | \(O(N)\) | x not in arr | 데이터 x가 리스트에 존재하지 않는지 확인 | | 14 | Pop | \(O(N)\) | arr.pop(index) | 특정 인덱스의 데이터를 꺼내기 / 단, 가장 뒤 원소를 꺼내는 경우 O(1) | | 15 | Remove | \(O(N)\) | arr.remove(x) | 리스트 내에 존재하는 데이터 x를 삭제 | | 16 | Copy | \(O(N)\) | arr.copy() | 리스트를 복제 | | 17 | Min | \(O(N)\) | min(arr) | 리스트 내에 존재하는 가장 작은 원소 | | 18 | Max | \(O(N)\) | max(arr) | 리스트 내에 존재하는 가장 큰 원소 | | 19 | Iteration | \(O(N)\) | for x in arr | 리스트 내에 존재하는 모든 원소 순회 | | 20 | Multiply | \(O(k*N)\) | arr * k | 리스트를 k번 반복하여 길게 만들기 | | 21 | Sort | \(O(NlogN)\) | arr.sort() | 리스트 내 존재하는 원소를 정렬 | : a list of the list functions in Python {#tbl-letters}
See ?@tbl-letters.
위 표에서 주목할 점은 연산을 크게 두 그룹으로 나눌 수 있다는 것이다.
#| code-fold: true
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(arr[4]) # 인덱싱(indexing)
# 저장(storing)
arr[7] = 10
# 뒤에 붙이기(append)
arr.append(10)
print(arr)
# 뒤에서 꺼내기(pop)
arr.pop()
print(arr)
# 길이(length)
print(len(arr))
# 배열 비우기(clear)
arr.clear()
print(arr)
# 출력:
# 4
# [0, 1, 2, 3, 4, 5, 6, 10, 8, 9, 10]
# [0, 1, 2, 3, 4, 5, 6, 10, 8, 9]
# 10
# []#| code-fold: true
arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
new_arr = arr[2:7] # 슬라이싱(slicing)
print(new_arr)
arr1 = [0, 1, 2, 3, 4]
arr2 = [5, 6, 7, 8, 9]
arr1.extend(arr2) # 확장(extend)
print(arr1)
arr = [0, 1, 2, 3, 4]
arr.insert(3, 7) # 삽입(insertion)
print(arr)
del arr[3] # 삭제(delete)
print(arr)
data = {7, 8, 9}
arr = list(data) # 다른 자료구조로 리스트 만들기
print(arr)
# 출력:
# [2, 3, 4, 5, 6]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# [0, 1, 2, 7, 3, 4]
# [0, 1, 2, 3, 4]
# [8, 9, 7] (set 변환으로 순서 비결정, 환경에 따라 다를 수 있음)#| code-fold: true
arr = [0, 1, 2, 3, 4]
print(3 in arr) # 존재 여부(in)
print(7 not in arr) # 비존재 여부(not in)
arr.pop(1) # 인덱스 1에 해당하는 원소 꺼내기(pop)
print(arr)
arr.remove(3) # 리스트의 특정 원소 삭제(remove)
print(arr)
new_arr = arr.copy() # 복제(copy)
print(new_arr)
# 출력:
# True
# True
# [0, 2, 3, 4]
# [0, 2, 4]
# [0, 2, 4]#| code-fold: true
arr = [3, 5, 4, 1, 2]
print(min(arr)) # 최소(min)
print(max(arr)) # 최대(max)
for x in arr: # 원소 순회(iteration)
print(x, end=" ")
print()
print(arr * 2) # 리스트 반복하여 곱하기(multiply)
arr.sort() # 정렬(sorting)
print(arr)
# 출력:
# 1
# 5
# 3 5 4 1 2
# [3, 5, 4, 1, 2, 3, 5, 4, 1, 2]
# [1, 2, 3, 4, 5]