[Kotlin] Collections 1 — List (ArrayList, LinkedList)

이번 포스트에서는 List의 하위 클래스라면 사용할 수 있는 함수들과, 객체로 만들어 사용할 수 있는 List의 하위 클래스들에 대해 알아볼 것이다.

List에 대해 알아보기 전에, List가 상속받고 있는 Collection에 대한 내용을 잠시 짚고 넘어가자.

Collection interface

Collection은 내가 필요한 자료들을 보관할 수 있게 해주는 interface이다. interface이므로 객체를 생성할 수 없고, Collection interface를 implement한 클래스가 Collection의 함수를 구현하고, 그 클래스의 객체를 통해 Collection의 함수들을 사용할 수 있다. Kotlin에서는 읽기 전용 Collection과 변경 가능 MutableCollection을 구분하고 있다는 사실을 기억하자. ‘E’라고 표시된 타입이 있는데, ‘Generics’라고 불리는 개념과 관련된다. Collection이 담고 있는 자료형이라고 생각하면 된다.

Fig1. Collection의 methods

List interface

List는 데이터 중복을 허용하며, 특정 자료형의 자료들을 순서대로 보관하는 구조이다. List interface는 Collection interface를 상속받는다. Collection interface와 겹치는 메서드는 List interface에서 override된 메서드들이다. 순서대로 보관하기 때문에 index를 통하여 접근이 가능한 interface이다. Kotlin의 List는 마치 배열처럼 ‘[]’기호를 사용하여 index를 통한 접근이 가능하다. 즉, ‘Int타입의 객체들을 보관하는 List타입의 객체 someList’가 있다면 someList.get(0) 대신 someList[0]으로 사용할 수 있고, someList.set(0, 100) 대신 someList[0]=100과 같이 더 간결하고 직관적으로 사용할 수 있다는 뜻이다.

Fig2. List의 methods

Fig2에서 연한 노란색이 읽기 전용인 List의 메서드들이고, 주황색이 변경 가능한 MutableList의 메서드이다. MutableList는 List를 상속받으므로, MutableList라면 List의 메서드들도 물론 사용 가능하다. 읽기 전용 List와 변경 가능한 List를 생성하는 방법은 Collections 사용하기 포스트에서 ‘Collections 생성 함수’ part를 참조하자.

List 종류

Fig3. List interface의 Hierarchy(상속 관계)

만약 자료들을 보관할 자료구조로 List를 선택하였다면, 다음은 List중 어떤 List를 선택할껀지 선택해야한다. Fig3은 List인터페이스의 하위클래스들이나 인터페이스 목록이다. List의 종류는 다 기억하기엔 벅찰 정도이다. 그러나 중요하고 자주 사용할 List는 ArrayList와 LinkedList이다.

ArrayList

ArrayList는 배열을 기반으로 데이터를 관리하지만, 배열과 달리 크기가 고정되어있지 않다. 즉 배열은 초기화할 때 크기를 정하고 이 때 보관 가능한 데이터의 개수가 배열의 크기와 같다면 새로운 데이터를 추가하여 배열의 크기를 변경할 수 없지만, ArrayList는 동작 기반이 되는 배열이 꽉 찼더라도 데이터를 추가할 수 있다. ArrayList는 MutableList를 구현하여, 변경 가능하다. mutableListOf()를 사용하여 생성한 List가 바로 ArrayList이다.

ArrayList 생성하기

ArrayList는 다음과 같은 방법으로 생성할 수 있다.

Example1. ArrayList 생성하기
fun main() {
    val arr = ArrayList<Int>(5) //초기 크기를 설정하기
    val arr2 = arrayListOf<Int>(10,11,12)   //arrayList에 들어갈 객체를 나열하기
    val arr3 = ArrayList(arr2)  //Collection을 인자로 받아 arrayList 생성
}

Example1을 보자. ArrayList는 Int 자료형을 담는 것으로 정했고,

1. arr은 ArrayList의 초기 크기를 설정하며 ArrayList를 저장하고 있다. 이렇게 초기 크기를 설정하는 이유는 ArrayList는 배열을 기반으로 구현되기 때문에, 배열 크기에 따라 데이터를 삽입하는 데 걸리는 시간이 다르기 때문이다. 초기 크기를 크게 설정하면 데이터 삽입이 빠르겠지만, 그만큼 더 많은 공간이 필요하다.

2. arr2는 배열에 들어가는 객체를 나열하면서 ArrayList를 생성한다.

ArrayList — time complexity

Fig4. ArrayList BigO

Fig4는 ArrayList의 시간 복잡도 중에 최악의 경우인 Big O를 나타낸 것이다.

