[Python] collections.deque

맨날 무엇이든지 대충대충 하는 습관이 들어서 그걸 고치기 위해 영어문서를 해석해보고 정리해본다.

 

문제풀이 할 때 가끔씩(?) 쓰는 collections 모듈이다.

Source code는 https://github.com/python/cpython/blob/3.8/Lib/collections/__init__.py

python/cpython

에서 확인할 수 있다.

여러 Object들이 존재하지만, 아직 사용해본 2개만 정리해보겠다. (나머지는 나중에 쓰는 날이 오면 그때 마다 정리하는 걸로..)

 

** 먼저 deque이다.

  (앞에 C++ STL 정리글에서 정리한 deque와 같다.)

 

* 선언

 

* Method들 정리 (n은 deque요소의 갯수, k는 extend의 경우 extend하는 요소들의 갯수)

append(x)       O(1)	deque의 맨 오른쪽에 x원소를 추가한다.
appendleft(x)       O(1)	deque의 맨 왼쪽에 x원소를 추가한다.
clear()    O(n)	deque의 모든 원소를 삭제한다.
copy()        O(n)	deque의 *shallow copy를 만든다.
count(x)       O(n)	deque의 원소 중 x의 개수를 return해준다. (없을 시 0 return)
extend(iterable)      O(k)	deque의 오른쪽에  iterable한 인자들을 추가한다.
extendleft(iterable)     O(k)	deque의 왼쪽에 iterable한 인자들을 추가한다.
index(x[,start[,stop]])	deque 안에 있는 x의 인덱스를 return해준다. []는 없어도 되고, 있으면 start에서 stop사이의 범위에서만 체크한다. (x가 없을 시 ValueError가 발생함)
insert(i, x)      O(n)	x를 i번째 인덱스에 삽입한다. (deque의 범위를 넘어서 i가 접근할 경우 IndexError 발생함)
pop(), popleft()    O(1)	맨 오른쪽원소(왼쪽원소)를 제거하고 return해준다 (원소가 없을 시 IndexError 발생함)
remove(value)    O(n)	value와 일치하는 요소를 제거한다. 일치하는 요소가 여러 개일 경우 0번째 인덱스부터 시작해서 가장 처음의 요소를 지운다. (value에 해당하는 요소가 없을 시 ValueError 발생함)
reverse()   O(n)	deque의 요소들을 뒤집는다.
rotate(k)   O(k)	deque의 요소들을 k번씩 오른쪽으로 이동시킨다. 맨 오른쪽에 있는 원소는 오른쪽으로 이동하면  맨 왼쪽으로 온다. (k에 -1을 넣으면 왼쪽으로 한 칸씩 rotate된다)

 

* Shallow Copy와 Deep copy의 차이점

https://blog.naver.com/ekdldhrtlsda/221764190608

python - Shallow Copy , Deep Copy