인프런 커뮤니티 질문&답변
작성한 질문수
배열 링크드리스트
작성
·
113
0
[질문 템플릿]
1. 강의 내용과 관련된 질문인가요? (예/아니오)
2. 인프런의 질문 게시판과 자주 하는 질문에 없는 내용인가요? (예/아니오)
3. 질문 잘하기 메뉴얼을 읽어보셨나요? (예/아니오)
[질문 내용]
여기에 질문 내용을 남겨주세요.
안녕하세요.
자바 HashSet 구현을 할때
이렇게 링크드 리스트를 이용하여 배열을 만들었는데, 질문이 있습니다.
ArrayList 와 LinkedList 중 LikedList 를 사용한 이유는 O(x) 가 더 빠르기 때문인가요 ? 어떠한 장점이 있길래 LinkedList 를 결정한건지 모르겠습니다.
제가 추측하기로는 buckets 내의 각각의 인덱스에 링크드 리스트가 필요하기 때문에 배열 타입을 링크드 리스트로 결정한 것인가요 ?
답변 3
1
안녕하세요. ghuhan18님
이 부분은 각각 트레이드 오프가 있습니다.
이것은 저의 생각이지만 자바에서 ArrayList 대신에 LinkedList를 선택한 이유는 HashSet구조의 특징 때문입니다.
HashSet은 기본적으로 데이터가 잘 충돌하지 않습니다. 따라서 각각의 버킷에 데이터가 함께 들어갈 일이 적습니다. 이 경우 ArrayList를 사용하면 빈 공간이 많을 가능성이 높습니다. 반면에 LinkedList를 사용하면 최적화된 메모리 공간을 할당할 수 있습니다.
감사합니다.
0
좋은 답변 감사합니다. 그런데 , ArrayList 를 사용한다고 해도 추가의 경우 성능상 불이익을 가지지만 삭제는 안되지 않나요 ?
코드 구현을 살펴보면 애당초 contains 메서드를 통해 확인되어서 중복되면 추가되지 않아 삭제될 가능성에 대한 걱정은 하지 않아도 되는 것 아닌가요 ?
0
안녕하세요, 인프런 AI 인턴입니다.
ghuhan18님이 궁금해하신 “ArrayList와 LinkedList 중 LinkedList를 사용하는 이유” 및 “LinkedList를 배열 타입으로 결정한 이유”에 대한 질문은 매우 좋은 질문입니다. 이와 관련하여, “6강 해시 충돌 구현” 강의 부분에서 강사님께서는 해시 테이블에서 LinkedList를 전체 버켓의 컨테이너로 사용하신 이유를 설명하고 계십니다.
LinkedList가 선택된 이유는 그 특성상 추가, 삭제 등의 연산에서 ArrayList에 비해 특정 상황에서 성능 상 이점을 가지기 때문입니다. 해시 테이블에서 충돌이 일어날 경우, 해당 인덱스(버킷)에서 데이터를 추가하거나 삭제할 필요가 있는데, 이러한 연산이 동적으로 빈번하게 일어날 경우 LinkedList가 더 유리할 수 있습니다. ArrayList는 중간 요소를 추가하거나 삭제할 때, 내부 배열의 요소를 이동시켜야 하는 비용이 발생하므로, 이 경우 LinkedList가 더 효율적일 수 있습니다.
질문과 연관된 내용은 다음 링크를 참조하여 주세요:
- “6강 해시 충돌 구현” 관련 질문에서, 공식 서포터즈 David이 3분 2초부터 LinkedList 사용 이유에 대해 간략히 소개하고 있습니다.
LinkedList와 ArrayList 선택에는 위와 같은 고려 사항이 있으며, 실제 사용 시에는 데이터의 양, 연산의 종류, 실행 속도 등 여러 요소를 고려하여 결정하는 것이 좋습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.