• ArrayList의 데이터 접근은 구현된 배열에서 인덱스를 통해 접근하기 때문에, O(1)의 시간 복잡도를 가진다.
• 데이터를 추가할 때 경우가 나누어지는데, ArrayList의 초기 크기를 5로 생성했다면, 데이터를 5개 추가할 때까지는 특별한 알고리즘 없이 바로 추가되어 O(1)의 시간 복잡도를 갖는다. 그 다음 데이터를 추가하면 ArrayList가 갖고 있는 배열을 더 큰 공간의 배열에 옮겨야 하기 때문에 원래의 데이터들을 삭제하고 새로운 곳에 복사를 한 후 데이터를 추가하면 O(N)의 시간 복잡도를 갖는다. 특정 위치에 데이터를 추가하는 경우는 특정 위치에 데이터를 넣고 인덱스 상 특정 위치보다 뒤에 있는 데이터들이 뒤로 옮겨져야 하기 때문에 역시 O(N)의 시간 복잡도를 갖는다. (Fig5는 빈 공간이 없을 때, ArrayList의 마지막 위치에 데이터 추가 과정을 나타냈지만, 실제로는 새로 생기는 배열의 크기가 하나씩 늘어나진 않을 수 있다.)

Fig5. 빈 공간이 없을 때, ArrayList의 마지막 위치에 데이터 추가 과정 예시

• 데이터를 제거하는 경우는 데이터를 삭제하고 인덱스 상으로 삭제한 데이터 뒤에 있던 데이터들이 앞으로 옮겨져야 하므로 O(N)의 시간 복잡도를 갖는다.
• 데이터를 검색하는 경우 어떤 순서(ex.순방향, 역방향)대로 데이터를 하나하나 비교해야하므로 O(N)의 시간 복잡도를 갖는다.

ArrayList 사용하기

ArrayList를 생성했다면 본 포스트 위쪽의 List Interface의 메서드를 사용하여 데이터에 접근, 데이터를 추가, 삭제, 검색 등을 할 수 있다. List Interface는 Collection Interface를 상속받으므로, Collection Interface의 메서드도 사용하고 ArrayList의 다른 메서드들도 사용하면 된다. ArrayList는 인덱스를 통한 원소 접근 시 빠른 속도를 보인다.

LinkedList

LinkedList는 ‘보관할 데이터와 다음 데이터의 주소를 갖는 Node’들을 연결하여 전체 데이터를 관리한다. LinkedList는 MutableList를 구현하여, 변경 가능하다.

Fig6. LinkedList 구조

Fig6은 Linked List 를 표현한 구조이다. Singly Linked List는 Node가 다음 데이터의 주소를 갖고 있지만, Doubly Linked List는 이전 데이터의 주소도 갖고 있어서 역방향으로 순회하는 것도 가능하다. 흔히 Linked List의 첫 노드를 head 또는 first, 마지막 노드를 tail 또는 last라고 부른다. Kotlin의 Linked List 는 Doubly Linked List구조를 취하고 있다.

LinkedList 생성하기

LinkedList는 다음과 같은 방법으로 생성할 수 있다.

Example2. LinkedList 생성하기
fun main() {
    val linkedList = LinkedList<Char>() //빈 LinkedList생성
    val linkedList2 = LinkedList(linkedList)    //Collection을 인자로 받아 linkedList 생성
}

LinkedList — time complexity

Fig7. LinkedList BigO

Fig7는 LinkedList의 Big O를 나타낸 것이다.

• 데이터에 접근하는 경우 어떤 순서(ex.순방향, 역방향)대로 데이터를 하나하나 비교해야하므로 O(N)의 시간 복잡도를 갖는다.
• 데이터를 추가하는 경우, 처음이나 마지막에 추가할 때는 head나 tail을 바꾸고 추가한 데이터의 다음이나 이전 참조를 원래 head나 tail로 정하면 되므로 O(1)의 시간 복잡도를 갖고, 특정 위치에 추가하는 경우 그 위치까지 어떤 순서(ex.순방향, 역방향)에 의해 들어갈 자리를 찾아야 하므로 O(N)의 시간 복잡도를 갖는다.
• 데이터를 제거하는 경우도 데이터를 추가하는 경우와 마찬가지의 시간 복잡도를 갖는다.
• 데이터를 검색하는 경우 어떤 순서(ex.순방향, 역방향)대로 데이터를 하나하나 비교해야하므로 O(N)의 시간 복잡도를 갖는다.

LinkedList 사용하기

LinkedList를 생성했다면 본 포스트 위쪽의 List Interface의 메서드를 사용하여 데이터에 접근, 데이터를 추가, 삭제, 검색 등을 할 수 있다. List Interface는 Collection Interface를 상속받으므로, Collection Interface의 메서드도 사용하고 LinkedList의 다른 메서드들도 사용하면 된다. (Doubly) LinkedList는 처음이나 마지막 위치에 데이터를 추가 혹은 제거할 때 빠른 속도를 보인다.

Reference

Overall part

1. Kotlin documents — https://kotlinlang.org/docs/reference/
2. Dmitry Jemerov and Svetlana Isakova. (2017). Kotlin in Action. USA: Manning
3. [Dzone] “Performance Analysis of ArrayList and LinkedList in Java” — https://dzone.com/articles/performance-analysis-of-arraylist-and-linkedlist-i