skip list 소개

William Pugh의 Skip list 논문을 참조해서 Skip list를 구현하고 있다.

이 논문에서는 max level이 대략적인 원소의 갯수에 따라 미리 정해져야 한다고 나와 있는데, 이것을 동적으로 증가하는 방식으로 구현하려니까 조금 복잡해지고 있다.

또한 template을 써서 generic하게 만들려고 계획 중이다.

현재, search와 insert가 제대로 되는 것을 확인한 버전까지 완료되었다.
(delete는 insert와 알고리듬이 비슷하다.)

Skip list는 Java SE 6에 ConcurrentSkipListSet, ConcurrentSkipListMap이라는 이름의 컬렉션으로 제공된다. 개발자라면 주목할만한 자료구조라고 할 수 있다.