[Android/kotlin] List vs MutableList vs ArrayList vs LinkedList

📌 List vs MutableList vs LinkedList vs ArrayList

🐳 List와 MutableList의 차이

 

Kotlin은 많은 변수들을 Mutable 여부로 나누고 있다는 것을 잊지말자.

 

List Collcection에서도 List와 MutableList의 차이는 Read-Only인지 아닌지의 차이이다.

 

그러나, Compile Time에는 둘다 List로써 인식된다. 이는 MutableList가 List를 상속하여 만들어졌기 때문이다.

결국 둘 다 컴파일 결과로 java.util.List 이 된다.

public interface MutableList<E> : List<E>, MutableCollection<E> {
	...
}    

 

🐬 MutableList와 ArrayList의 차이

 

MutableList와 ArrayList의 차이는 사실 클래스명 그대로의 차이이다.

 

MutableList = 추가, 삭제 등 수정이 가능한 리스트

ArrayList = 내부에 Array로 구현되어 있는 추가, 삭제 등 수정이 가능한 리스트

 

즉, ArrayList는 MutableList 중에서도 ArrayList를 사용하겠다 라고 명시한 것이고

MutableList는 Mutable한 List를 사용하겠다 라는 의미이다

 

그러나 현재 Kotlin에서는 mutableList나 arrayListOf나 둘 다 ArrayList를 반환한다.

/**
 * Returns an empty new [MutableList].
 * @sample samples.collections.Collections.Lists.emptyMutableList
 */
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> mutableListOf(): MutableList<T> = ArrayList()

/**
 * Returns an empty new [ArrayList].
 * @sample samples.collections.Collections.Lists.emptyArrayList
 */
@SinceKotlin("1.1")
@kotlin.internal.InlineOnly
public inline fun <T> arrayListOf(): ArrayList<T> = ArrayList()

 

아무래도 미래를 위해서(?) ArrayList말고도 또다른 Mutable한 List이 생길 수 있으니, 이 때 형변환의 자유로움을

위하여 상위 클래스로 만들어 놓은게 아닐까 추측해본다..

 

🐋 ArrayList와 LinkedList의 차이

 

ArrayList

 

내부에 Array(배열)을 두며, 데이터를 추가하면 해당 배열에 set하는 식으로 처리한다.

내부 배열의 size가 커저야 할 때 기존의 array를 copy하고 1.5배 size를 늘린 새 배열을 만들어 기존 배열을 넣고 새 배열을 사용한다.

원하는 데이터를 index를 통해 직접 접근하므로 O(1)의 복잡도를 가진다.

데이터를 중간에 삭제하거나 추가할 경우, 뒤의 데이터 블록들을 한 칸씩 shift하므로 O(n)의 복잡도를 가진다.

내부에 배열로 되어있기 때문에, 연속된 메모리 공간을 사용한다. 인덱스로 접근하면 인덱스로 접근한 원소만 가져오지 않고, 주변의 블럭도 캐시로 읽어들인다. (참조의 지역성-링크)

따라서 공간 최적화의 이점을 누릴 수 있다.

Array와 다르게 길이가 동적으로 할당될 수 있다는 장점이 있지만, 늘어난 배열만큼 데이터를 사용하지 않으면 메모리 낭비로 이어진다는 점이 단점이다.

다만 ArrayList는 공간을 한 번 할당하면 추가할 때 마다 특별하게 들어가는 자원이 없다.

 

정리

1. 내부에 배열을 통해서 구현되어 있는 리스트. 따라서 배열의 특성을 따라간다.

2. Random Access가 가능하므로 인덱스를 통한 검색 시 O(1)의 복잡도를 가진다.

3. 연속된 메모리 공간을 차지하므로 참조의 지역성 효과를 누릴 수 있다. (캐시 효율이 좋다)

4. 데이터를 맨처음, 맨끝이 아닌 곳에 추가할 경우 O(n)의 복잡도를 가진다 (그만큼 shift해야하므로)

