이 글은 2022년 11월 5일 18시 00분 (KST)을 기준으로 한 In defense of linked lists - antirez 의 번역입니다. 전문 지식의 부재나 영어 실력의 부족으로 오역이나 매끄럽지 않은 문장이 포함되어 있을 수 있습니다. 수정 제안은 댓글이나 public.ranolp@gmail.com으로 연락해주십시오.
며칠 전 Twitter에서 (오 친애하는 Twitter여, 나는 무슨 일이 있더라도 Twitter에서 최대한 오래 버텨볼 겁니다. Twitter를 만드는 데에 온 힘을 쏟는 사람들을 걱정하신다면, 떠나기 전에 다시 한 번 생각해보십시오). 그러니까 Twitter에서, Rust로 작성한 아주 나쁜 연결 목록(Linked List) 구현에 대해 이야기하고 있었습니다. 특정 어조의 답글을 보며, 사람들이 연결 목록이란 걸 사실상 농담처럼 여긴다고 느꼈습니다. 연결 목록이 코딩 인터뷰에 유용할 뿐인 사소한 자료 구조이고, 그 외에는 사실상 쓸모가 없다는 의견이었죠. 다른 말로 하자면, 자료 구조 계의 거품 정렬(Bubble Sort)이라고 말이에요. 저는 이에 동의하지 않습니다. 그래서 제가 연결 목록을 사랑하는 모든 이유를 담아 이 블로그 게시글을 작성하고자 마음먹었습니다.
자, 이제 자료 구조를 설명하는 감성적인 게시글을 읽을 준비를 하시고, 제가 경고하지 않았다고 말하진 말아주세요.
연결 목록은 교육적입니다. 교육자나 책 어느 한 켠, 뭐가 됐든 당신에게 연결 목록을 처음으로 선보이는 것들은, 대개 연결 목록을 작은 원과 그 원에서 다른 원을 가리키는 화살표로 표현합니다. 그리고 그게 당신의 머릿속에서 엄청난 일을 만들죠. 재귀를 처음 이해했을 때 일어나는 일과 비슷합니다. 연결(Link)이란 것으로 구성된 자료 구조가 진정 무엇인지 알 수 있게 됩니다. 아주 단순한 정점(Node) 하나가 다른 정점을 참조할 때 훨씬 강력하고 복잡해진다는 것을요. 또, 연결 목록은 새내기 프로그래머에게 계산(Computation)에서 공간과 시간에 대한 근본적인 것들을 보여줍니다. 어떻게 원소를 덧붙이는 게 상수 시간에 일어나는지, 어째서 순서가 본질적으로 값비싼지를요. 그건 "특정 위치에" 원소를 삽입하려면 한 정점에서부터 해당하는 정점까지 가야 하기 때문이죠. 그럼 당신은 곧장 어떻게 이걸 빠르게 만들 수 있을지 생각(다음 학습을 위해 준비)합니다. 또 동시에 O(1)과 O(N)이 의미하는 게 무엇인지 깊이 이해하게 됩니다.
연결 목록은 확장하기 쉽습니다. 이전 원소를 가리키기 시작하면 우리는 앞뒤로 이동할 수 있습니다. "먼" 지점을 가리키기 시작하면 완전히 새로운 속성을 가지는 건너뛰기 목록이 생깁니다. 여러 값을 갖도록 정점을 고치면, 연결 목록이 풀어져 색다른 캐시 명확성 속성을 제공합니다. 거기에 더해, 연결 목록은 어딘가에 끼워넣을 수 있습니다. 예를 들어, Linux 커널에는 어떤 구조체든 연결을 위한 필드를 추가해주는 매크로가 있습니다. 나아가, 연결 목록은 합성 가능합니다. 이건 꽤 강렬한 특성인데, 연결 목록을 둘로 쪼개는 건 O(1)입니다. 그리고 두 연결 목록을 붙이는 것 역시 O(1)입니다. 이 특성을 지혜롭게 사용하면 재미있는 것들이 가능해집니다. 예를 들어, 스레드 작업을 구현하는 Redis 모듈에서, 느린 요청을 처리하는 스레드는 (락을 잡지도 않고, 자원 경쟁도 없애기 위해) 가짜 클라이언트 구조를 활용했습니다. 스레드를 활용한 명령 실행이 끝났을 때, 클라이언트의 출력 버퍼는 진짜 클라이언트의 실제 버퍼에 붙여버릴 수 있습니다. 출력 버퍼를 연결 목록으로 표현했기 때문에 아주 쉽게 할 수 있습니다.
연결 목록은 유용합니다. Redis는 틀렸다 쳐도, Redis와 Linux 커널 모두가 틀리진 않았겠죠. 연결 목록의 연산은 자연스럽게 쓰는 몇몇 진행 과정과 서로 닮아서 유용합니다. 도착한 순서대로 혹은 역순으로 덧붙이는 건 물리적인 세계에서 아주 자연스럽습니다. 차례차례 물건을 가져가는 것도 유용하긴 마찬가지죠. 그건 그냥 첫 원소에서 끝 원소를 향해 차례차례 움직이는 것, 현재 원소에서 다음 원소로 반복해 움직이는 것이니까요.
연결 목록은 단순합니다. 이진 트리나 해시 테이블과 같은 몇몇 자료 구조와 마찬가지로, 큰 문제 없이 메모리에 구현해낼 수 있는 흔치 않은 자료 구조입니다.
연결 목록은 개념적입니다. 스스로를 가리키는 정점은 제가 상상할 수 있는 컴퓨터 요소 중 가장 자기중심적입니다. 무한 반복의 이상적인 표현 형태기도 하죠. NULL을 가리키는 원소는 외로움의 비유입니다. 연결 목록의 끝 원소가 다시 첫 원소를 가리킨다면 닫힌 순환을 나타내는 강력한 상징이죠.
그러한 모든 이유로, 저는 연결 목록을 사랑합니다. 그리고 당신 역시 그러할 수 있다면 좋겠습니다. 적어도, 연결 목록을 보며 미소 지을 수 있기를.
