[Kotlin] 컬렉션(Collections)

Kotlin Collections

코틀린 표준 라이브러리는 컬렉션을 관리하기 위한 기능을 제공한다. 코틀린의 컬렉션은 크게 가변 컬렉션인 mutable과 불변 컬렉션인 immutable로 나뉜다. 여기서 가변 컬렉션이라고 var를 사용하는 것은 아니다. var는 객체의 참조(주소)가 가변이라는 것이다. 컬렉션에서 가변, 불변은 요소(elements)를 추가/삽입/변경이 가능하는지를 의미한다.

 

종류

1. List

리스트는 순서가 있는 컬렉션이다. 자료구조에서 학습한 연결리스트와 같다.

var list = listOf(100,101,102)
var mlist = mutableListOf<Int>()
mlist.add(100)
mlist.add(101)
...

자매품으로 ArrayList도 존재한다.

var list = ArrayList<Int>()
list.add(100)
list.add(101)
...

 

시간 복잡도는 다음과 같다.

	Add	Remove	Get	Contains
List	O(1)	O(1) or O(n)	O(n)	O(n)
ArrayList	O(1)	O(n)	O(1)	O(n)

(위에서 List의 Remove 시간복잡도 O(1)은 삭제할 엘리먼트의 레퍼런스를 알고 있다고 가정한 경우이다. 삭제 대상 탐색이 필요할 경우 O(n))

요소 변경이 빈번할 경우 List, 조회가 빈번할 경우 ArrayList를 활용하는게 좋은 선택이다.

 

 

2. Map

Map은 <key,value>로 객체를 관리하는 컬렉션이다. 특징으로는 순서가 없이 저장되지만 삽입/삭제/조회가 빠르다

var map = mapOf("key1" to 101, "key2" to 102, "key3" to 103)
println(map["key1"])
println(map["key2"])
println(map["key3"])

var mMap = mutableMapOf<String,Any?>()
mMap.put("key1",100)
mMap.put("key2","KONG")
mMap.put("key3",102)

//.set(key,value):키에 대응하는 값 변경
mMap.set("key3",111)

//.remove(key): 객체 삭제
mMap.remove("key3")

//.getOrDefault(key, defaultValue)
mMap.getOrDefault("key4", 200) //200

	put	remove	get	next
HashMap	O(1)	O(1)	O(1)	O(h/n)

내부적으로 해시 테이블을 사용한다. h는 해시의 버킷 수를 의미하고, n은 해시 테이블을 사용하는 엘리먼트의 개수이다. 엘리먼트가 줄어들면 해시버킷이 비어있을 가능성이 줄어들어 O(1)에 근접한다.

 

 

3. Set

Set은 중복되지 않는 객체를 관리하는 컬렉션이다. 또한, 순서를 보장하지 않는다.

var set = setOf(100,200,300,400)

var iterator = set.interator()

while(iterator.hasNext())
	print("${iterator.next()}")
    
var mSet = mutableSetOf<Int>()
mSet.add(10)
mSet.add(20)
mSet.add(30)
mSet.remove(20)
print(mSet) //{10,30}
mSet.contains(10) //true

 

	add	contains	next
HashMap	O(1)	O(1)	O(h/n)

내부적으로 해시 테이블을 사용한다는 점에서 map과 동일하여 같은 시간 복잡도를 갖는다.

 

4. Stack

코틀린 표준 라이브러리에서는 Stack이 존재하지 않는다. 따라서, Stack를 사용하는 방법은 두 가지이다.

 

방법1. ArrayList를 Stack으로 활용

var stack = arrayListOf<Int>()

stack.add(10)
stack.add(20)
stack.add(30)

stack.removeAt(stack.size-1)

print(stack[stack.size-1])

print(stack.isEmpty())

print(stack.size)

ArrayList의 삽입은 맨끝(Top)이고, (크기-1)번째 데이터를 삭제하는 행위는 Top의 삭제를 의미한다. 이는 Stack의 LIFO 특성을 만족한다.

 

방법2. Java에 구현되어 있는 Stack 라이브러리 사용하기.

코틀리은 JVM 위에서 작동하는 언어로 Java의 라이브러리를 사용할 수 있다. 

import java.util

var stack = Stack<Int>()

//삽입
stack.push(1)
stack.push(2)
stack.push(3)

//삭제
stack.pop()

//Top 데이터 조회
print(stack.peek())

//size
print(stack.size)

	push	pop	get
Stack	O(1)	O(1)	O(n)

 

 

5. Queue

코틀린 표준 라이브러리에서는 Queue가 존재하지 않는다. 따라서, Queue를 사용하는 방법은 두 가지이다.

 

방법1. ArrayList를 Queue로 활용

var queue = arrayListOf<Int>()

queue.add(10)
queue.add(20)
queue.add(30)

queue.removeAt(0)

ArrayList의 삽입은 맨끝이고, 인덱스 0번째 데이터를 삭제하는 행위는 Queue의 FIFO 특성을 만족한다.

 

방법2. Java에 구현되어 있는 Queue 라이브러리 사용하기.

코틀리은 JVM 위에서 작동하는 언어로 Java의 라이브러리를 사용할 수 있다. 

import java.util

var queue: Queue<Int> = LinkedList<Int>()

//삽입
queue.add(1)
queue.add(2)
queue.add(3)

//삭제
queue.poll()

//맨 앞 데이터 조회
print(queue.peek())

//초기화
queue.clear()

	add, offer	remove, poll	get
Queue	O(1)	O(1)	O(n)