java ArrayDeque : 원형큐에 expand를 얹었다.

 java의 arrayDeque가 어떻게 구현되었는지 간단히 알아보겠습니다. 세세하게 뜯지는 않을 거고, 중요한 변수들과 메서드만 보도록 하겠습니다.

 

 

---

 먼저, 이 메서드를 보도록 하겠습니다.

 

 

 코드를 봐도 뭔 말인지 모르겠습니다. 이럴 때는 쪼개시면 됩니다.

 

 

 먼저, if문을 만족하지 않는다면, MIN_INITIAL_CAPACITY개의 원소를 저장할 수 있는 배열이 생성됩니다. 이 값은 디폴트로 8입니다. 만약에, numElements가 8보다 크거나 같으면 어떻게 될까요?

 

 

 그러면 이런 알 수 없는 코드들이 수행되는데요. 어렵지 않아요. 132번째 부터 136번째 줄까지는 bit or 연산을 하고 있어요. 우항을 보면, >>> 연산자가 있는데요. 이는 쉽게 말해서 우측으로 이동한다 정도로 생각하심 됩니다. initialCapacity가 2진수로 100000 이렇게 표현이 될 때, 어떻게 돌아가나 봅시다.

 

 

 초기 상태는 위와 같습니다. init의 2진수는 100000입니다. 여기서 init>>>1을 하면 10000입니다.

 

 

 이 둘을 bit or 하면 어떻게 되나요? 110000이 됩니다.

 

 

 다음에 110000이 init이 되는데요. init>>>2의 값은 1100입니다. 이 둘을 bit or 하면 111100이 됩니다.

 

 

 다음에 111100이 init이라면, init>>>4는 11일 겁니다. 위에 있는 두 수를 bit or 하면 아래와 같습니다.

 

 

 111111이 나옵니다. 여기에 1을 더하면 1000000이 되는데요. 이것은 initCapacity보다 큰 2의 제곱수를 의미합니다. 이 메서드에서 사용된 1, 2, 4, 8, 16, 32 트릭은 LCA, 최소 공통 조상 알고리즘에서 많이 이용되니, 알아두셔도 좋겠습니다. 아이디어도 나름 참신합니다.

 

 어찌 되었던, 내부에 있는 배열의 capacity는 처음에 2의 제곱수임을 알 수 있습니다.

 

 

---

 그러면 이것이 어디에 쓰일까요? 원소를 push하고 pop을 할 때 쓰입니다. 그 중에, 우리가 관심을 가질만한 것은 addFirst, addLast일 건데요. addFirst를 보겠습니다.

 

 

 229번째 줄을 보면, head에, (head - 1) & (elements.length - 1)을 넣는데 elements.length가 2의 제곱수였으니, 거기에 1을 뺀다면 11..1 꼴이 될 겁니다. mask 역할을 하게 됩니다. 순서를 보면, head가 먼저 바뀌고, head의 위치에 e를 집어 넣습니다.

 

 

 그런데, addLast에서는 tail이 가리키는 곳에 e를 넣고, tail을 증가시킵니다. 일단, 공통적으로 head나 tail이 변할 때 bit and를 이용하는 것을 알 수 있는데요. 이 값은 2^k - 1꼴의 자연수임을 알 수 있습니다. 연산의 순서로 미루어 보았을 때, head와 tail은 다음과 같이 도식화를 시킬 수 있음을 알 수 있습니다. 맨 앞이 2번째, 맨 뒤가 4번째일 때, 이 둘의 값은 아래와 같습니다.

 

 

 head는 진짜 원소의 시작 위치이고, tail은 원소의 끝 1칸 뒤에 있는 셈입니다. 처음에는 head와 tail이 같았습니다. 이 때가 빈 상태였습니다. 즉, head와 tail이 같다면 empty 상태입니다. 문제는 뒤나 앞에 계속 추가가 되다가, head와 tail이 같아지는 경우일 텐데요.

 

 

 이런 경우에, 빈 상태하고 구분이 되지 않습니다. head와 tail이 같은 상태이기 때문입니다. size를 추가로 두면 가능하긴 하겠다만. 어찌 되었던, add 과정에서 원소가 하나 추가되었다면 빈 상태는 아니므로, 이 때에는 FULL 상태가 됩니다. 그렇다면 확장을 해야 하는데요. 2의 제곱수 단위로 capacity가 들어가야 하므로, 공간이 2^i배로 뻥튀기가 되어야 합니다.

 

---

 그 과정을 보도록 합시다.

 

 

 뭔가 어려워 보이는데요. 제일 알아먹기 쉬운 것은 newCapacity가 n의 2배였다는 것입니다. 즉, grow rate는 2임을 알 수 있습니다. 다음에, n이 length고 p가 head입니다. n에서 p를 뺀 값이 r인데요. n 값은 8이였습니다.

 

 

 p가 2이고, n이 8이므로, r이 6임을 알 수 있습니다. 이 r값은, arraycopy에서 쓰는데요.

 

 

 length만큼, 원본 배열의 srcPos부터 srcPos+len-1까지의 내용을, 복사 배열인 dest의 destPos부터 destPos+len-1까지 복사합니다. arrayCopy 하는 부분만 따로 보겠습니다.

 

 

 158번째 줄을 해석하면, 원본이 elements였고, 복사 배열이 a인데, 원본은 p부터 p+r-1까지의 내용을, 복사본의 0부터 r-1에 복사합니다. r이 6이고, p가 2였으므로, 원본의 2부터 7까지의 내용을 복사본의 0부터 5까지에 복사해 버립니다.

 

 

 그러면 요래 될 겁니다. 다음에 원본 배열의 0번째부터 p개를, 복사본의 r번째부터 p개만큼 복사하라 하는데. r 값은 6이였고, p 값이 2였습니다. 원본의 0번째 부터 2개면 파란색 부분을 의미합니다. 이것을 복사본의 6번째 부터 복사하는데, 파란 부분이 6번째 위치부터 복사가 된다면 어떻게 될까요?

 

 

 아래와 같이 됩니다. 이렇게 두 부분으로 나누어서 잘 복사하고 난 다음에, head를 0으로 tail을 n값인 8로 셋팅해 주면 됩니다. 여기까지 이해하셨다면, 완전히 다 이해하신 겁니다. pollFirst와 pollLast는 그리 어렵지 않기 때문입니다.

 

 

 First 위치를 뽑고 제거를 하려면, 어떻게 해야 할까요? 가리키고 있는 곳을 꺼내온 다음에, null 처리를 합니다. 그 다음에 head를 증가시켜 줍니다. 이는 head가 원소의 1번째 위치를 가리키기 때문입니다.

 

 

 반면 pollLast는 tail을 먼저 이동시키고, 해당 위치에 있는 원소를 제거합니다. 이는 tail이 제일 끝에 있는 원소 다음에 위치해 있기 때문입니다. ArrayDeque를 한 줄로 요약하면, 원형 큐에 expand를 살포시 얹은 구조입니다.이렇게 구현해서 큐로 썼을 때, LinkedList로 구현했을 때 보다 빠른지는 테스트를 해 보시면 될 듯 합니다.