[Kotlin] 선형리스트(ArrayList) vs 연결리스트(LinkedList)

리스트(List)는 무엇인가?

---

import java.util.*

fun main() {

    // 연결리스트(LinkedList) 데이터 삽입 시간
    val linkedList: LinkedList<String> = LinkedList()
    linkedList.add("1")
    linkedList.addAll(arrayOf("2", "3"))
    linkedList.addFirst("Head")
    linkedList.addLast("Last")
    println(linkedList)

    var startTime = System.currentTimeMillis()
    for (i in 0 until 10) {
        linkedList.add(4, "?")
    }
    println(linkedList)
    println("연결리스트(LinkedList) 데이터 삽입 소요 시간 : " + (System.currentTimeMillis() - startTime))
    println()


    // 선형리스트(ArrayList) 데이터 삽입 시간
    val arrayList: ArrayList<String> = ArrayList()
    arrayList.add("1")
    arrayList.addAll(arrayOf("2", "3"))
    arrayList.add(0, "Head")
    arrayList.add(arrayList.size, "Last")
    println(arrayList)

    startTime = System.currentTimeMillis()
    for (i in 0 until 10) {
        arrayList.add(4, "?")
    }
    println(arrayList)
    println("선형리스트(ArrayList) 데이터 삽입 소요 시간 : " + (System.currentTimeMillis() - startTime))

}

실행 결과

 

 

 

 

각각 10개의 데이터를 삽입했을 때의 소요 시간 결과로는 별 차이가 없다.

좀 더 많은 데이터를 삽입해보자. (1만 개씩)

 

 

 

각각 1만 개 추가했을 때의 결과

 

 

 

 

좀 더 많은 데이터를 삽입해보자. (10만 개씩)

 

 

 

각각 10만 개 추가했을 때의 결과

 

 

 

연결리스트(LinkedList)가 선형리스트(ArrayList) 보다 데이터 삽입, 삭제 성능이 좋다.

이제 데이터 Access time 측면에서 보자.

 

 

 

---

import java.util.*

fun main() {

    // 연결리스트(LinkedList) 데이터 삽입 시간
    val linkedList: LinkedList<String> = LinkedList()
    linkedList.add("1")
    linkedList.addAll(arrayOf("2", "3"))
    linkedList.addFirst("Head")
    linkedList.addLast("Last")
    println(linkedList)

    var startTime = System.currentTimeMillis()
    for (i in 0 until 1000000) {
        linkedList[2]
    }
    println("연결리스트(LinkedList) 데이터 접근 소요 시간 : " + (System.currentTimeMillis() - startTime))
    println()


    // 선형리스트(ArrayList) 데이터 삽입 시간
    val arrayList: ArrayList<String> = ArrayList()
    arrayList.add("1")
    arrayList.addAll(arrayOf("2", "3"))
    arrayList.add(0, "Head")
    arrayList.add(arrayList.size, "Last")
    println(arrayList)

    startTime = System.currentTimeMillis()
    for (i in 0 until 1000000) {
        arrayList[2]
    }
    println("선형리스트(ArrayList) 데이터 접근 소요 시간 : " + (System.currentTimeMillis() - startTime))

}

100만 번 접근했을 때의 소요 시간

 

1000만 번 접근했을 때의 소요 시간

 

 

1억 번 접근했을 때의 소요 시간

 

 

선형리스트(ArrayList)가 연결리스트(LinkedList) 보다 데이터 Access time 성능이 좋다.

 

 

 

 

 

참고.

stackoverflow.com/questions/10656471/performance-differences-between-arraylist-and-linkedlist

Performance differences between ArrayList and LinkedList