👉 [Python] Deque vs List

collections 모듈은 Python에서 제공하는 내장 모듈 중 하나이다.

 이 모듈은 여러 유용한 자료 구조를 구현하는데 사용되는데, 그 중 하나가 `deque`(Double-Ended Queue)

deque는 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐(Queue)와 스택(Stack)의 역할을 동시에 맡는다!

이 자료 구조는 데이터를 양쪽 끝에서 추가하거나 제거할 때 매우 효율적인데, O(1) 의 시간복잡도를 갖는다.

list는데이터를 삽입하거나 삭제할 때 맨 끝을 기준으로 작업을 수행하기 때문에, 리스트의 길이가 길어질수록 작업 속도가 느려진다. 시간복잡도가 O(N) 에 수렴한다.

 

반면, deque 는 데이터를 양쪽 끝에서 추가하거나 제거할 수 있으므로, 길이가 길어져도 빠른 속도로 작업을 수행할 수 있다.

왜냐하면 내부적으로 deque은 double-linked list로 구현되었기에 좌-우에서 삽입/삭제에 매우 유연하다.

 

 

from collections import deque

my_deque = deque()

또는 리스트를 `deque`로 변환할 수도 있다.

 

from collections import deque

my_list = [1, 2, 3]
my_deque = deque(my_list)

데이터를 왼쪽 끝에 추가하는 메서드는 `appendleft()`이고, 오른쪽 끝에 추가하는 메서드는 `append()`

데이터를 왼쪽 끝에서 제거하는 메서드는 `popleft()`이고, 오른쪽 끝에서 제거하는 메서드는 `pop()`.

다음은 `deque`의 몇 가지 예시이다.

from collections import deque

my_deque = deque()

my_deque.append(1)
my_deque.appendleft(2)
my_deque.append(3)
print(my_deque)  # 출력: deque([2, 1, 3])

my_deque.popleft()
my_deque.pop()
print(my_deque)  # 출력: deque([1])

 

 

물론 deque가 무조건적으로 훌륭하진 않다. 시간복잡도를 O(1)로 갖지만 리스트처럼 인덱스를 이용한 임의 접근이나 슬라이싱이 불가능하다. 

 

또한, deque는 내부적으로 이중 연결 리스트로 구현되어 있어, 각 원소가 다음 원소와 이전 원소의 포인터를 가지고 있기 때문에 리스트보다 더 많은 메모리를 사용하니까, 알잘딱깔센하게 사용해야 한다.