리스트 목차
리스트 List
특성
순서대로 저장하는 시퀀스이자 변경 가능(Mutable List)한 목록
입력 순서가 유지
내부적으로는 동적 배열로 구현됨
- 파이썬뿐만 아니라 현대 언어들은 언어별로 대부분 동적 배열을 지원
- C++나 자바: 동적 배열은 가장 자주 쓰는 자료형 중 하나.
- 파이썬에서도 가장 자주 쓰는 자료형으로서, 특히 코딩 테스트 시 매우 빈번하게 활용됨.
[각 언어 별 동적 배열 구현]
| 언어 | 동적배열 |
|---|---|
| 파이썬 | list |
| C++ | std::vector |
| 자바 | ArrayList |
[장점] 리스트를 사용하면 스택을 사용할지, 큐를 사용할지(9장)를 고민 필요 없음
(이유)스택과 큐에서 사용 가능한 모든 연산을 함께 제공.
실행 가능한 연산
| 연산 | 시간 | 설명 |
|---|---|---|
| len(a) | O(1) | 전체 요소의 개수 리턴 |
| a[i] | O(1) | 인덱스 i의 요소를 가져옴 |
| a[i:j] | O(k) | 1) i부터 j까지 슬라이스의 길이만큼인 k개의 요소를 가져옴 |
| 2) 객체 k개에 대한 조회가 필요하므로 O(k) | ||
| elem in a | O(n) | 1) elem 요소가 존재하는지 확인 |
| 2) 처음부터 순차 탐색하므로 n만큼 시간이 소요 | ||
| a.count(elem) | O(n) | elem 요소의 개수를 리턴 |
| a.index(elem) | O(n) | elem 요소의 인덱스를 리턴 |
| a.append(elem) | O(1) | 리스트 마지막에 elem 요소를 추가 |
| a.pop() | O(1) | 1) 리스트 마지막 요소를 추출 |
| 2) 스택의 연산 | ||
| a.pop(0) | O(n) | 1) 리스트 첫번째 요소를 추출 |
| 2) 큐의 연산 | ||
| 3) 전체 복사가 필요하므로 O(n) | ||
| 4) 큐의 연산을 이용한다면 리스트보다는 O(1)에 가능한 데크(deque)를 권장(나중에 설명) | ||
| del a[i] | O(n) | 1) i에 따라 다름 |
| 2) 최악의 경우 O(n) | ||
| a.sort() | O(n log n) | 1) 정렬 |
| 2) 팀소트(Timsort)를 사용 (6장 링크) | ||
| 3) 최선의 경우 O(n)에도 실행될수 있음 | ||
| min(a), max(a) | O(n) | 최솟값/최댓값을 계산하기 위해서는 전체를 선형 탐색 |
| a.reverse() | O(n) | 1) 뒤집음 |
| 2) 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 됨 |
- 리스트의 경우 탐색 시 값의 존재 유무를 확인하려면, 정렬된 경우에는 이진 검색이 효율적(18장)
리스트의 활용 방법
리스트 선언 방법
>>> a = list()
대괄호( [] )로 좀 더 간단하게 선언 가능
>>> a = []
초깃값을 지정해 선언
>>> a = [1, 2, 3]
>>> a
[1, 2, 3]
삽입
append()
>>> a = [1, 2, 3]
>>> a
[1, 2, 3]
>>> a.append(4)
>>> a
[1, 2, 3, 4]
insert()
: 특정 위치의 인덱스를 지정해 요소를 추가 가능.
# 3번째 인덱스에(인덱스는 0부터 시작한다) 5를 삽입한다.
>>> a.insert(3, 5)
>>> a
[1, 2, 3, 5, 4]
문자와 불리언 삽입
리스트는 숫자 외에도 다양한 자료형을 단일 리스트에 관리 가능
-> 매우 편리.
다른 언어
- 동적 배열에 삽입할 수 있는 자료형을 __동일한 타입으로 제한__하는 경우가 많은 데 비해, 파이썬은 이처럼 자유롭게 삽입
>>> a.append('안녕')
>>> a.append(True)
>>> a
[1, 2, 3, 5, 4, '안녕', True]
추출
인덱스 지정하면 추출 가능
>>> a[3]
5
슬라이싱 slicing, 예외처리
특정 범위 내의 값을 매우 편리하게 가져올 수 있음.
원래 슬라이싱은 문자열에 유용하게 활용되는 기능으로서, 리스트에도 동일한 형태로 매우 유용하게 활용 가능.
다른 언어들
- 인덱스의 반복문을 구성하고 순회하면서 값을 출력해야 함,
파이썬의 슬라이싱은 이처럼 시작 인덱스와 종료 인덱스를 설정해 간단히 해당하는 값 출력 가능
리스트이름[첫번째 인덱스: 끝 인덱스: step(생략가능 default = 1)]
>>> a[1:3]
[2, 3]
시작 인덱스는 다음과 같이 생략 가능
: 이 경우 처음부터 값을 가져옴
>>> a[:3]
[1, 2, 3]
- 종료 인덱스를 생략 가능
- 마지막까지 값을 가져온다
>>> a[4:]
[4, '안녕', True]
홀수 번째 인덱스의 값만 가져올 수도 있음
# 인덱스 1, 2, 3의 값
>>> a[1:4]
[2, 3, 5]
# 인덱스 1, 3의 값
>>> a[1:4:2]
[2, 5]
- 존재하지 않는 인덱스를 조회할 경우
- 다음과 같이 IndexError 가 발생 ```python
a[9] Traceback (most recent call last): File “
", line 1, in IndexError: list index out of range
IndexError 는 인덱스가 리스트의 길이를 넘어설 때 발생하며
**try 구문으로 에러에 대한 예외 처리 가능.**
```python
try:
print(a[9])
except IndexError:
print('존재하지 않는 인덱스')
요소 삭제 2가지 방법
1) 인덱스로 삭제하기 2) 값으로 삭제하기
인덱스로 삭제
[del 키워드]
인덱스의 위치에 있는 요소를 삭제할 수 있다.
>>> a
[1, 2, 3, 5, 4, '안녕', True]
>>> del a[1]
>>> a
[1, 3, 5, 4, '안녕', True]
값으로 삭제
[remove() 함수]
값에 해당하는 요소를 삭제할 수 있다.
>>> a
[1, 3, 5, 4, '안녕', True]
>>> a.remove(3)
>>> a
[1, 5, 4, '안녕', True]
[pop() 함수]
스택의 팝 pop 연산처럼 추출로 처리.
즉 삭제될 값을 리턴 후 삭제
>>> a
[1, 5, 4, '안녕', True]
>>> a.pop(3)
'안녕'
>>> a
[1, 5, 4, True]
리스트의 특징
장점
연속된 공간에 요소를 배치하는 배열의 장점
+ 다양한 타입을 연결해 배치하는 연결 리스트의 장점
= 배열과 연결 리스트가 모두 필요 없을 정도로 강력 -> 때문에 파이썬은 아예 원시 타입 자료형은 제공하지도 않음.
다음은 CPython에서 리스트를 정의한 헤더 파일의 일부.
// cpython/Include/cpython/listobject.h
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
CPython에서 리스트는 요소에 대한 포인터 목록( ob_item )을 갖고 있는 구조체 Struct 로 선언되어 있음.
리스트에 요소를 추가하거나 조작하기 시작하면 ob_item 의 사이즈를 조절해 나가는 형태로 구현되어 있음.
리스트는 이처럼 객체로 되어 있는 모든 자료형을 다음과 같이 포인터로 연결
파이썬은 모든 것이 객체 파이썬의 리스트
- 그림 5-2처럼 이들 객체에 대한 포인터 목록을 관리하는 형태로 구현.
- 사실상 연결 리스트에 대한 포인터 목록을 배열 형태로 관리,
-> 그 덕분에 파이썬의 리스트는 배열과 연결 리스트를 합친 듯이 강력한 기능을 자랑.
다음은 정수로 이뤄진 값들을 파이썬 리스트에 삽입하는 코드다.
>>> a = [1, 2, 3]
>>> a
[1, 2, 3]
일반적으로 정수형 배열이라고 하면, 이처럼 정수로만 이뤄진 값을 연속된 메모리 공간에 저장하는 경우를 말하며, 정수가 아닌 값은 저장할 수 없다. 그러나 파이썬의 리스트는 연결 리스트에 대한 포인터 목록을 관리하고 있기 때문에 앞서 ‘리스트의 활용 방법’(링크삽입) 절에서 살펴본 것처럼 다음과 같이 정수, 문자, 불리언 등 제각기 다양한 타입을 동시에 단일 리스트에서 관리하는 게 가능.
>>> a = [1, '안녕', True]
>>> a
[1, '안녕', True]
단점
- 각 자료형의 크기는 저마다 서로 다름
-> 이들을 연속된 메모리 공간에 할당 불가능 - 결국 각각의 객체에 대한 참조로 구현할 수밖에 없음.
-
- 인덱스를 조회 시
- 모든 포인터의 위치를 찾아가서 타입 코드를 확인하고 값을 일일이 살펴봐야 하는 등 추가적인 작업이 필요
-> 속도 면에서도 훨씬 더 불리