[자료구조] List vs Set 정의 & 차이점

Ordered collection vs Unordered collection

---

우선 List와 Set의 공통점으로는 "같은 종류(타입)의 데이터를 저장" 한다는 특징을 갖는다.

 

이에 반해 차이점은 다음과 같다.

 

List

• 입력 순서를 유지하며, 데이터의 중복을 허용
• 인덱스를 통해 저장 데이터에 접근이 가능

 

Set

• 입력 순서를 유지하지 않으며, 데이터의 중복 허용하지 않음
• 데이터에 null 입력 가능하나, 한 번만 저장하고 중복 저장을 허용하지 않음
• 인덱스가 따로 존재하지 않기 때문에 Iterator를 사용하여 조회

 

 

위와 같이 너무 명확한 차이를 갖는 두 ADT를 살펴본 이유는 무엇일까? 단순히 면접 대비를 위해 저 짧은 개념들을 살펴볼 수도 있지만 최종적으로는 실무에서 상황에 맞는 ADT를 이용하기 위한 목적이 크다고 생각된다.

 

예시를 통해 한번 살펴보자.

 

만약 "월드컵에서 한번이라도 골을 넣은 선수를 저장" 해야하고 이때 "이름"은 모두 다르다는 예시가 있다고 하자.

이때 문제 자체에서 순서를 고려하지 않았고 중복으로 이름을 넣을 필요가 없기 때문에 그러므로 이때는 Set을 이용하는 쪽으로 문제 접근을 할 수 있겠다.

 

또 다른 예시로 "2000년도 부터 2019년도 까지 MBC에서 연예대상을 수상한 예능인을 순서대로 저장" 한다는 예시가 있다면 이때는 "순서" 라고 명확하게 문제에서 표시를 해줬기 때문에 List를 고려해볼 수 있을 것이다.

 

물론 처음엔 ADT 관점에서 문제를 접근하였겠지만 문제 상황마다 적절한 자료구조(구현체)를 선택하는 것은 개발자의 몫일 것이다.

 

 

 

List, Set 어떤 것을 쓰는 것이 유리한가

---

위에서 "월드컵에서 한번이라도 골을 넣은 선수를 저장" 이라는 예시를 들어 문제 상황에 따른 List, Set의 선택에 대해 짧게 설명을 했었다.

 

하지만 이때 List를 사용할 수도 있지 않을까? 라는 의문점이 들 수도 있어서 추가적으로 정리를 하고자 한다.

 

예를 들어 축구 선수로 메시, 호나우두, 지단...등이 있다고 하자. 이때 굳이 중복으로 선수를 저장할 필요는 없으므로 "중복 검사" 과정이 필수적으로 포함된다.

 

그래서 선수들을 ArrayList or LinkedList에 저장을 한 뒤 동일한 이름의 선수가 들어왔을 시 중복 검사를 수행한다면 List의 경우 WorstCase일 때 O(n)의 시간 복잡도가 들어갈 것이다. 왜냐하면 List에서 데이터를 탐색하기 위해서는 전체 데이터를 순회해야하기 때문이다.

 

하지만 Set의 구현체인 HashSet은 탐색에 있어서 상수시간 O(1)을 보장하도록 구현되어 있기 때문에 "중복 검사" + 시간복잡도 측면에서 이점이 있다.

 

해당 관점에서 직접 테스트 해보자면 다음과 같다.

 

속도 비교

10000000의 숫자를 ArrayList, LinkedList, HashSet에 각각 저장했고, 특정 위치에 저장할 때 걸리는 시간과 5000000 값이 존재하는지 확인하는데 걸리는 시간을 측정해봤다.

int size = 10000000;
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
Set<Integer> hashSet = new HashSet<>();

for (int i = 0; i <= size; i++) {
    arrayList.add(i);
    linkedList.add(i);
    hashSet.add(i);
}

System.out.println("1. add() test : ArrayList vs LinkedList");
// ArrayList add test
Instant start = Instant.now();
arrayList.add(3000, -1);
Instant end = Instant.now();
long time = Duration.between(start, end).toMillis();
System.out.println("ArrayList add(3000, -1) time : " + time);

// LinkedList add test
start = Instant.now();
linkedList.add(3000, -1);
end = Instant.now();
time = Duration.between(start, end).toMillis();
System.out.println("LinkedList add(3000, -1) time : " + time);

