시작하기

과거 파이썬을 공부 할 때 자료구조를 파이썬 기반으로 공부를 했었다. 복습하는 차원에서 Kotlin으로 관련 method들을 알아보고, 또 필요한 경우 직접 구현해보며 공부해보자

Array

array는 같은 타입의 변수들로 이루어져 있고, 일반적으론 크기가 정해져있다.

• 접근 O(1) thanks to Random Access
• 검색 O(n)
• 삭제, 추가 O(n)

인덱스로 원소에 빠르게 접근해야 할 때 유용.

use in kotlin

## initialize
val a = arrayOf(1,3,4)
val b = (3..10).toList().toTypedArray() // Array<T> 형태로 변경
val c = intArrayOf(3,4,5)
val d = Array(4) { i -> i*3 } // [0, 3, 6, 9]

## basic operations
a[2] // 4
b.get(1) // 4
c.set(3, 11)
c[3] // 11
a.first()
a.last()
a.lastIndex
a.size

## 원소 추가, 새로운 array를 만들어야함
var e = a.plus(10)

## array slice, 
val d = a.sliceArray(4..5) //[6,6]

Collections

Kotlin에서는 읽기전용 Collection과 변경 가능한 Mutable Collection을 구분하고 있다.
일반적으로 add, addAll, remove, removeAll, retainAll, clear는 Mutable Collection에서 사용할 수 있으며, contains, containsAll, isEmpty, iterator, size 등은 상관없이 사용 가능하다.

List (일반)

중복을 허용하며 순서대로 자료를 보관한다. Kotlin에서는 immutable 하기 때문에 값 추가나 변경은 불가능하다.

• 접근 O(n)
• 검색 O(n)

ArrayList

배열을 기반으로 데이터를 관리하지만, array와 달리 크기가 고정되어 있지 않다.

공식 문서를 보면 RandomAccess가 되는 MutableList이다~ 라는 것을 알 수 있다. index를 통한 접근에 많이 필요할 때 좋다.

in Kotlin

kotlin에서는 mutableListOf()의 기본 구현이 ArrayList이다.

val a = arrayListOf(3,4,5)
a.add(3)
a.remove(4) 

Time Complexity

• 접근 O(1) : array를 기반으로 구성되기에 random access가 가능하다.
• 검색 O(n)
• 삭제 O(n)
• 추가 O(1) or O(n) : array size가 남아있으면 1 아니면 n

LinkedList

LinkedList는 데이터(value)와, 다음 데이터의 주소(next)를 갖는 Node들을 연결하여 데이터를 관리한다. 맨 앞이나 맨 뒤에 데이터를 추가하거나 제거할때 유용하게 사용된다.

in Kotlin

일반적으로 LinkedList를 단방향을 의미하지만 Kotlin에서는 DLL(Double LinkedList)이기 때문에 양방향이다.

val a = LinkedList<Int>()

a.add(3)
a.addFirst(5)
a.addLast(7)
println(a)

time complexity

• 접근 O(n)
• 추가, 삭제 O(1) or O(n) : 맨 앞 or 맨 뒤의 경우 1 아니면 n
• 검색 O(n)

Set

중복을 허용하지 않는 Collection이다. 순서가 없다는 것이 특징이다.

in kotlin

val a = setOf<Int>(3,4,6)
val b = setOf<Int>(6,4,3)

a.contain(3)
b.add(5)

time complexity

HashSet을 통해 구현되어 추가, 삭제, 검색 모두 O(1)이다.

Map

key: value 형태로 저장하는 collection이다. key가 unique 하며, python에서 dictionary를 생각하면 된다.

in kotlin

kotlin에서는

val a = mapOf<String, Int>("1" to 1, "2" to 2, "3" to 3)
val b = mutableMapOf<String ,Int>()
a.get("1")
a["1"]
a.values
a.keys
b["3"] = 6

time complexity

kotlin에서는 mutableMapOf()를 하면 MutableMap은 interface 이기에 HashMap을 통해 구현이 되어 있다. 찾아보는 바에 의하면 HashMap의 storing(저장)과 retrieving(읽기) 모두 O(1)로 보인다.

마무리

간단하게 Array와 Kotlin의 Collection 들을 알아보았다. 가볍게 훑어보았다 정도로 기억해두자.