Skip list1 스킵 리스트 (skip list) 동작 방법 skip list는 linked list와 비슷하게 다음 원소를 가리키는 포인터를 가지고 있다. 그렇기 때문에 데이터의 삽입/삭제를 빠르게 할 수 있다. 이것은 linked list 특성상 당연해 보이는데 skip list는 여기에 검색 속도까지 책임진다. linked list부터 시작해서 어떤 방법으로 검색 속도를 향상시키는지, 부작용은 없는지 확인해보자. 시간 복잡도 $O(n)$ 공간 복잡도 $O(n)$ linked list를 먼저 그려보면 위와 같다. 삽입/삭제는 앞, 뒤 노드만 수정하면 되기 때문에 빠르게 할 수 있지만 역시 검색이 문제다. 다음 원소를 가리키는 포인터만 따라가서는 당연히 속도가 좋지 않기 때문인데, 포인터를 여러 개 두는 방향으로 이를 개선한다. 그러면 다음 원소뿐만 아니라 그다.. 2019. 10. 17. 이전 1 다음
