스킵 리스트는 여러 포인터가 있는 정렬된 연결 리스트로 탐색, 삽입, 제거와 같은 연산을 하면서 리스틑에서 더 앞에 있는 원소로 가끔 건너뛸(skip, 스킵) 수 있게 해준다. 이런 스킵 기능은 연결 리스트의 큰 문제점인 목표를 찾기 위해 리스트에 속한 모든 원소를 스캔해야 한다는 걸 완화해준다.

⇒ 시간 감소

스킵 리스트는 삽입, 제거, 탐색 등의 연산을 훨씬 효율적으로 만드는 확률 자료 구조.

스킵 리스트를 소개하는 이유

1. 자료 구조와 마찬가지로 스킵 리스트는 추가 정보나 구조를 통해 중요한 알고리즘적 이점을 제공 → 다중 계층의 링크가 탐색 비용을 감소시킨다.
2. 확률적 자료 구조로 무작위성(randomness)을 더 많이 채용한다.

14.1 무작위적 구조와 결정적인 구조의 비교

삽입할 때마다 매개변수를 무작위로 선택함으로써 데이터의 순서를 변화시키는 대신 데이터를 구조에 연결하는 방법을 변화시킨다.

무작위성은 평균적인 경우의 성능을 향상시킬 수 있다. 또, 무작위성은 데이터가 비상식적으로 나쁜 순서로 도착하는 경우의 손해를 완화시키는데 도움이 된다.

14.2 스킵 리스트 소개

항상 강제로 한 노드에서 다른 노드로 포인터를 따라가야만 원하는 노드에 도달할 수 있다.

스킵 리스트는 이런 비효율성을 완화하기 위해 여러 원소를 한 번에 건너뛸 수 있는 기능을 제공한다. 스킵 리스트는 단순한 정렬된 연결 리스트이며, 각 노드가 여러 레벨을 가질 수 있다.

SkipList {
	Integer: top_level
	Integer: max_level
	SkipListNode: front
}

top_level: 현재 사용 중인 가장 높은 레벨

max_level: 허용 가능한 최대 레벨

스킵 리스트의 복잡성과 그 복잡도로 생기는 효율성은 노드 내부의 포인터 구조에서 비롯된다. 리스트의 다음 노드를 가리키는 포인터를 노드마다 하나씩만 저장하는 대신, 스킵 리스트의 각 노드는 미리 정해진 레벨, 또는 높이가 있으며, 수준마다 다음 노드에 대한 포인터를 저장한다.

SkipListNode {
	Type: key
	Type: value
	Integer: height
	Array of SkipListNodes: next
}

스킵 리스트에서 더 높은 레벨은 그보다 낮은 레벨보다 노드를 더 적게 포함하기 때문에, 높은 레벨의 노드들은 낮은 층에서는 불가능한 더 먼 거리로 연결될 수 있다.