리스트, 배열과 연결 리스트를 통합하고 속도는 양보한 파이썬의 객체 타입

파이썬의 리스트는 말 그대로 순서대로 저장하는 시퀀스이자 변경 가능한 목록을 말한다.

입력 순서가 유지되며, 내부적으로는 동적 배열로 구현되어 있다.

 

각 언어 별 동적 배열을 구현한 자료형은 아래와 같다.

언어	동적 배열
파이썬	list()
c++	std::vector
자바	ArrayList

 

리스트의 주요 연산과 시간 복잡도

리스트는 다양한 기능을 제공하면서도 O(1)에 실행 가능한 연산들도 있다.

연산	시간 복잡도	설명
len(a)	O(1)	전체 요소의 개수를 리턴한다.
a[i]	O(1)	인덱스의 i 번째 요소를 가져온다.
a[i:j]	O(k)	인덱스 i 번째부터 j-1 번째 까지의 슬라이스 길이만큼의 k개의 요소를 가져온다. 이 경우 객체 k에 대한 조회가 필요하므로 O(k)이다.
elem in a	O(n)	elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n 만큼의 시간이 소요된다.
a.count(elem)	O(n)	elem 요소의 개수를 리턴한다.
a.index(elem)	O(n)	elem 요소의 인덱스를 리턴한다.
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)	뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다.

 

리스트의 경우 탐색 시 값의 존재 유무를 확인하려면, 정렬된 경우에는 이진 탐색이 효율적이다.

매번 정렬이 필요하고, 대개는 리스트가 정렬된 상태가 아니므로 모든 엘리먼트를 순차적으로 조회하는 형태로 구현되어 있어 최악의 경우 항상 O(n)이 소요된다.

 

 

---

리스트의 특징

파이썬의 리스트는 연속된 공간에 요소를 배치하는 배열의 장점과 다양한 타입을 연결해 배치하는 연결 리스트의 장점을 모두 취한 듯한 형태를 띈다.

리스트를 잘 사용하기만 해도 배열과 연결 리스트가 모두 필요가 없을 정도로 강력하다.

하지만 리스트는 다양한 자료형을 통합해서 저장할 수 있기 때문에, 실제로 연속된 메모리 공간에 할당할 수 없고 각각의 객체에 대한 참조로 구현할 수 밖에 없다. 모든 포인터의 위치를 찾아가서 타입 코드를 확인하고 값을 일일히 살펴봐야 하므로 속도 측면에서 불리한 객체 타입임이 분명하다.