System.out.println();
System.out.println("2. contains() test : ArrayList vs LinkedList vs HashSet");
int targetNumber = 5000000;

// ArrayList contains test
start = Instant.now();
arrayList.contains(targetNumber);
end = Instant.now();
time = Duration.between(start, end).toMillis();
System.out.println("ArrayList search time : " + time);

// linkedList contains test
start = Instant.now();
linkedList.contains(targetNumber);
end = Instant.now();
time = Duration.between(start, end).toMillis();
System.out.println("linkedList search time : " + time);

// HashSet contains test
start = Instant.now();
hashSet.contains(targetNumber);
end = Instant.now();
time = Duration.between(start, end).toMillis();
System.out.println("HashSet search time : " + time);

1. add() test : ArrayList vs LinkedList
ArrayList add(3000, -1) time : 5
LinkedList add(3000, -1) time : 0

2. contains() test : ArrayList vs LinkedList vs HashSet
ArrayList search time : 20
linkedList search time : 54
HashSet search time : 0

 

특징

왜 위와 같은 결과가 나왔을까?

• ArrayList는 중복을 허용하고 순서를 보장하여 데이터를 저장하고 배열과 같이 인덱스로 내부의 객체를 관리한다. 따라서 특정 위치의 데이터에 접근하는 속도가 빠르다. 하지만, 특정 위치(i)에 삽입을 할 때는 i + 1 번 데이터부터 끝까지의 데이터를 한 칸씩 이동해야 하기 때문에 느리고, 삭제 또한 마찬가지이다. 또한, contains 메소드 실행 시 처음 순차적으로 데이터 탐색을 진행하면서 값을 찾기 때문에 시간이 오래 걸린다.
  
  
• LinkedList는 노드 간에 연결을 통해서 내부 객체를 관리한다. 삽입이나 삭제 시, 해당 노드의 위치에 연결된 정보만 바꿔주면 되기 때문에 속도가 빠르다. 하지만, 데이터에 접근할 때는 맨 앞의 노드부터 순차적으로 접근해야하기 때문에 느리다.

contains() 속도가 ArrayList가 LinkedList보다 빠른 것은 ArrayList가 내부적으로 배열을 사용하고 인덱스로 접근하기 때문인 것 같다.

• HashSet은 비선형 구조로 순서가 없고 인덱스도 존재하지 않는다. 또한, 중복을 자동으로 제거해준다. 데이터가 있는지 확인할 때는 모든 데이터를 찾아보는 것이 아니라 데이터를 key로 순서와 상관없이 바로 확인한다. 따라서 List보다 속도가 훨씬 빠르다는 것을 알 수 있다.

 

HashSet은 어떻게 중복 값을 걸러내는가?

• HashSet은 내부적으로 HashMap을 호출해서 구현한다.
• 저장하기 전에 먼저 hashCode() 메소드를 호출해서 같은 해시 코드가 있는지 확인을 한다. 만약 같은 해시 코드가 있다면, equals() 메소드로 중복 여부를 검사한다.

 

HashSet에 대한 자세한 내용은 아래 포스팅을 참고

[자료구조] HashSet이란 무엇인가?

 

	ArrayList	LinkedList	HashSet
add()	O(1)	O(1)	O(1)
add(index, value)	O(N)	O(1)
remove()	O(N)	O(1)	O(1)
contains()	O(N)	O(N)	O(1)
get()	O(1)	O(N)

 

언제 Set 또는 List를 사용해야 할까?

• 저장되는 데이터의 순서를 보장해야한다면 List를 사용
• contains(element)는 Collection에 데이터가 존재하는지 확인하는 메소드다. List의 contains 실행 속도는 O(n)이지만, Set는 O(1)으로 매우 빠르다. 탐색이 잦다면 Set를 고려해볼 수 있다.
• 데이터가 많지 않다면 성능보다, 구조가 간단한 List를 고려해볼 수 있다.
• 중복을 허용하지 않는 Collection이 필요하다면 Set를 고려해볼 수 있다.
• 하지만 List를 사용하거나 Set을 사용하거나 동작에 차이가 없는 상황이라면, HashSet을 사용하는 것이 훨씬 유리하다.