며칠 전 트위터에서였다(아, 사랑하는 트위터여: 무슨 일이 일어나든 나는 가능한 한 오래 그곳에 있을 것이다 — 트위터를 만드는 데 많은 에너지를 쏟은 사람들을 생각한다면, 플랫폼을 떠나기 전에 다시 한번 생각해 보길 바란다). 그곳 트위터에서 나는 Rust로 작성된 아주 형편없는 연결 리스트 구현에 대해 이야기하고 있었다. 몇몇 답글의 어조를 보니 많은 사람들이 연결 리스트를 농담거리 정도로 여기는 것 같았다. 코딩 인터뷰에만 쓸모 있을 뿐 그 외에는 전혀 쓸모없는 하찮은 자료구조라는 것이다. 한마디로 자료구조계의 버블 정렬인 셈이다. 나는 동의하지 않았고, 그래서 내가 사랑하는 연결 리스트의 모든 것을 담아 이 글을 쓰기로 했다.

그러니 자료구조에 대한 감상적인 글을 읽을 준비를 하시길. 미리 경고하지 않았다고는 하지 마시길.

연결 리스트는 교육적이다. 선생님이든, 책의 한 페이지든, 혹은 처음으로 연결 리스트를 접하게 해주는 어떤 것이든, 화살표로 다른 원을 가리키는 작은 원을 보여주는 순간 머릿속에서 거대한 무언가가 일어난다. 처음으로 재귀를 이해했을 때와 비슷하다. 링크로 이루어진 자료구조가 진정 무엇인지 깨닫게 된다. 단일 노드의 사소함이 다른 노드를 참조하는 순간 훨씬 더 강력하고 복잡해진다는 것을 말이다. 연결 리스트는 초보 프로그래머에게 계산에서의 공간과 시간에 관한 근본적인 것들을 보여준다. 어떻게 원소를 상수 시간에 추가할 수 있는지, 그리고 순서가 본질적으로 왜 비용이 드는지 — “제자리”에 원소를 삽입하려면 한 노드에서 다른 노드로 이동해야 하기 때문이다. 그러면 곧바로 그 과정을 더 빠르게 할 방법을 고민하기 시작하고(이것이 다음 단계로 나아가기 위한 준비가 된다), 동시에 O(1)과 O(N)이 진정 무엇을 의미하는지 깊이 이해하게 된다.

연결 리스트는 확장 가능하다. 이전 원소를 가리키는 포인터 하나만 추가하면 양쪽으로 이동할 수 있게 된다. 가끔씩 “먼” 포인터를 추가하면 전혀 다른 특성을 가진 스킵 리스트가 된다. 각 노드가 여러 항목을 담도록 바꾸면 연결 리스트는 언롤드(unrolled) 리스트가 되어 캐시 측면에서 전혀 다른 특성을 제공한다. 연결 리스트는 임베드될 수도 있다. 예를 들어 Linux 커널에는 어떤 구조체든 서로 연결할 수 있도록 필드를 추가하는 매크로가 있다. 더 있다. 연결 리스트는 조합 가능하다. 이는 대담한 특성이다. 연결 리스트를 O(1) 시간에 두 개로 나눌 수 있고, 두 연결 리스트를 O(1) 시간에 하나로 합칠 수도 있다. 이 특성을 현명하게 활용하면 흥미로운 일들이 가능해진다. 예를 들어 스레드 연산을 구현한 Redis 모듈에서는, 느린 요청을 처리하는 스레드가 가짜 클라이언트 구조체를 다루었다(이 덕분에 락도, 경합도 없었다). 스레드에서 실행되던 명령이 마침내 실행을 마치면, 해당 클라이언트의 출력 버퍼를 실제 클라이언트의 버퍼에 그대로 이어 붙일 수 있었다. 출력 버퍼가 연결 리스트로 표현되어 있었기에 이는 쉬운 일이었다.

연결 리스트는 유용하다. Redis 하나가 틀릴 수는 있어도, Redis와 Linux 커널이 동시에 틀릴 수는 없다. 연결 리스트가 유용한 이유는 특정한 자연스러운 과정을 닮았기 때문이다. 도착한 순서대로, 혹은 역순으로 무언가를 추가하는 일은 물리적 세계에서도 자연스럽다. 항목을 하나씩 꺼내는 것도 유용하고, 그런 항목들을 head에서 tail로 옮기거나 현재 위치 다음으로 옮기는 것도 마찬가지다.

연결 리스트는 단순하다. 이진 트리나 해시 테이블 등 몇 안 되는 자료구조와 함께, 기억에만 의존해 구현해도 큰 실수 없이 만들 수 있는 드문 자료구조 중 하나다.

연결 리스트는 개념적이다. 자기 자신을 가리키는 노드는 컴퓨팅에서 상상할 수 있는 가장 자기중심적인 존재다. 가장 저속한 무한 루프를 이상적으로 표현한 것이다. NULL을 가리키는 노드는 고독의 은유다. tail과 head가 연결된 연결 리스트는 닫힌 순환의 강력한 상징이다.

이러한 모든 이유 때문에 나는 연결 리스트를 사랑하며, 여러분도 최소한 연결 리스트를 보며 미소 짓기 시작하길 바란다.