이진 탐색 트리의 대안으로 Skip List도 존재한다.

위 그림은 1, 3, 5, 7, 9가 저장된 스킵 리스트를 나타낸 것이다.

여러 층으로 구성되어 있으며, 위 층을 통해 아래층의 원소를 건너뛸 수 있다.

각 층마다 2개 또는 3개의 원소 간격으로 위층과 연결된 링크가 존재해야 한다.

위 Skip List에서 4를 추가하는 과정을 그림으로 나타내면 다음과 같다.

BST에서처럼 원소들을 건너뛸 수 있어, O(logn) 시간 insert가 가능하다.

마찬가지로 O(logn) 시간 search, delete도 가능해진다.

위 그림에서 원소 6이 추가되면 다음과 같아진다.

맨 아래 층에서 3개의 원소를 거치는 동안 위층으로 가는 링크가 등장하지 않았다. 따라서 위층에 원소를 추가하여 skip list 조건을 회복시켜야 한다.

위 그림과 같이 둘째 층에 원소 5와 링크가 추가되었다.

추가된 5 주위를 살펴보면, 둘째 층의 3, 5, 7에서도 위로 가는 링크가 없음을 발견할 수 있다. 그러므로 첫째 층에도 원소 5를 추가해 주었다.

그런데 맨 윗층에 세 개의 원소가 있는데도 (위층이 아예 존재하지 않으므로) 위로 가는 링크가 하나도 없다. 이런 경우 새로운 층을 추가해 주면 된다.