[Java] List와 Set의 차이, 그러면 Set은 어떻게 구현할까요?

공부를 하기 전에 제가 아는 것 부터 적어보자면..

일단 List는 순서가 있고 중복이 존재할 수 있구요

삽입 삭제에 걸리는 시간이 O(n)

반대로 Set은 중복이 없고 순서가 존재하지 않구요

삽입 삭제에 걸리는 시간이 O(1)입니다.

 

...네

공부해서 글을 작성해보겠습니다.

Java의 Collection

• Collection은 '요소'라고 알려진 어떠한 객체의 그룹을 나타냅니다.
• 일부 컬렉션은 중복 요소를 허용하고 다른 일부는 그렇지 않습니다. 일부는 순서가 있고 다른 일부는 순서가 없습니다.
• JDK는 Set과 List와 같은 더 구체적인 하위 인터페이스의 구현을 제공합니다.

List

• List는 Collection의 하위 인터페이스로, 순서가 있는 컬렉션입니다.
• 중복 값을 저장할 수 있는 객체들의 순서가 있는 Collection입니다.
• List는 삽입 순서를 유지하며, 요소의 위치 기반 접근과 삽입을 허용합니다.

Set

• Collection의 하위 인터페이스로, 중복 값이 저장되지 않는 객체들의 순서가 없는 컬렉션입니다.
• 이는 수학적 집합을 구현하는 인터페이스입니다.
• 이 인터페이스는 Collection 인터페이스로부터 상속받은 메서드들을 포함하고 있으며, 중복 요소의 삽입을 제한하는 기능을 추가합니다.

시간 복잡도 차이

List와 Set 인터페이스는 구체적인 구현체에 따라 시간 복잡도가 달라집니다.

ArrayList (List 구현체)

• get(int index), set(int index, E element): O(1)
• add(E element), remove(int index): 평균적으로 O(n)

LinkedList (List 구현체)

• get(int index), set(int index, E element): O(n)
• add(E element), remove(int index): 리스트의 양 끝에서는 O(1), 그 외의 경우에는 O(n)

HashSet (Set 구현체)

• add(E element), remove(Object o), contains(Object o): 평균적으로 O(1)

TreeSet (Set 구현체)

• add(E element), remove(Object o), contains(Object o): O(log n) 

그렇다면, Set은 어떻게 구현하나요?

Set은 Hash table로 구현합니다. 왜냐하면 Hash table이 Set과 같은 특성을 가지기 때문입니다.

Hash table은 Key가 중복이 될 수 없고, 데이터도 랜덤하게 저장됩니다.

따라서 Set을 구현할 때에는 Hash table의 Key에 데이터를 저장하는 방식으로 구현할 수 있습니다.

List, Set, 각각 언제 사용하는게 좋을까요?

List는 순서가 중요하거나 같은 요소를 여러 번 포함해야 하는 경우, 그리고 특정 위치의 요소에 빠르게 접근해야 하는 경우에 적합하며,

Set은 요소의 중복을 허용하지 않아야 하거나, 요소의 삽입이나 삭제, 그리고 특정 요소의 존재 유무 확인 등이 빈번하게 일어나는 경우에 적합합니다.

참고 자료

https://www.youtube.com/watch?v=CMgpTGs_N_w

https://stackoverflow.com/questions/1035008/what-is-the-difference-between-set-and-list

What is the difference between Set and List?

https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html

Collection (Java Platform SE 8 )