순서대로 저장되며 변경 가능한 목록. 내부적으로는 동적 배열로 구현되어있다
동적배역이란..?
크기를 지정하지 않는 배열로, 할당된 공간이 다 채워지면 크기가 동적으로 증가하는 배열을 말한다
파이썬의 리스트는 매우 다양한 기능을 제공해서 스택을 사용할지, 큐를 사용할지 고민할 필요가 없다. ⇒ 스택과 큐의 기능을 모두 제공한다.
리스트의 주요 연산과 시간복잡도
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| len(a) | O(1) | 전체 요소의 개수 return |
| a[i] | O(1) | 인덱스 i의 요소를 가져옴 |
| a[i:j] | O(k) | i-j까지의 슬라이스 길이만큼 k개의 요소를 가져온다. |
| elem in a | O(n) | elem의 요소가 a에 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼의 시간 소요 |
| 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) | 리스트의 첫번째 요소 추출. 큐의 연산. 이 경우는 전체 복사가 필요하므로 시간복잡도가 **O(n)**이다. 따라서 큐의 연산을 주로 사용한다면 리스트보다는 O(1)이 가능한 deque(데크)를 권장 |
| del a[i] | O(n) | i에 따라 다름. 최악의 경우가 O(n)이다. |
| a.sort() | O( n log n ) | 정렬. 팀소트(Timsort)를 사용하며, 최선의 경우 O(n)가능 |
| min(a), max(a) | O(n) | 최솟값/최댓값을 계산하기 위해서는 전체를 선형 탐색해야 한다. |
| a.reverse() | O(n) | 뒤집는다. 리스트는 순서가 유지되므로 뒤집게 되면 입력 순서는 반대로 된다. |
#리스트 선언
a = list()
a = []
#insert
a = [1,2,3,4]
a.insert(3,5)
>>[1,2,3,5,4]
#append
a.append('안녕')
>>[1,2,3,5,4,'안녕']
위의 예시에서 알 수 있듯이
insert()를 통해 특정 위치의 인덱스를 지정해 요소를 추가 가능
파이썬의 리스트는 동적 배열에 다양한 자료형 가능