💚 자료구조 - List와 Set의 차이점

List

1. 같은 종류의 아이템을 저장

2. 순서를 보장, 중복을 허용

• 2000~ 2024년까지 연예 대상을 수상한 예능인을 순서대로 저장

  • 연예대상을 여러번 받았을 수 있음(중복 허용), 순서대로 저장(순서를 보장)

• 탐색 알고리즘 : 완전 탐색

• 용도 : index 접근이 필요할 때

• 특징 : index 접근 가능

Set

1. 같은 종류의 아이템을 저장

2. 순서를 보장하지 않음.

3. 중복을 허용하지 않음.

• 월드컵에서 한번이라도 골을 넣은 선수 이름을 저장(선수 이름은 다 다르다)

  • 순서도 상관 없고 중복이 되면 안 됨.

  • 만약 List에 넣는다면?

    • A, B, C, D, E 선수가 존재한다. A선수가 골을 넣고 ㆍㆍㆍE 선수까지 골을 넣었을 때, A선수가 다시 골을 넣는다면? List 안에 있는지 확인해야 되기 때문에 처음부터 끝까지 List를 확인해야 된다.

    • 여기서 확인하는데 시간이 빨리 끝날 수도 있지만 위치에 따라 오래 걸릴 수도 있다. 즉, 데이터가 있는지 확인하기 위해 걸리는 시간이 일정하지 않다.

• 탐색 알고르즘 : 해시 함수 & 버킷

• 용도 : 포함 여부만 확인할 때

• 특징 : 중복값 제거, 요소 오름차순 정렬, index 접근 불가

HashMap

HashMap은 키-값 쌍(key-value pair)을 저장하는 자료구조로, 키(key)를 통해 값(value)에 빠르게 접근할 수 있다.

예를 들어, 학번과 학생 이름을 저장할 때 key는 학번, value는 학생 이름으로 설정해보자.

HashMap<Integer, String> studentMap = new HashMap<>();
studentMap.put(2001206, "이두유");  // key: 2001206, value: "이두유"

하나의 key는 오직 하나의 value랑만 연결될 수 있다.

중복된 키는 허용되지 않지만 값은 중복될 수 있다.

HashSet

HashSet은 고유한 값만 저장하는 집합(Set) 자료구조이다.

HashSet은 내부적으로 HashMap을 활용하여 구현되고, HashMap의 키(key)를 사용하여 값을 저장하고, 값(value)에는 더미 값을 넣는다.

HashSet의 요소들은 HashMap의 키 부분에 저장되며, 값은 무시된다. 이를 통해 객체 그 자체가 고유하게 저장되는 효과를 얻는다.

HashSet<Integer> studentIds = new HashSet<>();
studentIds.add(2001206);  // key 부분에 데이터가 저장

HashSet은 Set 인터페이스의 구현체로, 중복되지 않는 요소를 저장하며, 순서를 보장하지 않는다.

SortedMap

연예 대상에서 한 번이라도 대상을 받은 예능인의 이름과 각각 몇 번을 받았는지 저장하시오. -> HashMap을 사용하여 이름과 횟수를 저장

연예 대상에서 한 번이라도 대상을 받은 예능인의 이름과 각각 몇 번을 받았는지 이름순으로 정렬하여 저장하시오. -> SortedMap

SortedMap은 key, value를 key에 대하여 정렬하여 저장하는 Map이다.

• 삽입, 삭제, 검색이 HashMap이 SortedMap보다 빠르다.

  • 즉, 정렬하지 않아도 되면 HashMap 사용, 정렬이 필요하다면 SortedMap 사용

• Map에서 Key는 항상 unique함을 가진다.

• ConcurrentSkipListMap

• TreeMap

추가

List의 크기가 n이라면 contains(item) : worst case : O(n)

Set은 크기와 상관없이 case(worst case, best case) 와도 상관없이 O(1)

HashMap: 키-값 쌍을 저장하며, 키를 통해 값에 빠르게 접근할 수 있다. 키는 중복이 불가능하고, 값은 중복이 가능하다.

HashSet: HashMap의 키 부분을 활용해, 고유한 값들을 저장하는 집합이다.

즉, 저장되는 데이터의 순서를 보장해야 된다면 List를 사용하면 되지만 탐색이 잦다면 Set을 사용하는 게 좋다.