스킵 리스트(skip list)는 1990년 윌리엄 푸(William Pugh)가 제안한 확률적 자료구조이다. 이 구조는 정렬된 연관 배열을 여러 레벨의 연결 리스트 형태로 구성하여, 평균적인 검색·삽입·삭제 연산을 O(log n)의 시간 복잡도로 수행할 수 있게 한다.
구조 및 동작 원리
- 기본 레벨(레벨 0)에는 모든 원소가 순서대로 연결된다.
- 각 원소는 확률적으로 위 레벨에 “스킵”(skip)되어 포함될 수 있으며, 레벨이 높을수록 포함될 확률은 낮다(보통 1/2).
- 검색 시 최상위 레벨에서 시작해 목표 값보다 큰 첫 번째 노드 바로 전까지 이동한 뒤, 다음 낮은 레벨로 내려가는 과정을 반복한다.
주요 특징
- 확률적 균형: 높이가 로그 스케일로 유지되며, 별도의 재조정 연산이 필요하지 않다.
- 메모리 효율: 트리 구조에 비해 포인터 수가 적고, 구현이 간단하다.
- 응용 분야: 데이터베이스 인덱스, 메모리 내 키‑값 저장소, 네트워크 라우팅 테이블 등에서 활용된다.
어원 및 한국어 표기
‘skip list’는 영어 원어 그대로 “건너뛰다(skip)”와 “목록(list)”의 의미를 결합한 용어이다. 한국어에서는 발음에 따라 “스킵 리스트” 또는 “스킵리스트”로 표기한다.
관련 문헌
- W. Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees,” Communications of the ACM, vol. 33, no. 6, 1990, pp. 668‑676.
- 다양한 교과서 및 논문에서 자료구조 교재의 일부분으로 다루어지고 있다.
요약
스킵 리스트는 확률적 방법을 이용해 균형 이진 탐색 트리와 유사한 성능을 제공하면서도 구현이 비교적 단순한 자료구조로, 현대 컴퓨팅 시스템에서 널리 사용된다.
