배열리스트의 탐색 연산의 시간복잡도에 관한 질문입니다.
각티슈
질문 제목 :배열리스트의 탐색 연산의 시간복잡도에 관한 질문입니다.질문 요약 :배열리스트의 탐색 연산의 시간복잡도에 관한 질문입니다.질문 내용 : 자료구조에 대해서 막 공부하고 있는 학생입니다.
배열리스트의 경우 인덱스를 이용한 참조는 한번의 연산으로 값에 접근할 수 있는데,참조를 인덱스로 하지 않을 경우 즉, 값으로 검색을 해야 할 경우에는 연결리스트와 동일한시간복잡도를 지니게 되는 건가요?
이 경우 연결리스트 대비 배열리스트가 가지는 장점이 하나 없어지므로 배열리스트를사용할 이유가 없겠네요?
배열리스트는 연결리스트에 비하면 별 다른 장점이 없어보이는데, (있다면 검색 연산에서의 속도 우위 정도 말고는 없는 것 같습니다.)실제로 현업에서 쓰이는지 궁금합니다.
-
거울
네 자바에는 해쉬라는게 있더라구요. 키값으로 값에 접근할 수 있는.. 참 편리하다.. 생각하고 넘어갔는데, 답변 덕분에 좀더 알게되었습니다. 아직은 자료구조 초입이라 답변의 모든 내용을 이해하긴 어렵지만요. 감사합니다.
-
엘보어
링크드리스트의 경우 해쉬와 같은 응용구조의 경우 직접접근의 형태로 모든 노드를 상수시간에 가까운 속도로 임의접근이 가능하기도 합니다.
언어에 따라 링크드리스트와 배열이 아무런 차이가 없는 경우도 있고, 이 둘이 아무런 차이가 없어 그냥 해쉬로 취급되는 언어도 있습니다.
루비가 그렇죠. 배열, 즉 리스트가 링크드리스트만 제공되고, 그 링크드리스트는 인덱스를 키로하는 해쉬(내지는 b+트리와 같은 구조)로 되있어서 해쉬와 배열간의 전환이 자유로운.... -
한란
배열과 링크드리스트는 리스트 구현의 한가지 방법들일 뿐입니다.
배열은 그 특성상 임의, 순차 접근 모두 가능하고 구현이 거의 전부 통 메모리로 되어 있기 떄문에 기계적으로 극히 빠른 속도를 가지고 있지만 크기를 늘렷다 줄엿다 하기 힘들거나, 각 원소간의 순서를 바꾼다거나, 중간에 삽입/삭제등의 연산이 일어나면 극단적인 성능저하를 띕니다. 따라서 사용이 제한적이면서 동시에 매우 광범위하게 사용되고 있습니다.
리스트리스트의 경우 대부분의 구현에서 원소의 삽