코틀린: 한 걸음 뒤에서 컬렉션의 숲을 바라볼까요?

컬렉션(Collection)에 관한 보충 설명입니다. 자세한 내용은 쉽게 다가가는 최신 프로그래밍: 코틀린 - 5.3 컬렉션을 참고하기 바랍니다. 컬렉션은 여러 개 원소를 갖는 객체 입니다. 우리가 다루는 객체 중 원소를 갖지 않는 객체가 과연 얼마나 될까요? 코틀린 표준 라이브러리는 거의 대부분 컬렉션에 관련된 함수들로 이루어져 있습니다. chunked, windowed, zipWithNext와 같은 함수가 어떤 함수인지 알고 있나요? 이름은 들어봤나요? 여러분이 열심히 고생해서 만든 함수가 코틀린 표준 라이브러리에 있을 가능성은 99%입니다.

컬렉션을 잘 다룬다는 것은 효율적이고 안정적인 응용 프로그램을 만들 수 있다는 뜻이기도 합니다. 여러분, Iterable과 Collection의 관계에 대해 정확히 알고 있나요? 컬렉션이라는 용어가 왜 List, Set, Map을 가리키는지  알고 있나요? 컬렉션을 본격적으로 다루기 전에 여러분이 꼭 알아야 할 내용들을 살펴볼 것입니다. 나무를 보기 전에 컬렉션의 숲(forest)을 먼저 봅시다. 컬렉션에서는 어떤 내용을 꼭 알아야하는가? 이 과정을  개념화(conceptualization)라고 합니다. 이 과정을 거친 다음 표준 라이브러리에서 제공하는 함수들를 살펴보는 게 정석입니다.

■   Iterable과 Collection
Iterable은 최상위 인터페이스(p.289의 <그림 5-1>을 참고하세요)입니다. Collection은 Iterable을 상속받은 하위 인터페이스입니다. Iterable은 자료 구조를 갖지 않으면서 원소 순환이 가능한 기능만을 제공합니다. Iterable에 해당하는 것은 배열과 Sequence가 있습니다(배열도 자료 구조 아닌가요? 맞습니다. 다만, 코틀린에서는 배열을 Collection과 구분합니다. 컬렉션 객체를 정렬하는 함수는 sorted()이지만, 배열 객체를 정렬하는 함수는 sortedArray()입니다).

반면, Collection에 해당하는 List, Set, Map은 구체적 자료 구조를 갖습니다.

■   불변 Collection과 가변 Collection
컬렉션이라고 했을 때 컬렉션에 속하는 타입은 List, Set, Map 3가지입니다. 여기서 Collection은 불변 컬렉션 타입입니다. 가변 컬렉션 타입은 접두어 Mutable을 앞에 붙인 MutableCollection입니다. 같은 방식으로 가변 컬렉션에 속하는 타입은  MutableList, MutableSet, MutableMap 3가지입니다.

■  컬렉션: 리스트
리스트는 원소들의 순서가 정해져 있기 때문에 인덱싱(indexing)을 통해 원소를 참조할 수 있습니다. 불변 리스트는 고정된 크기(=원소 갯수)를 갖는 배열로 구현됩니다. 반면, 가변 리스트는 ArrayList 또는 LinkedList 중 하나로 구현할 수 있습니다. ArrayList() 또는 LinkedList() 처럼 생성자를 사용해 해당 자료 구조를 갖는 리스트 객체를 생성할 수 있습니다. 표준 함수 arrayListOf()를 사용하면, 원소를 초기화할 수 있습니다(배열 객체를 생성하는 방식과 비슷하다는 점 눈치챘나요?). 이렇게 생성한 리스트 객체(arList2)도 ArrayList로 구현된 가변 리스트 객체입니다. 

잠깐! 컬렉션 타입 객체를 선언할 때는 구체적 타입을 명시하는 각 괄호(<>, angle bracket)를 사용합니다(자세한 내용은 5.2 제네릭을 참고하기 바랍니다).

import java.util.LinkedList

fun main() {
    val llist: LinkedList<String> = LinkedList<String>()

    val immutableList: List<Int> = listOf(1, 2, 3)  // 불변 리스트
    // 가변 리스트 - 생성자 사용
    val arList: ArrayList<String> = ArrayList<String>() 
    // 가변 리스트 - 표준 함수 사용(원소 초기화)
    val arList2: ArrayList<String> = arrayListOf("aaa", "bbb", "ccc") 
}

ArrayList와 LinkedList는 어떤 차이점이 있을까요? ArrayList는 인덱싱을 사용해 원소를 빨리 참조할 수 있지만(Big O 표현식으로 나타내면 원소 탐색에 걸리는 시간 복잡도는 O(1)입니다), 중간에 원소를 삽입하는 게 쉽지 않습니다(우선 배열 크기부터 늘린 다음, 삽입할 위치를 확보하기 위해 기존 원소들을 쭉~ 뒤로 밀어야 하겠죠. 물론 ArrayList 의 맨 뒤에 원소를 삽입하는 건 그리 어렵진 않겠지만).

반면 LinkedList는 ArrayList와 정반대입니다. LinkedList는 ArrayList와 반대로 중간에 원소를 삽입하는 건 유리하지만, 원소를 참조하는 데는 O(n)(n은 원소 갯수)의 시간 복잡도가 필요합니다 (LinkedList에 저장된 원소를 찾으려면 연결 리스트의 첫 번째 원소부터 마지막 원소까지 링크를 따라가며 찾아가야 하니까요).

