java collections reverse : list를 뒤집는 연산을 간단하게 알아봅시다.

 안녕하세요. 이번 시간에는 Collections의 reverse 메소드에 대해 알아보도록 하겠습니다. 사실 오늘 알게 된 메소드이기도 합니다.

 

---

 먼저 메소드의 설명을 보겠습니다.

 

 리스트의 order를 뒤집는다는 설명만 되어 있어요. 예를 들자면 list에 5, 4, 3, 2, 1 순서가 있었다면, reverse를 호출한 후에는 1, 2, 3, 4, 5가 된다는 말입니다. 대표적인 것으로 ArrayList와 LinkedList가 있는데요. 보통 저는 ArrayList의 순서를 많이 뒤집는 편입니다.

 

 

 위 예제 프로그램을 보겠습니다. ArrayList에 1부터 10까지를 차례대로 넣었습니다. 그리고, 8번째 줄에 Collections의 reverse 메소드를 호출하였습니다. 결과는 어떻게 나올까요?

 

 순서가 뒤집힌 결과가 나옵니다. ArrayList는 indexing이 되는 구조이니, List에 들어간 원소의 갯수가 n개라면 복잡도가 O(n)이 나와도 이상하지 않습니다. 임의의 위치에 접근하는 데 걸리는 시간이 O(1)이기 때문입니다.

 

 

 LinkedList의 경우에도 똑같습니다. LinkedList 객체를 넘겨주기만 하면 거꾸로 뒤집힙니다.

 

 

 어렵지 않군요. 그런데 문득 궁금한 게 있습니다. LinkedList는 Random Access가 안 될 텐데, 리스트에 들어간 원소 갯수가 n이라면, 시간 복잡도가 O(n)이 될까요?

---

 리스트에 들어간 원소의 크기가 10일 때에, 위와 같이 호출이 됩니다. 여기서, node를 주목해 볼 만 한데요.

 

 

 딱 봐도, 절반을 기준으로 끝에서부터 탐색할지, 처음부터 탐색할지 결정함을 알 수 있어요. 그래서, node(index) 메서드는 시간 복잡도가 index에 비례합니다. 그리고, 이 인덱스에 접근하는 메서드를 get이 호출하고, 이 get을 Collections의 swap이 호출하게 되는데요. 이 swap은 아래 줄에서 호출이 되어 버립니다.

 

 

 379번째 for loop가 size에 비례하므로, 378번째 줄의 if문에 걸리는 경우 시간 복잡도는 리스트의 size의 제곱에 비례하게 될 겁니다. 만약에 링크드 리스트에 들어간 원소 갯수가 n개라면, 시간 복잡도는 O(n^2)가 될 겁니다. 그런데, 10만개의 원소를 LinkedList에 넣고 Collections의 reverse 메소드를 호출해 보면 매우 빠르게 동작함을 알 수 있습니다. 최소한 n에 제곱 비례하는 복잡도는 아니라는 이야기입니다.

 

 

---

 무슨 일이 일어난 걸까요? 먼저 LinkedList는 RandomAccess가 가능한 구조가 아닙니다. 그리고, 하나 더 중요한 것은 size가 꽤 크다는 점입니다. 378번째 줄을 보셨다면 아셨겠지만, REVERSE_THRESHOLD라는 조건이 붙었음을 알 수 있는데요. 이것보다 size가 크면서, RandomAccess가 가능하지 않으면, 378번째 if문을 만족하지 않음을 알 수 있어요.

 

 이 값이 java 1.8을 기준으로는 18인데요. 10^5는 18보다는 크니, else 블록으로 내려올 겁니다.

 

 

 else 블록에서는 어떤 일이 일어날까요? fwd와 rev Iterator를 생성하는데요. 중요한 것은, List는 순회 가능한 구조라는 것입니다. 그런데, 한 방향으로만 순회 가능하면 사실상 의미가 없습니다. 단일 연결 리스트가 그러합니다. Java의 LinkedList는 양방향 구조입니다. 즉, 현재 노드가 있다면, 다음 노드의 위치도 알 수 있고, 이전 노드의 위치도 알 수 있습니다. 

 

 

 즉, 이전 위치로 이동하는 것도 O(1)이고, 다음 위치로 이동하는 것도 O(1)임을 알 수 있습니다. 더 중요한 것은 어떤 원소들을 거꾸로 뒤집을 때, 앞에서부터 탐색하는 위치와, 뒤에서부터 탐색하는 위치 2개만을 가지고 뒤집어 버릴 수 있다는 점입니다. 예를 들어, 다음 리스트를 생각해 봅시다.

 

 

 1, 2, 3, 4가 저장이 되어 있다고 해 봅시다. 앞에서부터 탐색하는 이터레이터와 뒤에서부터 거꾸로 탐색하는 이터레이터가 있다고 합시다. 이를 각각, f, b라 하겠습니다.

 

 

 먼저 f가 가리키는 노드에는 4를 b가 가리키는 노드에는 1을 넣습니다.

 

 

 그러면 1과 4가 맞바뀔 겁니다. 다음에 f는 next로 이동하고, b는 이전 원소로 이동합니다. prev가 있으니 당연하게도, 이전 원소로 이동하는 복잡도는 O(1)일 겁니다.

 

 

  f가 가리키는 노드는 3으로, b가 가리키는 원소는 2로 바꿉니다. 그러면 원래 1, 2, 3, 4 순으로 저장되어 있던 것이 4, 3, 2, 1 순서로 저장되어 있음을 알 수 있습니다. 그러면 fwd는 첫 번째 원소를, rev는 마지막 원소를 가리키게 하면 됩니다. 그런데, reverse 메소드에서 rev 이터레이터는 처음에 마지막 원소의 next 값을 가리키게 했는데요. 이 경우, rev 이터레이터가 null 값을 가지고 있어요.

 

 값을 얻어올 때, null인 경우에는 맨 마지막 원소로 이동하고, 그렇지 않으면, 현재 위치의 prev로 이동하고, 해당 item 값을 얻어오게 하면 될 겁니다. 실제로, LinkedList의 ListItr의 prev는 제가 설명한 것과 같이 구현되어 있습니다. 또한 쿼리의 특성상, 한 칸씩 이동하는 연산이 주를 이루므로, Iter의 prev나 next 호출이 주를 이룰 겁니다. 이 연산이 O(1)입니다. 원소 갯수가 n인 경우, next 연산을 n/2번, prev 연산을 n/2번 하게 되므로 복잡도는 O(n)이 됩니다.