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