List & Set

List

1. 같은 종류의 아이템을 저장한다.
2. 순서를 보장한다.
3. 중복값을 허용한다.

List 구현체(DS)

ArrayList
LinkedList

Set

1. 같은 종류의 아이템을 저장한다.
2. 순서를 보장하지 않는다.
3. 중복값을 허용하지 않는다.

Set 구현체(DS)

SortedSet : 순서를 보장하는 Set 구현
HashSet : Hash 형태로 Set 구현

Set은 List에 비해 속도, 성능이 우수하다.

Example

1. 모든 선수들의 이름이 다르고, 한번이라도 골을 넣은 선수를 저장하기 위한 ADT

Set : 한번이라도 골을 넣은 경우 해당 선수의 이름이 한개만 존재하면 되기 때문에, 중복이 되어서는 안된다. 또한, 순서를 보장할 이유가 존재하지 않는다.

2. 2000년 ~ 2019년까지 연예대상을 받은 연예인을 순서대로 저장하기 위한 ADT

List : 시간의 흐름에 따라 대상을 받은 연예인을 순서대로 저장해야 하기 때문에 순서를 보장하는 List를 사용한다. 또한, 2000년에 대상을 받은 연예인이 20년동안 대상을 다시 받을 수 있기 때문에, 중복값을 허용해야한다.

Set대신 List사용

중복을 허용하지 않는 List를 구현하려면 현재 List에 내가 추가하려고 하는 값이 존재하는지 탐색 후 존재하지 않으면 추가해야한다. 즉, 탐색하는 추가 시간이 소모되는 셈이다.

=> 인덱스의 위치를 알 수 없기 때문에 선형탐색을 하고 시간이 일정하지 않다. O(N)

Set은 데이터를 탐색하는데 Size와 상관없이 소모되는 시간이 일정하다. O(1)

=> 중복을 방지하고 성능이 좋고 소모되는 시간이 짧다.

출처 : 쉬운코드 유튜브
이미지 : https://techdifferences.com