📌읽고 나면 진짜 쉬워지는 자료 구조 - 14. 스킵 리스트

요약: 스킵 리스트(Skip List)는 정렬된 연결 리스트에서 빠른 탐색을 가능하게 하기 위해 일부 원소를 건너뛸 수 있도록 설계된 자료 구조로서, 트리 구조 없이 O(log n) 에 가까운 탐색 성능을 제공하며, 균형 이진 탐색 트리(BST)의 대안으로 사용될 수 있다.

🔖 14.1. 스킵 리스트란?

연결 리스트의 문제점

• 연결 리스트는 노드들이 순차적으로 연결되어 있기 때문에, 특정 원소를 찾으려면 처음부터 끝까지 탐색해야 함

• 따라서 탐색 속도가 O(n) 으로 느림

스킵 리스트의 핵심 아이디어

• 일부 노드를 "건너뛰는 포인터"를 추가하여, 탐색 속도를 향상시킴

• 노드마다 여러 개의 레벨(level)을 가질 수 있으며, 높은 레벨일수록 더 멀리 이동할 수 있는 포인터를 포함함

• 결과적으로 탐색, 삽입, 삭제 연산이 평균적으로 O(log n) 의 시간 복잡도를 가짐

🔖 14.2. 스킵 리스트의 동작 원리

구조

• 스킵 리스트는 여러 개의 레벨을 가진 정렬된 연결 리스트로 볼 수 있음

• 가장 아래 레벨(레벨 1)은 일반적인 연결 리스트와 같음

• 위쪽 레벨로 갈수록 일부 노드만 포함하여, 더 빠르게 건너뛰며 탐색할 수 있음

탐색 과정 (Search)

1. 최상위 레벨(가장 높은 레벨)에서 시작

2. 현재 노드의 다음 노드 값과 찾는 값 비교

   • 찾는 값보다 크다면, 아래 레벨로 이동

   • 찾는 값보다 작다면, 오른쪽으로 이동

3. 가장 낮은 레벨에 도달하면 정답을 찾음

📌 탐색 속도: 평균적으로 O(log n)

삽입 과정 (Insert)

1. 새로운 노드를 삽입할 위치 탐색

2. 확률적으로 레벨을 결정 (예: 50% 확률로 위 레벨로 올라갈 수 있음)

3. 선택된 레벨에 따라 새로운 포인터 연결

📌 삽입 속도: 평균적으로 O(log n)

삭제 과정 (Delete)

1. 삭제할 노드를 탐색하면서, 해당 노드를 가리키는 포인터들을 찾음

2. 각 레벨에서 노드 제거 후 포인터 재연결

📌 삭제 속도: 평균적으로 O(log n)

🔖 14.3. 스킵 리스트의 실행 시간

• 탐색, 삽입, 삭제 모두 평균적으로 O(log n) 의 성능을 가짐

• 최악의 경우(모든 노드가 한 개의 레벨만 가지는 경우)에는 일반 연결 리스트와 동일하게 O(n) 이 될 수도 있음

• 하지만 무작위화(randomization) 를 활용하여 대부분의 경우 이진 탐색 트리와 비슷한 성능을 유지할 수 있음

🔖 14.4. 스킵 리스트 vs. 이진 탐색 트리

비교 항목	스킵 리스트	이진 탐색 트리(BST)
구조	여러 레벨의 연결 리스트	트리 구조 (좌/우 자식)
탐색 속도	평균 O(log n)	평균 O(log n)
최악의 경우	O(n) (레벨이 잘못 분포되면)	O(n) (균형이 무너지면)
구현 난이도	비교적 쉬움	AVL, Red-Black Tree 등 균형 유지 필요
랜덤성 활용	있음	없음

👉 스킵 리스트는 균형 유지가 필요 없는 트리의 대안으로 사용될 수 있음

🔖 14.5. 스킵 리스트의 활용 사례

• 데이터베이스 인덱싱: 빠른 탐색이 필요한 경우 사용

• 캐시 시스템: 최근 데이터 검색을 빠르게 처리할 때 유용

• 분산 시스템 (e.g. LevelDB, Redis): O(log n) 성능을 유지하면서 데이터 저장

🎯 스킵 리스트 핵심 정리

• 연결 리스트의 느린 탐색 속도를 개선하기 위해 "건너뛰기" 개념을 도입한 자료 구조

• 탐색, 삽입, 삭제 속도가 평균적으로 O(log n)

• 균형 트리(BST)와 비슷한 성능이지만, 균형 유지가 필요하지 않음

• 무작위화를 이용해 최악의 경우를 방지할 수 있음

• 데이터베이스, 캐싱, 분산 시스템에서 널리 사용됨