linked list 검색
초코향
안녕하세요~^^
전산을 공부하는 전산과 학생인데요
궁금한 것이 있어 이렇게 질문 올립니다~^^
linked list에서 검색을 할 경우 순차 검색을 사용 하는데요.
혹시 순차 검색 말고 더 빠르게 검색하는 방법이 있을 까요?
감사합니다~^^
-
뿡뿡몬
하지만 스택을 배열로 만들었다고 배열이 아니며 스택을 링크드리스트로 만들었다고 링크드리스트가 아닌 것 처럼 어떤 기능으로 구현했건 인터페이스가 링크드리스트라면 링크드리스트가 아닐까요?
-
새
페르샤님 정말 감사합니다^^
-
갅지삘여우
답글로 논문을 올려드리겠습니다....^^;
-
앵겨쪼
linked list의 성능을 개선한 skip list라는 이론이 있습니다. 이이론은 나온지 10여년 밖에 되지 않아서 논문밖에는 없는걸로 알고 있구요. 쉽게 생각하면 linked list와 같지만 foward head의 개수를 늘려서 binary search와 같은 효과를 내주는 이론입니다. 보통 linked list의 탐색, 삽입, 삭제 시간 복잡도가 O(n)이 나온다고 하면 skip list의 탐색,삽입,삭제의 시간복잡도는 O(log n)이 나옵니
-
통꽃
수다님께서 제 질문을 잘못 이해 하신것 같은데 링크드 리스크에서 검색할 경우 입니다. 빠른 검색을 할 경우 당연히 링크드 리스크를 사용하지 않겠죠. 하지만 지금 제 질문에서는 링크드 리스크를 사용할 경우 조금더 빠르게 검색하는 방법이 있을까 였습니다.;; 덧글 감사합니다^^.
-
미쿡
또 다른 방법을 하나 생각해 냈는데, Splay tree처럼 가장 자주 Access하는 자료나 아니면 그럴 확률이 높은 자료들이 들어 있을 경우 마지막으로 accessed node를 맨 처음으로 갖다 놓는 것입니다. 그렇게 하면 자주 찾게 되어지는 node를 순차 검색할때 가장 먼저 찾게 되므로 시간을 단축시킬수 있습니다.
-
풀잎
찬님의 말에도 일리가 있군요 트리로 만들어 놓은 다음 더블 링크드 리스트로 하면 앞뒤 선택이 가능 할 것이고 힙 이나 바이너리 트리 처럼 검색을 하면 될것 같은 생각이 드네요.
-
아라
linked list와 tree를 각기 만들어 두시고,
linked list로 add remove할때, tree로 소팅해서 같이 포인터를 가지고 있으면 안될까요?
그리고 찾기할때에는 tree로 찾으면... -
달빛
list에 요소를 삽입할때 정렬된 상태를 유지한다면 binary search로 좀 더 빠르게 검색할 수 있지요 ^^
-
가지
저도 생각을 해봤는데요 링크드리스트의 특성상 순차검색 밖에 없지 않을까요? 링크드리스트의 특성이라 함은 임의의 위치에서 삽입과 삭제를 쉽게 마음대로 할수 있는것일텐데요. 빠르게 검색하려고 정렬을 하거나 삽입 삭제에 제한을 둔다면 그건 이미 링크드리스트가 아닌거 같아요
뭐 더 잘 아시는분 있으면 저도 알쿼주세요 ㅠㅠ