5. 내부 배열의 크기는 매번 늘어나는 것이 아니라, 꽉 차면 기존의 1.5배씩 size-up되므로, 나머지 사용되지 않는 부분들은 메모리 낭비이다.

 

LinkedList

 

데이터를 저장하는 data와 다른 노드와의 연결고리인 link로 구성되어 있는 Node로 구성된 리스트이다.

// 추상적인 Node라는 것을 구체적으로 구현해본다면...
data class Node(
    val data: Any? = null,
    val link: Int? = null // 일반적으로 link는 메모리 번지수를 의미하기에 int형으로 선언하였음.
)

 

단순 데이터만 저장하는 것이 아닌 link 변수 또한 노드에 저장하므로 ArrayList에 비하여 메모리 공간 효율이 떨어진다. (메모리를 더 많이 차지한다)

노드의 연결이 link로 이루어지므로 데이터의 삭제나 추가에 있어서 선형 리스트보다 효율이 좋다. 물론 Singly linked list 에서는 처음부터 해당 노드까지 다시 찾아가야 하므로 최악의 경우 O(n)의 복잡도를 가진다. 

원하는 데이터를 찾아가려면 해당 노드까지 링크를 통해 찾아가야하므로 O(n)의 복잡도를 가진다.

또한 메모리에 연속적으로 할당되어 있지 않기 때문에 공간 최적화의 이점을 누릴 수 없다.

ArrayList와 달리 노드가 추가될 때마다 그에 따른 자원이 필요하다

 

정리

1. Data와 Link를 가지는 Node라는 것으로 이루어진 리스트이다.

2. 검색 시 해당 노드까지 Link를 통하여 접근해야하므로 O(n)의 복잡도를 가진다.

3. 노드가 인접한 메모리 공간에 할당된다고 보장하지 않으므로 참조의 지역성 효과를 보기 힘들다 (캐시 효율이 나쁘다)

4. 데이터를 추가, 삭제할 시 앞 뒤 노드들의 Link만 변경하면 되므로 O(1)의 복잡도를 가진다.

5. 데이터만 저장하는 ArrayList와 달리 Link값을 저장하기 위한 메모리도 소모하므로 메모리를 더 차지한다.

 

🦈 LinkedList, ArrayList In Android !

 

그렇다면 List가 자주 쓰이는 RecyclerView의 Adapter의 경우, ArrayList와 LinkedList 중 어떤 List Collection을 이용해야 할까?

 

결론부터 말하자면, ArrayList를 사용하는 것이 낫다.

 

RecyclerView Adapter는 일반적으로 데이터를 index로 접근하여 처리한다.

 

ArrayList의 경우 index를 알고 있을 때, 해당 데이터를 찾아가는 데 O(1)의 복잡도를 보인다. 또한 위에 언급하였듯, 참조의 지역성 효과를 누려 보다 효율적인 캐싱으로 데이터를 찾아가는 데에 있어서는 훨씬 효율적이다.

그러나 LinkedList의 경우, 해당 데이터를 찾아가는 데 O(n)의 복잡도를 보이며, 참조의 지역성 효과 역시 누리기 힘들다.

 

그렇다면 Android에서 LinkedList는 어디에 써먹어야할까?

 

특히 첫번째나 마지막 원소가 추가 / 삭제 / 수정 등이 빈번하게 일어나는 리스트에서 사용하면 좋다.

 

 

 

 

Reference

Official Document 및 find path in Android Studio IDE

https://stackoverflow.com/questions/46445909/difference-between-mutablelist-and-list-in-kotlin

https://stackoverflow.com/questions/43114367/difference-between-arrayliststring-and-mutablelistofstring-in-kotlin 

https://stackoverflow.com/questions/35391705/android-adapter-using-linkedlist-vs-arraylist  

https://stackoverflow.com/questions/53218501/using-kotlins-mutablelist-or-arraylist-where-lists-are-needed-in-android

https://zorba91.tistory.com/287  

https://stackoverflow.com/questions/34490365/linkedlist-vs-arraylist-on-a-specific-android-example

및 자료구조에 관한 문서들..