스킵 리스트(Skip List)

1. 기본 개념
   도서관 책 찾기로 비유하면:

레벨 2: ---3----------------68-----------------96---> (빠른 이동)
레벨 1: ---3----22----30----68----77----88----96---> (중간 이동)
레벨 0: ---3----22----30----68----77----88----96---> (모든 책)

실제 도서관:
레벨 2: ----소설--------------역사--------------> (대분류)
레벨 1: ----소설----SF----판타지----역사----현대사-> (중분류)
레벨 0: (모든 책들이 순서대로 진열된 책장)

2. 검색 과정:

91을 찾는 경우:

1) 레벨 2에서 시작
   3 → 68 → 96 (96이 너무 큼)
   
2) 레벨 1로 내려옴
   68 → 77 → 88 → 96 (96이 너무 큼)
   
3) 레벨 0에서 정확한 위치 찾기
   88 → 91 (찾음!)

3. 장점:

일반 리스트:
- 91 찾기 위해 모든 숫자 확인
- 3→22→30→55→68→77→88→91
- 8번 이동

스킵 리스트:
- 건너뛰기로 빠른 이동
- 3→68→88→91
- 4번 이동

4. 실제 활용 예시:

온라인 쇼핑몰 상품 정렬:

가격대별 검색:
레벨 2: ----1만원대--------5만원대--------10만원대-->
레벨 1: ----1만원--2만원--5만원--7만원--10만원-->
레벨 0: (모든 상품 가격순 정렬)

7만원대 상품 찾기:
1) 레벨 2: 1만원대 → 5만원대 
2) 레벨 1: 5만원대 → 7만원대
3) 레벨 0: 정확한 가격대 상품

5. 삽입/삭제 예시:

새 상품 추가 (80,000원):

1) 레벨 0에 삽입
   77,000 → 80,000 → 88,000

2) 동전 던지기로 상위 레벨 진출 결정
   - 앞면: 상위 레벨로 진출
   - 뒷면: 현재 레벨에서 멈춤

결과:
레벨 1: (운 좋으면) 진출
레벨 2: (매우 운 좋으면) 진출

6. 실생활 비유:

엘리베이터가 있는 아파트:

일반 계단:
- 1층부터 차례로 이동
- 모든 층 확인 필요

엘리베이터(스킵 리스트):
- 빠른 이동 가능
- 주요 층만 거쳐서 이동

이처럼 스킵 리스트는 여러 층의 리스트를 만들어서 빠른 검색을 가능하게 하는 자료구조입니다. 각 층에서 건너뛰기가 가능해 효율적인 검색이 가능합니다.