연결 리스트에서 index를 사용하여 빠르게 탐색하기

연결 리스트는 간단하게는 선형 연결 리스트에서부터 복잡하게는 여러 트리까지 많은 곳에서 사용하는 자료 구조이다. C와 같은 로우레벨에서 자료들을 저장하고 삭제하는데 효과적이다. C에서 기본으로 제공하는 배열은 삽입과 삭제의 비용이 크지만 연결 리스트는 그렇지 않고 그 구조도 배열처럼 선형으로 구성하지 않고 다른 여러 방식으로 구성할 수 있다.

하지만 C에서 연결 리스트를 직접 구현해보면 치명적인 단점을 발견하게 되는데, 기본적인 선형 연결 리스트에서 특정 노드를 탐색하는 방법은 순차 탐색 밖에 없다는 것이다. 중간에 있는 노드들을 곧바로 접근하지 못하니 이진 탐색은 그 비용이 너무 크다. 이런 점을 극복하기 위해 선형 연결 리스트가 아닌 트리로 구조를 바꾸면 탐색이 훨씬 빨라지지만, 일단은 선형 연결 리스트에서 탐색 속도를 빠르게 하는 방법을 알아보자.

색인

만약 연결 리스트를 항상 정렬된 상태로 저장한다고 하자. 노드의 삽입은 언제나 탐색 과정을 동반할 것이다. 하나의 노드를 삽입한다면 O(n)의 시간 복잡도를, n개의 노드를 삽입한다면 O(n^2)의 시간 복잡도를 갖는다. 노드의 삽입이 오래 걸리는 이유는 결국 탐색이 오래 걸리기 때문이고, 탐색이 오래 걸리는 이유는 탐색 방법이 순차 탐색이기 때문이다.

논의 대상인 연결리스트의 노드는 다음과 같은 기본적인 구조를 갖는다고 하자.

| 데이터 |
| 다음 노드를 가리키는 포인터 |

이런 노드를 갖는 연결리스트는 어쩔 수 없이 헤드에서부터 순차 탐색을 해야한다. 중간에 있는 노드를 접근할 방법이 없기 때문이다. 그렇다면 특정 노드들에 접근할 수 있는 노드 포인터들을 외부에 갖고 있다면 어떨까?

| node1 | node2 | node3 | node4 | node6 | node7 |

6개의 정렬된 노드를 가진 연결 리스트가 있다. 우리가 node5라는, node4와 node6 사이에 삽입될 노드의 위치를 특정하고 싶다고 하자. node1을 가리키는 head만 갖고 있다면 최악의 경우 node1부터 node7까지 모든 노드를 순회해야 한다. 하지만 node4의 주소를 알고 있다면 어떻게 될까? 먼저 삽입하려는 node5와 node4를 비교한다. 삽입하려는 노드가 더 크므로 node4 아래의 노드들은 비교하지 않아도 된다. 따라서 탐색해야할 범위가 6개에서 3개로 줄게 된다.

정렬된 노드들은 항상 어떤 기준으로 나누어질 수 있고 이를 보통 색인이라고 한다. 만약 1부터 100까지 저장되어 있다면 10, 20, 30, 40 등이 색인의 역할을 할 수 있다. 마치 사전에서 단어를 찾듯이, 어떤 숫자의 위치를 찾으려면 이 색인을 이용해서 찾을 수 있다. 46의 위치를 찾으려면 먼저 46이 어떤 색인에 해당하는지 알아야 한다. 십의 자리가 4이므로 탐색을 시작해야 할 색인은 40이다. 또한 십의 자리가 4라는 것은 50보다 작다는 것이므로 색인 50 이상의 숫자들은 탐색할 필요 없다. 따라서 46의 위치를 알기 위해서는 색인 40부터 50전까지만 탐색하면 된다.

색인의 구조

색인이 무슨 역할을 할 수 있는지 알았다. 그렇다면 색인은 어떻게 설계해야 할까?

색인을 활용하여 하고 싶은 일은 결국 탐색이다. 찾고자하는 노드가 연결리스트에 존재하는지, 존재한다면 그 위치가 어디인지, 존재하지 않지만 새로 만들어 넣는다면 어디에 들어가야 하는지 알고싶다. 만약 노드의 존재 여부만을 알고 싶다면 노드 하나를 가리키는 단일 노드 포인터만으로도 충분히 특정 범위의 색인을 구현할 수 있다. 하지만 현재 연결리스트에 존재하지 않는 새 노드가 들어갈 위치를 탐색할 경우, 색인 범위의 바로 앞 노드도 가리켜야 한다.

