List와 Set - 차이점

지난 라이브 코딩 면접을 진행하며 필자는 아무 생각 없이 가장 익숙한 List 자료구조를 사용했다. 그러자 면접관님들이 Set을 사용하지 않은 이유와 그 둘의 차이점 등을 물으셨다. 자료구조와 그들의 특성에 대해 깊히 공부하지 않은 나는 정확한 답변을 하지 못하였고, 다양한 자료구조들의 특성을 이해하고 적절한 자료구조를 사용하는 것에 대한 중요성을 느껴 이 글을 작성하게 되었다

List와 Set이란

List: 순서가 보장되고 중복이 허용되는 자료구조

Set: 순서가 보장되지 않으며 중복이 허용되지 않는 자료구조

차이점 1: 중복 허용

위에서 나왔듯이 List는 중복을 허용하고 Set은 중복을 허용하지 않습니다.

차이점 2: 인덱스

List는 순서를 보장하는 자료구조이기 때문에 add로 element를 추가하면 그 순서가 보장됩니다. 따라서 index를 사용하여 특정 element를 가져올 수 있습니다.

Set은 순서를 보장하지 않기 때면에 add로 element를 추가하더라도 그 위치를 지정할 수 없습니다 (순서는 set 구현에 따라 달라짐). 따라서 index를 사용하는 function을 사용할 수 없습니다.

차이점 3: 검색 속도 (e.g. contains)

List의 가장 자주 쓰이는 구현인 ArrayList와 Set의 HashSet를 사용하여 설명하겠습니다.

ArrayList는 위에서 말했듯이 순서가 보장되는 자료구조이다. 따라서 검색을할 때 순차적으로 elements들을 순회합니다. 따라서 시간복잡도는 O(n)이 나옵니다.

Hash를 사용하는 HashSet은 이름 그대로 hash를 이용하는 것입니다. Hash에 관해서는 추가 적으로 포스팅할 예정입니다. 이 포스트에서는 내부적으로 배열을 사용하는 방법 정도로만 이해하고 넘어가면 됩니다. 데이터의 길이가 가변적인 List와 같은 자료구조와 달리 데이터의 길이가 고정되어 있는 배열(array)는 더 빠른 검색속도를 보입니다. 따라서 이러한 Hash를 사용하는 HashSet은 검색에서 O(1)의 시간복잡도를 보입니다.

결론) 언제 써야할까?

List와 Set 둘 중 무엇을 사용해도 상관이 없다면, 즉

• 중복된 데이터를 저장할 필요가 없고
• 데이터의 위치(index)를 이용하는 동작을하지 않는다면

Set, 그리고 그 중에서도 HashSet을 사용하는 것이 훨씬 빠른 동작 속도를 보입니다.

필자는 중복된 데이터가 없고 contains 함수만 사용하면 되는 데이터를 저장하는데 ArrayList를 사용했었기에 그에 관련한 꼬리 질문을 많이 받았습니다.. 문제를 풀 때 시간 복잡도를 더 고려하고 문제를 푸는 연습을 하는게 좋을 것 같습니다.