[TypeScript] 자료 구조로 담아내기. #8 - 연결 리스트

연결 리스트는 가장 간단한 형태의 연결된 자료 구조입니다. 이는 배열과 달리 순차 접근을 기반으로 합니다.

순차 접근

순차 접근은 임의 접근과 달리 임의의 위치에 한 번에 접근할 수 없습니다. 목표에 접근하기 위해서는 우선 선임자에 접근해야 합니다. 선임자에 접근하기 위해서는 또 그 선임자에 먼저 접근해야 합니다. 즉, 이름에서도 알 수 있듯이 모든 접근은 순차적으로 이루어집니다.

그중에서도 연결 리스트의 접근은 마치 반복자와 유사합니다. 첫 노드를 시작으로 원하는 위치에 도달할 때까지 후임자 참조를 통해 순회합니다.

const node0 = node;
const node1 = node0.next();
const node2 = node1.next();

// ...

왜 순차 접근인가?

그렇다면 왜 순차 접근 방식이 필요할까요? 이러한 방식은 매우 불필요한 오버헤드처럼 느껴질 수 있습니다.

조금 관점을 바꿔 봅시다. 우선 임의 접근에 대해 다시 생각해 볼 필요가 있습니다. 이는 모든 위치에 직접 접근하는 것입니다. 바꿔 말하면 사전 규칙에 따라 접근자를 유추할 수 있어야 한다는 뜻이기도 합니다. 컴퓨터 프로그래밍 세계에서 일반적인 접근자는 메모리 주소일 것이고요. 결국 임의 접근은 시작 주소로부터 떨어진 거리에 따라 메모리 주소를 유추할 수 있는 체계로 구현됩니다.

좋습니다. 임의 접근은 매우 빠릅니다. 이것만으로 충분한가요? 흠, 글쎄요. 정말 접근 속도 하나만을 고려한다면 이보다 훌륭한 해결책은 없을 것입니다. 하지만 지나치게 경직되어 있다는 생각이 들지는 않나요? 규칙은 변경할 수 없고, 위치는 정해진 규칙에 따라야만 합니다. 이러한 제약은 때로 매우 불합리하게 다가올 수 있습니다.

순차 접근을 구현하는 일반적인 아이디어는 연결입니다. 이는 원하는 위치에 다음 위치에 대한 접근자를 저장하는 방식으로 구현됩니다. 모든 위치는 런타임에 자유롭게 지정될 수 있습니다. 따라서 매우 큰 메모리 덩어리를 할당할 필요가 없습니다. 접근은 오직 서로에 대한 연결에 의존할 뿐, 위치 지정에 일절 규칙이 없기 때문에 지정한 두 위치 사이에 새로운 위치를 끼워 넣는 것도 쉽습니다. 그저 관련된 몇몇 위치 간 연결을 재설정하면 될 뿐입니다.

간단하면서 강력하다!

순차 접근은 일반적으로 연결을 통해 구현되며, 연결을 활용하는 매우 많은 자료 구조가 있습니다. 상술했듯 연결 리스트는 그중 가장 간단한 축에 속합니다. 하지만 간단하다고 실망하진 마세요. 연결 리스트는 다음 단계로 나아가는 추진력이면서 동시에 많은 아이디어를 선사할 것입니다. 물론 자료 구조로써 자체적인 강력함도 빼놓을 순 없겠지요. 이번 파트도 즐거운 시간이 되길 바랍니다!

내용은 다음 편에서 이어집니다. 읽어주셔서 감사합니다!

묻고 답하기

개인적인 판단에 의해 적절하다고 여겨지는 경우, 모두가 볼 수 있도록 이곳에 문답이 추가됩니다. 그렇지 않더라도 질문에 대한 답변은 별도로 이루어집니다.