📖 Collection

여러 개의 데이터를 하나의 그룹으로 다루기 위한 도구 모음

Collection 주요 인터페이스

List : 순서가 있으며 데이터 중복 허용 O

Set : 순서가 없으며 데이터 중복 허용 X

Map : Map & Value 구조, Key는 중복 허용 X, Value는 중복 허용 O

---

📝 List

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

List 인터페이스의 주요 구현체

• ArrayList : 단방향 포인터 구조. 조회가 빠름
• LinkedList : 양방향 포인터 구조. 삽입, 삭제가 빠름

🤔 사용 예

순서가 중요하거나 동일한 요소를 여러 번 저장해야 할 때 사용
ex) 쇼핑 목록이나 작업 목록 같은 경우

val shoppingList = mutableListOf("Milk", "Eggs", "Flour", "Eggs")
println(shoppingList) 

>>["Milk", "Eggs", "Flour", "Eggs"]

---

📝 Set

• 데이터의 중복을 허용하지 않고 순서를 보장하지 않음
• 인덱스가 따로 존재하지 않기 때문에 Iterator를 사용하여 조회

🤔 사용 예

주로 어떤 컬렉션에서 중복을 제거하고자 할 때, 또는 어떤 항목의 존재 유무만 중요할 때
ex) 어떤 행사에 참석하는 사람들의 이름 목록에서 중복을 제거하고 싶을 때

val attendees = setOf("Alice", "Bob", "Charlie", "Dave", "Alice", "Bob")
println(attendees) 

>>["Alice", "Bob", "Charlie", "Dave"]

---

📝 Map

• Key & Value 구조
• Key는 순서가 없으며 중복을 허용하지 않음. Value는 중복을 허용.
• 인덱스가 따로 존재하지 않기 때문에 Iterator를 사용하여 조회

🤔 사용 예

데이터가 키-값 쌍(key-value pairs)의 형태로 존재하고, 키를 통해 빠르게 값을 검색하고 관리해야 할 때

fun main() {
    // 쇼핑 리스트 생성
    val shoppingList = listOf("Milk", "Eggs", "Bread")

    // 쇼핑 리스트 출력
    println("Shopping List: $shoppingList")

    // 리스트에서 특정 아이템 찾기
    if ("Eggs" in shoppingList) {
        println("Don't forget to buy Eggs!")
    }
}

---

📝 "시간복잡도"면에서 List와 Set 비교

List

List에서 in 연산자를 사용하면 사실 상 for문을 한번 도는 것이기 때문에 선형 시간인 O(n)의 시간 복잡도를 가진다.
그래서 잘못 사용하면 TimeOut이 발생할 수 있다.
대신 Set으로 바꾸고 in연산자를 사용하면 시간이 줄어든다.

아래는 1부터 10000000까지의 범위를 가지는 리스트인 list 변수에서 in 연산자를 사용해 10000000을 찾을 때 걸리는 시간을 구하는 코드이다.

fun list(){
    val list = (1..10000000).toList()

    val startTime = System.nanoTime()
    val existList = 10000000 in list
    val endTime = System.nanoTime()

    val duration = (endTime - startTime)

    println("List Execution time: $duration ms")
}

>> List Execution time: 20196400 ms

Set

Set의 시간복잡도는 O(1)이다.
Set은 해시 함수와 해시 테이블을 이용해서 만든 자료구조이므로 해시 함수 연산 시간만큼 걸리므로, 데이터가 커지더라도 일정한 속도가 보장된다.
아래는 Set을 사용한 코드이다.

fun set(){
    val set = (1..10000000).toSet()

    val startTime = System.nanoTime()
    val existSet = 10000000 in set
    val endTime = System.nanoTime()

    val duration = (endTime - startTime)

    println("Set Execution time: $duration ms")
}

>> Set Execution time: 29500 ms

Set을 사용하면 시간이 적게 걸리는 걸 확인할 수 있다.
그래서 무언가 값이 있는지 확인하려면 set() 으로 변경한다음 in 연산을 사용하는 것이 좋다.

📌 정리

List에서 in 연산은 O(n)으로 선형시간으로 탐색한다.
반면에 set이나 dict는 O(1)로 상수시간으로 탐색한다.
따라서 많은 양의 데이터에서 in으로 값을 검색하고자 할 때는 set으로 변환하면 더 빠르다.