[algorithm] LinkedHashMap - 순서를 유지하는 HashMap
들어가며 릿코드의 LRU Cache 문제를 풀다가 이 자료구조를 알게 되었다. 처음에는 HashMap으로 직접 LRU Cache에 해당하는 알고리즘을 작성하였으나, 입력값이 커지니 Time limit exceed 가 발생했다. 이 문제의 솔루션은 LinkedHashMap 을 확장하는 것으로 별다른 로직 추가 없이 LRU Cache의 요구사항을 만족시킬 수 있었다. 이런 건 그냥 지나갈 수 없다. 간단하게라도 이 자료구조를 학습해보고 정리해본다. LinkedHashMap 이란 무엇인가? HashMap의 모든 기능은 그대로 사용할 수 있다. 추가적으로, 저장된 데이터들의 순서를 유지한다. 순서를 유지하기 위해 이중 연결 리스트 (Doubly Linked List)를 사용한다. 따라서 메모리 사용량이 Hash..
IT/프로그래밍
2020. 2. 22. 16:33
