며칠 전 Twitter에서 있었던 일입니다. (아, Twitter라니. 무슨 일이 일어나든 가능한 한 오래 여기 남아 있을 생각입니다. 이 플랫폼을 만드는 데 많은 에너지를 쏟은 사람들을 조금이라도 생각한다면, 떠나기 전에 다시 한 번 생각해 보세요.) 아무튼 Twitter에서 Rust로 작성된 아주 형편없는 연결 리스트 구현에 관해 이야기하고 있었습니다. 몇몇 답글의 어조를 보니, 많은 사람이 연결 리스트를 농담처럼 여긴다는 느낌을 받았습니다. 코딩 면접에나 쓸모가 있고 그 외에는 완전히 쓸모없는, 하찮은 자료구조라는 거죠. 한마디로 말하면 자료구조계의 버블 정렬입니다. 저는 그 의견에 동의하지 않습니다. 그래서 연결 리스트의 좋은 점을 제가 사랑하는 모든 것과 함께 풀어낸 이 글을 쓰기로 했습니다.

그러니 자료구조를 주제로 한 감상적인 글을 읽을 준비를 하세요. 미리 경고하지 않았다고 하지는 마시고요.

연결 리스트는 교육적입니다. 선생님이나 책의 한 페이지, 또는 여러분에게 처음으로 연결 리스트를 소개하는 무언가가 작은 원 하나와 다른 원을 가리키는 화살표를 보여 주는 순간, 머릿속에서 엄청난 일이 일어납니다. 처음으로 재귀를 이해했을 때와 비슷합니다. 연결로 이루어진 자료구조의 본질을 깨닫게 되는 것이죠. 단순한 노드 하나가 다른 노드를 가리키는 순간 훨씬 강력하고 복잡해집니다. 연결 리스트는 초보 프로그래머에게 계산에서 공간과 시간이 무엇을 의미하는지 근본적인 사실을 보여 줍니다. 원소를 상수 시간에 추가할 수 있다는 것, 그리고 순서에는 본질적으로 비용이 든다는 것을 말입니다. 원소를 제 위치에 삽입하려면 한 노드에서 다음 노드로 이동해야 하기 때문입니다. 곧바로 이 과정을 빠르게 만들 방법을 고민하기 시작하고(다음에 배울 내용도 준비하게 됩니다), 동시에 O(1)과 O(N)이 실제로 무엇을 뜻하는지 깊이 이해하게 됩니다.

연결 리스트는 확장할 수 있습니다. 이전 원소를 가리키는 포인터를 추가하면 이제 양쪽 방향으로 이동할 수 있습니다. 가끔씩 먼 위치를 가리키는 포인터를 추가하면 전혀 다른 특성을 지닌 스킵 리스트가 됩니다. 각 노드에 여러 원소를 담도록 바꾸면 연결 리스트는 언롤드 연결 리스트가 되어, 캐시 측면에서 매우 다른 특성을 제공합니다. 연결 리스트는 임베드할 수도 있습니다. 예를 들어 Linux 커널에는 어떤 구조체에든 필드를 추가해 구조체들을 서로 연결할 수 있게 해 주는 매크로가 있습니다. 여기서 끝이 아닙니다. 연결 리스트는 조합도 가능합니다. 이건 대단한 특성입니다. 연결 리스트 하나를 O(1)에 둘로 나눌 수 있고, 연결 리스트 두 개를 O(1)에 하나로 이어 붙일 수도 있습니다. 이 특성을 현명하게 활용하면 흥미로운 일이 가능합니다. 예를 들어 스레드 작업을 구현하는 Redis 모듈에서는 느린 요청을 처리하는 스레드가 가짜 클라이언트 구조체를 다뤘습니다. 이렇게 하면 잠금도 경합도 없었습니다. 스레드 명령의 실행이 마침내 끝나면, 클라이언트의 출력 버퍼를 실제 클라이언트의 버퍼에 이어 붙일 수 있었습니다. 출력 버퍼가 연결 리스트로 표현되어 있었기 때문에 이 작업은 쉬웠습니다.

연결 리스트는 유용합니다. Redis의 판단이 틀릴 수는 있어도 Redis와 Linux 커널이 모두 틀릴 수는 없습니다. 연결 리스트가 유용한 이유는 특정한 자연적 과정과 닮았기 때문입니다. 도착한 순서대로 무언가를 추가하거나, 그 역순으로 추가하는 일은 현실 세계에서도 자연스럽습니다. 원소를 하나씩 꺼내는 것도 유용하고, 그런 원소를 헤드에서 테일로 옮기거나 현재 원소의 다음 위치로 이동시키는 것도 유용합니다.

연결 리스트는 단순합니다. 이진 트리, 해시 테이블 등 몇 안 되는 자료구조와 함께, 큰 실수를 저지르지 않고도 기억만으로 구현할 수 있는 드문 자료구조 중 하나입니다.

연결 리스트는 개념적입니다. 자기 자신을 가리키는 노드는 컴퓨팅에서 제가 상상할 수 있는 가장 자기중심적인 존재입니다. 조금 더 저속하게 표현하면 무한 루프를 이상적으로 나타낸 것이기도 합니다. NULL을 가리키는 노드는 외로움의 은유입니다. 테일과 헤드가 서로 연결된 연결 리스트는 닫힌 순환을 상징하는 강력한 기호입니다.

이 모든 이유로 저는 연결 리스트를 사랑합니다. 여러분도 적어도 연결 리스트를 보며 미소 짓기 시작했으면 합니다.