랜덤 접근이 가능한 deque 자료구조를 chunk로 구현하면 어떤 이점이 있을까요?
deque를 공식 레퍼런스 사이트에서 보면, Chunk로도 구현이 된다고 되어 있습니다. 그러면, Chunk로 구현했을 때, 장점이 무엇일까요? 일단, deque가 Random 접근이 되려면, 기본적으로 연속적이여야 합니다. List는 Random access를 지원하지 않습니다. 더 정확히 이야기 하면, base 주소가 있고, 그것을 통해서 i번째 index에 접근할 수 있어야 합니다. 1차 구조의 덱을 생각해 보겠습니다. 원래 4개의 원소가 있었고, 5를 어딘가에 추가한다고 해 보겠습니다. 원래 capacity가 4였다면, 하나를 추가하려는 순간 추가하지 못하게 될 겁니다. 그러므로 확장 연산이 수행이 될 겁니다. 그러면 확장된 후에 기존의 원소가 어떻게 들어가는 것이 좋을까요? 이렇게 들어가는 것이..
자료알고/자료구조
2020. 4. 7. 01:08
최근댓글