링크드 리스트가 Search가 느림
느린이유가 포인터가 하나있어서 그 포인터를 순서대로 따라갈수밖에 없기 때문
binarysearch하려면 중간쯤을 찍을수 있어야하는데 중간을 한번에 찍을 방법이 없잖아
아 그러면 노드에 포인터를 하나만 둘 필요가 없거든요. 중간으로 가는게 안됨? 그럼 첫 노드에서 그냥 중간으로 가는걸 넣지 뭐
혹은, 아예 헤드 포인터가 여러개라서 한놈은 첫번째를 가리키고 다른하나는 중간껄 가리킬수도있어.
갔다가 두번에 가도되니까..그냥 첫 노드가 중간 노드 가리키는 포인터 하나 더 있다고 생각해
소팅되어있다고 생각하고 중간으로 가는 포인터가 있다고 치자.
우리가 x를 찾으려 한다고 치면 첫번째에서 찾고 없으면 바로 중간에 있는 노드로 넘어가서 그 값과 x를 비교하게됨
결국 한번만 비교를 해서 절반을 날릴 수 있게되지
이 아이디어를 멈출 이유가 없음
그래서 왼쪽의 절반으로 가는 포인터가 또있음.
그 안에도 중간으로 가는포인터가 또 있음
재귀재귀!
안에서도 똑같은 일이 계속 일어나는거야
이게 실제로 쓰는 자료구조임
이름이 Skip list야