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