면접 질문중 list, map, set의 차이점을 묻는 질문에 어버버한 경험을 상기하며 정리한다.
1. List
'리스트는 순서가 있고 중복이 허용되며 가변적인 크기를 가진 자료구조이다'
특징
- 순서가 있으며 데이터의 중복이 허용된다.
- 크기가 가변적이며, 비어있는 데이터가 없다.
- 원하는 데이터가 뒤쪽에 있을 경우 속도가 떨어진다.
( 리스트를 순회해야 하기 때문 )
1.1 ArrayList
'내부적으로 데이터를 배열에서 관리하며 추가, 삭제를 위해 임시 배열을 생성해 데이터를 복사한다'
특징
- 각 데이터 추가/삭제마다 배열을 새로 만들어 복사해주므로 참조보다 추가,삭제가 많을 경우 불리하다.
1.1.1 Array와 ArrayList의 차이
Array의 경우 길이가 고정되어 변경이 불가하다. ArrayList의 경우 Array를 이용해 만든 List형 자료구조이며 Array와 다르게 길이를 할당하지 않지만 데이터 추가시 배열의 최대 크기가 넘으면 2배 크기의 배열을 만들고 원본을 복사하여 재생성 한다.
Default 길이는 10이다.
ArrayList는 배열을 이용하여 리스트를 구현한 것이다.
다만 배열을 가변적으로 사용하며 리스트가 가지는 특성인 저장순서 유지와 중복 허용의 특징을 가지고 있다.
ArrayList는 클래스이기 때문에 배열을 추가, 삭제 할 수 있는 기능을 함께 포함하고 있다.
1.2 LinkedList
'데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태를 가지고 있다'
특징
- 내부적으로 양방향의 연결 리스트로 구성되어 원소를 순방향 혹은 역방향으로 순회할 수 있다.
- 데이터 참조의 경우 배열에 비해 시간이 오래 걸린다.
2. Map
' Key와 Value의 한쌍으로 이루어진 데이터의 집합'
특징
- key에 대한 중복이 없으며(데이터는 중복을 허용한다.), 순서를 보장 하지 않는다.
- 빠른 검색 속도를 가진다 ' O(1) '
- 인덱스가 따로 존재 하지 않는다.
2.1 HashMap
HashMap은 내부적으로 배열을 만들어 관리하며 key 값으로 넘겨준 객체의 해시 코드를 계산하여 배열의 접근 인덱스로 사용한다.
2.2 TreeMap
TreeMap은 Key-Value 쌍을 내부적으로 RedBlack Tree로 저장하여 관리한다. TreeMap의 시간 복잡도는 O(lon n)이다. 대신 정렬된 순서를 얻을 수 있다.
2.3 LinkedHashMap
LinkedHashMap으로 구현된 Map은 데이터의 입력 순서를 기억한다. LinkedHashMap의 경우 O(1)의 시간 복잡도를 갖지만 Linked-List를 유지하기 위한 비용이 생길 수 있다.
3. Set
' 순서가 보장되지 않는 데이터의 집합으로 중복된 데이터가 들어갈 수 없다'
3.1 HashSet
HashSet은 객체들을 순서없이 저장하고 동일한 객체는 중복 저장하지 않는다. 객체를 저장하기 전에 객체의 hashcode()메소드를 호출해 해시값을 얻고, 이미 저장되어 있는 객체들의 해시코드와 비교한다.
3.2 TreeSet
HashSet과 마찬가지로 중복 저장하지 않지만 오름차순으로 데이터를 저장하고 관리한다. (Red-Black Tree를 사용한다.)
3.3 LinkedHashSet
LinkedHashSet의 경우 HashSet과 동일하지만 입력된 순서를 저장하고 관리한다.
