1. deque 란?
- deque(덱)는 파이썬의 collections 모듈에서 제공하는 자료 구조 중 하나로, "double-ended queue"의 약자입니다. deque는 큐(queue)와 스택(stack)의 특성을 모두 가지고 있으며, 양쪽 끝에서 데이터를 효율적으로 추가하고 제거할 수 있는 자료 구조입니다. 이것은 리스트(list)보다 데이터를 추가하거나 제거할 때 빠르고 효율적이며, 특히 큰 데이터 집합에 유용합니다.
deque를 사용하기 위해서는 collections 모듈을 임포트해야 합니다:
from collections import deque
2. 주요 특징과 사용법
- 다음은 deque의 주요 특징과 사용법에 대한 설명입니다.
2-1. 데이터 추가 및 제거
- deque는 양쪽 끝에서 데이터를 추가하고 제거할 수 있습니다. 다음과 같은 메서드를 사용할 수 있습니다.
- append(x): 오른쪽 끝에 원소 x를 추가합니다.
- appendleft(x): 왼쪽 끝에 원소 x를 추가합니다.
- pop(): 오른쪽 끝에서 원소를 제거하고 반환합니다.
- popleft(): 왼쪽 끝에서 원소를 제거하고 반환합니다.
2-2. 길이 확인
- len(deque)를 사용하여 deque의 길이를 확인할 수 있습니다.
2-3. 인덱싱 및 슬라이싱
- deque도 리스트처럼 인덱싱과 슬라이싱을 지원합니다.
2-4. 회전
- rotate(n) 메서드를 사용하여 deque를 오른쪽으로 n번 회전할 수 있습니다. 음수 n을 지정하면 왼쪽으로 회전합니다.
2-5. 최대 길이 제한
- maxlen 매개변수를 사용하여 deque의 최대 길이를 제한할 수 있습니다. 이를 설정하면 deque의 길이가 최대 길이를 초과하면 오래된 요소가 자동으로 제거됩니다.
아래는 간단한 예제 코드입니다
from collections import deque
# 빈 deque 생성
my_deque = deque()
# 오른쪽 끝에 데이터 추가
my_deque.append(1)
my_deque.append(2)
# 왼쪽 끝에 데이터 추가
my_deque.appendleft(0)
# deque 출력
print(my_deque) # 출력: deque([0, 1, 2])
# 오른쪽 끝에서 데이터 제거
my_deque.pop()
# 왼쪽 끝에서 데이터 제거
my_deque.popleft()
# deque 출력
print(my_deque) # 출력: deque([1])
3. deque와 list의 성능 차이
- 아래에서는 두 자료 구조 간의 주요 성능 차이를 설명합니다.
3-1. 데이터 추가 및 제거 성능
- list: 리스트는 동적 배열(dynamic array)로 구현되어 있어 데이터를 추가하거나 제거할 때, 특히 리스트의 끝에 원소를 추가하거나 제거하는 경우, 평균적으로는 상수 시간(O(1))에 수행됩니다. 그러나 리스트의 앞 부분에 원소를 추가하거나 제거하는 경우, 해당 인덱스 이후의 모든 원소를 이동해야 하므로 시간 복잡도는 O(n)이 될 수 있습니다. 이는 큰 리스트에서 앞부분에 데이터를 추가 또는 제거할 때 성능 저하를 초래할 수 있습니다.
- deque: deque는 이중 연결 리스트(doubly linked list)로 구현되어 있으며, 양쪽 끝에서 데이터를 추가하거나 제거할 때 상수 시간(평균적으로 O(1))에 수행됩니다. 따라서 deque는 큐(queue) 및 스택(stack)과 같은 시나리오에서 데이터를 앞뒤로 추가하거나 제거해야 하는 경우에 더 효율적입니다.
3-2. 인덱싱 및 슬라이싱 성능
- list: 리스트는 동적 배열로 구현되어 있으므로 인덱싱과 슬라이싱이 O(1)의 시간 복잡도를 가집니다. 이는 리스트의 장점 중 하나입니다.
- deque: deque도 인덱싱 및 슬라이싱을 지원하지만, 리스트처럼 빠른 접근이 아닙니다. 인덱스를 기반으로 원소에 접근할 때는 리스트보다 약간의 오버헤드가 발생할 수 있습니다. 그러나 이러한 차이는 일반적으로 큰 데이터 집합에서 미미합니다.
3-3. 회전 성능
- list: 리스트는 슬라이싱을 사용하여 회전을 수행할 수 있지만, 이렇게 하면 새로운 리스트를 생성하는 데 O(n) 시간이 소요됩니다.
- deque: deque에서는 rotate(n) 메서드를 사용하여 회전을 수행하며, 회전 연산은 해당하는 요소 수에 비례하는 시간(O(k))이 걸립니다. 이는 deque의 회전 연산이 리스트보다 효율적이며, 큐를 구현하는 데 유용합니다.
4. 결론
- 따라서 데이터 추가 및 제거 연산이 주로 필요한 경우에는 deque가 list보다 성능이 우수합니다. 그러나 인덱싱 및 슬라이싱이 주요 요구사항이라면 list가 더 적합할 수 있습니다. 사용 사례에 따라 두 자료 구조를 적절히 선택하여 최적의 성능을 얻을 수 있습니다.