리스트
리스트
- 순서대로 저장하는 sequence
- 변경 가능
- 입력 순서가 유지
- 내부적으로 동적 배열로 구현되어 있음(7장에서 자세히)
장점
다양한 기능을 제공, O(1)에서 실행 가능한 연산도 존재
리스트의 주요 연산 시간 복잡도
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| len(a) | O(1) | 전체 요소 개수 |
| a[i] | O(1) | index가 i인 요소 |
| a[i:j] | O(k) | 슬라이싱에서 k개에 대한 조회가 필요 |
| elem in a | O(n) | elem이라는 요소가 a안에 있는지 확인 |
| a.count(elem) | O(n) | elem 요소의 개수 |
| a.index(elem) | O(n) | elem요소의 index |
| a.append(elem) | O(1) | elem요소를 리스트 마지막에 추가 |
| a.pop() | O(1) | 리스트 마지막 요소를 추출 |
| a.pop(0) | O(n) | 리스트 첫번재 요소 추출(큐의 연산) |
| del a[i] | O(n) | index가 i인 요소 제거 ( 최악의 경우가 O(n) ) |
| a.sort() | O(n log n ) | 정렬. Timsort(6장)를 사용. 최선의 경우 O(n)에도 실행될 수 있음 |
| min(a), max(a) | O(n) | 최솟값/최댓값 |
| a.reverse() | O(n) | 뒤집기 |
리스트의 경우 탐색 시 값의 존재 유무를 확인하려면
정렬된 경우, 이진 검색이 효율적.
그러나 대개 리스트가 정렬된 상태가 아니기 때문에, 리스트의 경우 순차적으로 조회하는 형태로 구현되어 있음 ⇒ 최악의 경우 O(n)이 소요
리스트 활용 방법
- a.insert(index, 값) ⇒ 해당 index 위치의 요소에 ‘값’을 삽입한다.
- 숫자 외에도 다양한 자료형을 추가 가능 (문자, 불리언 등)
- a[index] ⇒ 해당 index 위치의 요소를 꺼내온다.
- a[i:j] ⇒ 슬라이싱 제공, i번째 index의 요소부터 j-1번째 요소까지 값을 리스트로 출력
- a[i:j:k] ⇒ 슬라이싱 시, i번째 부터 시작해 k번씩 건너뛰면서 j까지 의 값
- 존재하지 않는 index 조회 시 IndexError 발생
⇒ Try 구문으로 에러에 대한 예외 처리 가능
try:
print(a[9])
except IndexError:
print("존재하지 않는 인덱스")- 리스트에서 요소를 삭제하는 방법은 크게 2가지
- 인덱스로 삭제하기
⇒ del a[i] 또는 a.pop(i) : i번째 index에 해당하는 요소 삭제
>>> a
[1,5,4,'안녕']
>>> a.pop(3)
[1,5,4] pop() 함수의 경우 삭제될 값을 먼저 리턴하고, 삭제가 진행됨
- 값으로 삭제하기
⇒ a.remove(값) : 값에 해당하는 요소를 삭제
리스트의 특징
파이썬의 리스트는 실제로는 각 원소의 객체에 대한 포인터 목록을 저장한다.
참조를 할 때, 포인터가 가리키는 메모리 공간 내 값(실제 원소)을 확인하여 사용하는 것이다.
파이썬은 모든 것이 객체이기에, 리스트 내에 다양한 타입을 단일 리스트 안에서 관리하는 게 가능.
하지만, 각 자료형의 크기는 저마다 서로 다르기 떄문에
이들을 연속된 메모리 공간에 할당하는 것은 불가능
결국, 각각의 객체에 대한 참조로 구현해야 한다.
당연히 인덱스를 조회하는 데에도 모든 포인터의 위치를 찾아가서
타입 코드를 확인하고 값을 일일이 살펴봐야 하는 추가적인 작업이 필요 ⇒ 속도 저하
하지만 강력한 기능을 위해 속도를 희생
'파이썬 알고리즘' 카테고리의 다른 글
| 딕셔너리 (0) | 2023.04.18 |
|---|---|
| 자료형, 자료구조, 추상 자료형 (0) | 2023.04.18 |
| 빅 오 표기법 (0) | 2023.04.18 |
| 파이썬 문법 기본 (0) | 2023.04.18 |