[python] list pop VS pop first

5. 자료 구조 — Python 3.10.2 문서

강의를 듣다가 잊고 있던 부분 다시 한 번 상기.

강의에서는 pop(0) 보다 pop()이 더 효율적이기 때문에, 리스트를 역순으로 정렬한 뒤 사용하는 풀이를 보여줬다.

 

 리스트를 큐로 사용하는 것도 가능한데, 처음으로 넣은 요소가 처음으로 꺼내지는 요소입니다 (《first-in, first-out》);
 하지만, 리스트는 이 목적에는 효율적이지 않습니다. 리스트의 끝에 덧붙이거나, 끝에서 꺼내는 것은 빠르지만, 리스트의 머리에 덧붙이거나 머리에서 꺼내는 것은 느립니다 (다른 요소들을 모두 한 칸씩 이동시켜야 하기 때문입니다).
 큐를 구현하려면, 양 끝에서의 덧붙이기와 꺼내기가 모두 빠르도록 설계된 collections.deque 를 사용하세요.

다른 블로그를 참고해보니, pop()은 O(1)의 시간이 걸리는 반면, pop(0)은 O(n)의 시간이 걸린다고. 왜? 위에서도 설명했듯 다른 요소들을 모두 한 칸씩 이동시켜야 하기 때문에.

 

그래서 양 끝에서의 덧붙이기와 꺼내기가 모두 빠르도록 설계된 collections.deque를 사용하길 권장하고 있다. 

deque를 사용하게 되면, list와 달리 popleft()도 O(1)의 시간이 걸린다고 한다. 

 

 

Reference

• 5.1.2. 리스트를 큐로 사용하기
• python deque 사용하는 이유 / popleft