Intro

대표적인 mutable 리스트인 ‘ArrayList’와 ‘LinkedList’에 대해 흔히 아는 사실은 다음과 같다.

ArrayList

• Random Access가 가능하므로 조회가 빠르다 = O(1)
• idx에 삽입을 할 경우, idx 이후의 원소를 모두 한칸씩 이동하여 저장해야하므로 느리다 = O(n)

LinkedList

• 조회를 위해 처음부터 해당 idx까지 이동해야 하므로 느리다 = O(n)
• idx에 삽입을 할 경우, idx 이전과 이후 노드들의 연결을 끊고 삽입하면 된다 = O(1)

정확히 반대의 분야에서 서로 Top인 상황..

최근 알고리즘 문제를 풀다, 빈번한 원소 삽입/삭제가 있는 문제에서 ‘LinkedList’는 시간초과가, ‘ArrayList’는 통과가 되는 신기한 경험을 했다.

통념이 사실인지 직접 실험해보면서 어떤 성능적 차이가 있는 지 확인해 보자

동작 방식

먼저 내부 구현을 통해 동작 방식을 알아보자

1. ArrayList

원소 조회

override actual fun get(index: Int): E {
        checkElementIndex(index)
        return backingArray[offset + index]
    }

⇒ index를 통해 RandomAccess가 가능한 것을 확인할 수 있다.

원소 삽입

fun add(index: Int, element: E) 내부 구현에서 실제 값이 저장되는 부분을 찾아가면 아래의 코드를 확인할 수 있다.

private fun addAtInternal(i: Int, element: E) {
        if (backingList != null) {
            backingList.addAtInternal(i, element)
            backingArray = backingList.backingArray
            length++
        } else {
            insertAtInternal(i, 1)
            backingArray[i] = element
        }
    }

private fun insertAtInternal(i: Int, n: Int) {
        ensureExtraCapacity(n)
        backingArray.copyInto(backingArray, startIndex = i, endIndex = offset + length, destinationOffset = i + n)
        length += n
    }