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

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

<br>

## 🔖 14.1. 스킵 리스트란?

### 연결 리스트의 문제점

* 연결 리스트는 노드들이 순차적으로 연결되어 있기 때문에, 특정 원소를 찾으려면 처음부터 끝까지 탐색해야 함
* 따라서 탐색 속도가 O(n) 으로 느림

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

* 일부 노드를 "건너뛰는 포인터"를 추가하여, 탐색 속도를 향상시킴
* 노드마다 여러 개의 레벨(level)을 가질 수 있으며, 높은 레벨일수록 더 멀리 이동할 수 있는 포인터를 포함함
* 결과적으로 탐색, 삽입, 삭제 연산이 평균적으로 O(log n) 의 시간 복잡도를 가짐

<br>

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

### 구조

* 스킵 리스트는 여러 개의 레벨을 가진 정렬된 연결 리스트로 볼 수 있음
* 가장 아래 레벨(레벨 1)은 일반적인 연결 리스트와 같음
* 위쪽 레벨로 갈수록 일부 노드만 포함하여, 더 빠르게 건너뛰며 탐색할 수 있음

### 탐색 과정 (Search)

1. 최상위 레벨(가장 높은 레벨)에서 시작
2. 현재 노드의 다음 노드 값과 찾는 값 비교
   * 찾는 값보다 크다면, 아래 레벨로 이동
   * 찾는 값보다 작다면, 오른쪽으로 이동
3. 가장 낮은 레벨에 도달하면 정답을 찾음

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

<br>

### 삽입 과정 (Insert)

1. 새로운 노드를 삽입할 위치 탐색
2. 확률적으로 레벨을 결정 (예: 50% 확률로 위 레벨로 올라갈 수 있음)
3. 선택된 레벨에 따라 새로운 포인터 연결

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

<br>

### 삭제 과정 (Delete)

1. 삭제할 노드를 탐색하면서, 해당 노드를 가리키는 포인터들을 찾음
2. 각 레벨에서 노드 제거 후 포인터 재연결

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

<br>

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

* 탐색, 삽입, 삭제 모두 평균적으로 O(log n) 의 성능을 가짐
* 최악의 경우(모든 노드가 한 개의 레벨만 가지는 경우)에는 일반 연결 리스트와 동일하게 O(n) 이 될 수도 있음
* 하지만 무작위화(randomization) 를 활용하여 대부분의 경우 이진 탐색 트리와 비슷한 성능을 유지할 수 있음

<br>

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

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

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

<br>

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

* 데이터베이스 인덱싱: 빠른 탐색이 필요한 경우 사용
* 캐시 시스템: 최근 데이터 검색을 빠르게 처리할 때 유용
* 분산 시스템 (e.g. LevelDB, Redis): O(log n) 성능을 유지하면서 데이터 저장

<br>

## 🎯 스킵 리스트 핵심 정리

* 연결 리스트의 느린 탐색 속도를 개선하기 위해 "건너뛰기" 개념을 도입한 자료 구조
* 탐색, 삽입, 삭제 속도가 평균적으로 O(log n)
* 균형 트리(BST)와 비슷한 성능이지만, 균형 유지가 필요하지 않음
* 무작위화를 이용해 최악의 경우를 방지할 수 있음
* 데이터베이스, 캐싱, 분산 시스템에서 널리 사용됨