node1	node2	node3	node4	node5	node6
10	11	12	22	24	27

만약 위와 같은 연결 리스트가 존재한다고 하자. 색인은 두 개로, 10 값을 갖는 node1을 가리키는 1번 색인 하나와 22 값을 갖는 2번 색인 하나가 있다.

index1	index2
node1	node4

여기서 24의 값을 갖는 노드가 존재하는지 찾는다면 index2를 참조하여 node4부터 탐색하면 된다. 하지만 만약 21의 값을 갖는 새 노드가 들어갈 자리를 찾는다면 어떨까?

먼저 이 노드는 index2의 범위에 해당한다. 앞자리가 2이기 때문이다. 그래서 index2부터 탐색을 시작하였더니 index2가 가리키는 첫 노드 node4가 새 노드보다 크다. 그 말은 node4앞에, node3뒤에 새 노드가 들어간다는 뜻이다. 우리의 index2는 node4만을 가리킨다. 이중 연결 리스트라면 node4에서 손쉽게 node3의 위치를 참조할 수 있다. 하지만 위에서 보였던 것처럼 단일 연결 리스트로 구현되었다면 index2에서 node3의 위치를 특정할 방법이 없다. 하지만 새 노드를 node4앞에 삽입하기 위해서는 node3의 위치을 알아야 한다.

이를 해결하기 위해 이중 연결 리스트를 사용할 수도 있다. 어찌보면 더 확장가능한 방법이라고 생각한다. 여기서는 색인의 구조를 달리하여 보았다. 만약 색인이 이 두 요소를 갖는 구조체로 정의된다면 조금 복잡하더라도 해결할 수 있다.

| index node 포인터 |
| 이전 node 포인터 |

index node는 위의 예시에서 node 4에 해당한다. 이전 node 포인터는 항상 index node 의 바로 앞 노드를 가리킨다. 이렇게 구성되어 있다면 우리는 색인 범위의 첫 노드로 새 노드를 삽입할 수 있다.

이전 노드를 가리키는 포인터

어차피 이전 노드 포인터를 안다면 바로 그 뒤에 위치한 index 노드 포인터가 굳이 필요한지 궁금할 수 있다. 이에 대한 대답은 색인에 접근하는 방법 속에서 발견할 수 있다. 위의 예시에서 만약 앞자리가 3인 노드들을 가리키는 index3 색인과, 4인 노드들을 가리키는 index4 색인이 있다고 하자. 두 색인 범위에 노드가 하나도 없다면, 이 두 색인의 이전 노드 포인터는 모두 node6을 가리키고 있을 것이다.

index3의 이전 노드 포인터의 다음 노드(색인 범위의 첫 노드)부터 index4의 이전 노드 포인터까지 탐색하면 새 노드의 위치를 특정할 수 있다. 만약 index3의 이전 포인터와 index4의 이전 포인터가 같은 주소를 가리킨다면 index3은 비어있다. 같은 주소가 아니라면 index4의 주소가 될 때까지 탐색하면 된다. 이를 통해 사실 index_node 자체는 필요하지 않다는 것을 알 수 있다. index_node는 before_node로부터 유도될 수 있다. 중요한 것은 before_node는 항상 특정 색인 범위 바로 앞에 존재하는 노드를 가리켜야 한다는 것이다.

종합해 보자면 이제까지 설명한 방법은 결국 연결리스트의 각 부분을 나누는 것이라고 볼 수도 있다. 각 색인의 이전 노드는 각 연결리스트의 헤드에 해당하고 모든 연결리스트의 테일은 다음 연결리스트의 첫 노드를 가리키는 것이다. 결국 연결리스트에 색인을 추가하여 이를 이용해 탐색하는 것은 전체 데이터를 어떤 규칙으로 분류하여 작은 연결리스트 여러개에 나누어 저장하는 것과 다를 바 없다.

마치며

인덱스를 구현하는 것은 탐색 알고리즘을 새로 구현하는 것이 아닌 탐색할 범위를 좁히는 과정에 불과하다. 과연 연결리스트 단독으로 방대한 양의 데이터를 저장하는 것이 올바른 것인지 의문이 들게 한다. 배열에 저장하여 관리하기 까다롭다면 트리를 사용하는 것이 더 가치있지 않나 싶다.