Kotlin 자료구조

Array(배열)

특징 :
1. Kotlin 컴파일러는 Array<'T'>을 Java의 배열로 컴파일한다.
2. 같은 타입의 정해진 크기의 연속된 요소로 이루어진 배열이다.
3. 생성된 순간 Size는 고정되며 Element 삭제나 추가를 할 수 없다.
4. Element들은 Mutable하다.
5. 인덱스로 검색이 가능하다.
6. Primitive 타입에 최적화되었다.

ex)

    val array = arrayOf(1, 2, 3)
    val array2 = Array(5) { 0 }
    val array3 = intArrayOf(0, 1, 2)
    val array4 = IntArray(3) { i -> i }

List(리스트)

특징 :
1. 읽기만 가능하다.
2. 불연속적인 메모리 공간을 점유해 메모리 관리에 용이하다.
3. 배열처럼 index를 통한 접근이 가능하다.

    val list = listOf<String>("a", "b", "c")

ArrayList(가변 리스트)

특징 :
1. List를 기반으로 한다.
2. 배열을 기반으로 데이터를 관리하지만, 배열과 달리 크기가 고정되어 있지 않다.
3. mutableListOf()를 사용해서 생성한 List가 ArrayList이다.(=MutableList())
4. 인덱스를 통한 데이터 접근은 O(1)의 시간복잡도이다.
5. 데이터 추가 시에는 ArrayList가 갖고있는 배열을 더 큰 공간의 배열에 옮겨야 하기에 원래의 데이터들을 삭제하고 새로운 곳에 복사를 한후 데이터를 추가할 수 있어 최대 O(N)의 시간복잡도를 갖는다.
6. 데이터 삭제, 검색하는 경우 O(N)의 시간복잡도를 갖는다.

    val mutableList = mutableListOf(1, 2, 3)
    println(mutableList[1])
    mutableList.add(4)
    mutableList.remove(3)
    
    val arrayList = arrayListOf("a", "b", "c")
    println(arrayList[2])
    arrayList.add("d")
    arrayList.remove("a")
    arrayList.contains("d")

LinkedList

특징 :
1. 보관할 데이터와 다음 데이터의 주소를 갖는 Node들을 연결하여 데이터를 저장한다.(양방향 링크드 리스트)
2. 데이터에 접근, 검색하는 경우 O(N)의 시간복잡도를 갖는다.
3. 데이터를 추가, 삭제하는 경우는 Head, Tail의 경우 O(1)의 시간복잡도를 가지나 특정 위치인 경우에는 O(N)의 시간복잡도를 가진다.

    val linkedList = LinkedList<Int>()
    linkedList.add(3)
    linkedList.addFirst(1)
    linkedList.addLast(2)
    linkedList.remove()//맨 앞의 값 삭제
    linkedList.removeLast()//마지막 값 삭제

ArrayList vs LinkedList

If) Index를 통해 접근할 때는
-> ArrayList가 더 좋은 성능
If) Head, Tail 위치에 데이터를 추가 혹은 삭제를 할 때는
-> LinkedList가 더 좋은 성능

Set

특징 :
1. 동일한 데이터를 허용하지 않는 Collection이다.
2. 저장되는 데이터들의 순서를 보장하지 않는다.
3. Mutable/Immutable 둘다 지원

    val set = setOf(1, 2, 3)
    println(set.contains(1))
    for (value in set)
        println(value)
    
    val mutableSet = mutableSetOf("a", "b", "c")
    mutableSet.add("d")
    mutableSet.remove("a")

LinkedHashSet

특징:
1. HashSet과 동일한 구조를 가지며 삽입된 순서대로 데이터를 출력합니다.
2. Kotlin의 Sets.kt의 setOf()에서는 Array 형태로 받는 elements들을 toSet이라는 Extension function을 통해 LinkedHashSet 구조로 저장시켜주고 있다.

val set = setOf<Int>(1, 2, 3, 4)
println(set) //[1, 2, 3, 4]

//Sets.kt
public fun <T> setOf(vararg elements: T): Set<T> =
	if (elements.size > 0) elements.toSet() else emptySet()

//_Arrays.kt
public fun <T> Array<out T>.toSet(): Set<T> {
    return when (size) {
        0 -> emptySet()
        1 -> setOf(this[0])
        else -> toCollection(LinkedHashSet<T>(mapCapacity(size)))
    }
}

Map

특징 :
1. Key, Value를 짝지어 저장하는 Collection이다.
2. Key는 유일하고 Value는 동일한 값을 허용합니다.
3. Pair(A, B)를 사용해 간단이 표현 가능하다.

    val map = mapOf<Int, String>(Pair(1, "a"), 2 to "b")
    map[1]

    val mutableMap = mutableMapOf<String, Int>(Pair("a", 1), "b" to 2)
    mutableMap["c"] = 45
    mutableMap.remove("a")
    mutableMap.replace("b", 4)