■  컬렉션: Set과 Map
Set과 Map은 다른 것처럼 보이지만 비슷한 점이 아주 많습니다. Set은 집합이기 때문에 중복 원소를 갖지 않습니다. Map은 <key, value> 쌍을 원소로 갖지만, key는 중복될 수 없다는 점에서 Set의 특징을 갖습니다.  그래서, Set과 Map을 구현하는 자료 구조도 HashXxx, LinkedHashXxx, TreeXxx 으로 같습니다. Xxx 는 Set 또는 Map 입니다.

Set과 Map을 구현하는 자료 구조에서 해시(hash)란 단어가 자주 등장하죠. 해시에 대해 알아볼까요. 영어 단어는 a부터 z까지 모두 26개의 알파벳을 기준으로 나눌 수 있죠(영어 사전이 이렇게 만든 거잖아요). 이때 알파벳을 해시 키(key)라고 부릅니다. 알파벳 'a'에 속한 단어들이 엄청 많겠죠. 그럼 이렇게 많은 원소들은 어떻게 처리할까요? 같은 해시 키를 갖는 단어들을 연결 링크 구조로 표현합니다(사전에서 단어 찾을 때 알파벳으로 먼저 찾고 페이지 넘겨가며 찾는 것과 같습니다) . 해시 키는 해시 테이블에 저장합니다. 영어 단어에 대한 해시 테이블은 모두 26개 행(row)으로 나타낼 수 있겠죠. HashXxx가 지금 설명한 방식대로 구현한 겁니다.

LinkedHashXxx는 HashXxx와 뭐가 다를까요? LinkedHashXxx는 해시 키를 어떤 기준에 맞게 순서대로 해시 테이블에 저장합니다( 해시 키를 구현하는 방식에 따라 불규칙성이 나타나면 이 방식으로 구현하는 것은 비효율적입니다) . 영어 단어에 대한 해시 키는 알파벳 순으로 차례대로 저장할 수 있습니다.

TreeXxx는 이진 트리(binary tree)로 구현합니다. 표준 함수 sortedXxxOf()를 사용해 가변 Set 객체 또는 가변 Map 객체를  생성하면, 내부적으로는 TreeXxx 구조로 구현합니다. 왜 그럴까요? 트리를 구성할 때 특정 기준(=정렬 기준)에 따라 자식 노드를 배치할 수 있기 때문입니다.

■  불변 컬렉션과 가변 컬렉션 생성
접두사 Mutable이 있는지를 보고  불변 컬렉션과 가변 컬렉션을 구분할 수 있습니다. 그러나, 더 중요한 것은 불변 컬렉션 객체와 가변 컬렉션 객체를 생성하는 방식을 이해하는 것입니다.

불변 컬렉션 타입 객체는 listOf(), setOf(), mapOf() 처럼 표준 함수 xxxOf()를 사용해 객체를 생성합니다. buildXxx() 또는 emptyXxx()를 사용해 불변 컬렉션 타입 객체를 생성할 수도 있습니다(p.291~p.293을 참고하세요).

가변 컬렉션 타입 객체는 mutableListOf(), mutableSetOf(), mutableMapOf() 처럼 표준 함수 mutableXxxOf()를 사용해 가변 컬렉션 타입 객체를 생성합니다. 가변 리스트 객체는 생성자(ArrayList()) 또는 표준 함수 arrayListOf()를 사용해 객체를 생성할 수 있습니다. Set과 Map 타입은 hashXxxOf(), linkedXxxOf(), sortedXxxOf()를 사용해 가변 Set 또는 가변 Map 객체를 생성할 수 있습니다. Xxx 대신 Set 또는 Map을 사용하면 됩니다. linkedXxxOf()는 연결 링크 방식의 해시 테이블을, sortedXxxOf()는 이진 트리 구조를 사용합니다.

■  공변성(covariance)
불변 컬렉션과 가변 컬렉션을 사용할 때 주의할 점은 공변성(5.2.4 클래스 상속 관계일 때 타입 변환을 참고하세요)입니다. 불변 리스트 타입과 불변 컬렉션 타입 사이에는 공변성(타입 호환 관계)이 성립합니다.

fun main() {
    val myList = listOf("aaa", "bbb", "ccc")
    showElements(myList)

    val mySet = setOf("A", "B", "C")
    showElements(mySet)
}

fun showElements(c: Collection<String>) {
    println(c)
}

가변 리스트 타입과 불변 컬렉션 타입 사이에도 공변성이 성립합니다.

fun main() {
    val myList = arrayListOf("aaa", "bbb", "ccc")
    showElements(myList)
}

fun showElements(c: Collection<Any>) {
    println(c)
}

 

그러나 불변 리스트 타입과 가변 컬렉션 타입 사이에는 공변성이 성립하지 않습니다. 요약하면 불변 컬렉션 타입은 공변성이 성립하지만, 가변 컬렉션 타입은 공변성이 성립하지 않습니다.

fun main() {
    val myList = listOf("aaa", "bbb", "ccc")
    showElements(myList)
}

fun showElements(c: MutableCollection<Any>) {
    println(c)
}

■  마무리 퀴즈(wrap-up quiz)
가변 리스트 타입과 가변 컬렉션 타입 사이에는 공변성이 성립할까요?

fun main() {
    val myList = mutableListOf("aaa", "bbb", "ccc")
    showElements(myList)
}

fun showElements(c: MutableCollection<String>) {
    println(c)
}