[Kotlin] Array vs ArrayList vs LinkedList vs Queue

 

Array

Pros

index access O(1)

Stack 영역에 연속된 메모리 할당으로 인해 캐시 히트율이 높음

 

Cons

데이터 크기를 미리 예상할 수 있을 때만 적절히 사용가능

삽입/삭제시 index control 해줘야함.

 

 

ArrayList

Pros

index 기반 접근시간 O(1)

차례대로 데이터를 추가하거나 마지막 (꼬리) 부터 데이터 삭제는 빠름.

 

Cons

삽입, 삭제시 밀어내기, 당겨오기 때문에 비효율적

Capacity 를 넘어갈 경우 기존 ArrayList 를 새 공간에 할당하며 복사가 일어나 비효율적

 

LinkedList

Java, Kotlin 의 LinkedList 는 내부적으로 DoublyLinkedList 로 구현되어있다.

class DoubleLinkedListNode (
	var nextNode: DoubleLinkedListNode?, 
    var prevNode: DoubleLinkedListNode?, 
    val values: Any){

}

Pros

빠른 삽입/삭제 (next 레퍼런스 값만 변경하면됨)

맨 앞/뒤 삽입 삭제도 head, tail 레퍼런스가 존재하기 때문에 빠름.

 

 

Cons

index 기반 access 이 불가능 (Search operation 느림) == O(N)

linking 에 사용되는 next, prev 등의 추가 공간사용.

 

 

 

Array vs ArrayList vs LinkedList 판단기준

구분	Access Time	Insert / Delete	Memory Allocation	비고
Array	O(1)	구현 방식따라 상이	On Stack at the compile time	데이터 크기 예상 가능할 때
ArrayList	O(1)	O(N)	On Heap at the runtime	맨 뒤 삭제/추가는 O(1) Capacity 넘어갈 경우 복사 O(N)
LinkedList	O(N)	O(1)	On Heap at the runtime	데이터가 많아질 수록 access time 길어짐

 

음.. ArayList <-> LinkedList 등
이렇게 전환하는덴 비용 별로 안드나?

 

 

Queue

Stack 은 ArrayList 기반

Queue 는 LinkedList 기반이다 왜 그럴까?

 

Stack 데이터의 삽입/삭제가 맨 윗칸 (top) 에서 이뤄진다. -> 배열의 맨 끝에서 삽입/삭제가 이뤄진다 

Queue 데이터의 삽입/삭제가 맨 첫칸에서 이뤄진다. -> 만약 ArrayList면 맨 첫칸을 지우며 당겨오느라 O(N)의 시간이 걸릴 것이다. 

 

 

Deque (Double Ended Queue)

LinkedList 로 구현

 

 

ArrayDeque 로 구현 (추천)

ArrayDeque 구현체와 LinkedList 방식의 구현의 장단점 비교는 위의 ArrayList vs LinedList 와 거의 같다.

데이터의 크기가 예상되고 뒷쪽에서 넣는게 많다면 ArrayDeque 를

데이터 크기 예상이 어렵고 앞쪽에서 넣는게 많다면 LinkedList 를 추천한다.

데이터 삽입/삭제 위치와 데이터 크기 예상 관계 없이 ArrayDeque가 더 유리하다.

 

LinkedList 기반 , ArrayDeque 기반 Deque 성능 테스트

 

총 1억개의 데이터를 Deque의 '뒷' 부분과 '앞' 부분에 넣어보겠다.

내 가설은 "ArrayDeque"는 배열 기반이므로 index 0 에 가까운 addLast 로 비교하면 LinkedList 가 훨씬 더 빠를 것이다 였다.

또, addFirst 라 해도 Capacity 가 높아지면 복사가 일어나므로 이 또한 LinkedList 가 더 빠를 줄 알았다.

 

 

1. addLast

internal fun testCompareDeque() {
    val linkedQueue : Deque<Int> = LinkedList<Int>()
    val arrayDeque : ArrayDeque<Int> = ArrayDeque(100)

    
    val linkedJobTime = measureTimeMillis {
        for (i in 1 .. 50_000_000) {
        // 꼬리 부분으로 넣는것 (뒷 부분)
            linkedQueue.addLast(i)
        }
    }

    val arrayDequeTime = measureTimeMillis {
        for (i in 1 .. 50_000_000) {
            arrayDeque.addLast(i)
        }
    }


    println("LinkedList based time")
    println("$linkedJobTime ms elapsed.")

    println("ArrayDeque based time")
    println("$arrayDequeTime ms elapsed.")
}

 

2. addFirst

    internal fun testCompareDequeFirst() {
        val linkedQueue : Deque<Int> = LinkedList<Int>()
        val arrayDeque : ArrayDeque<Int> = ArrayDeque(100)

        // First 에 넣는 것
        val linkedJobTime = measureTimeMillis {
            for (i in 1 .. 50_000_000) {
                linkedQueue.addFirst(i)
            }
        }

        val arrayDequeTime = measureTimeMillis {
            for (i in 1 .. 50_000_000) {
                arrayDeque.addFirst(i)
            }
        }

        println("LinkedList based time")
        println("$linkedJobTime ms elapsed.")

        println("ArrayDeque based time")
        println("$arrayDequeTime ms elapsed.")
    }

3. RemoveLast

5천만개 데이터를 각각 넣어놓고  모두 last 에서 제거해보자.

    @Test
    internal fun testCompareDequeDelete() {
        val linkedQueue : Deque<Int> = LinkedList<Int>()
        val arrayDeque : ArrayDeque<Int> = ArrayDeque(100)

        for (i in 1 .. 50_000_000) {
            linkedQueue.addLast(i)
            arrayDeque.addLast(i)
        }

        val linkedJobTime = measureTimeMillis {
            while(linkedQueue.isNotEmpty()) {
                linkedQueue.removeLast()
            }
        }

        val arrayDequeTime = measureTimeMillis {
            while(arrayDeque.isNotEmpty()) {
                arrayDeque.removeLast()
            }
        }

        println("LinkedList based time")
        println("$linkedJobTime ms elapsed.")

        println("ArrayDeque based time")
        println("$arrayDequeTime ms elapsed.")
    }

 

4. RemoveFirst

    @Test
    internal fun testCompareDequeDeleteFirst() {
        val linkedQueue : Deque<Int> = LinkedList<Int>()
        val arrayDeque : ArrayDeque<Int> = ArrayDeque(100)

        for (i in 1 .. 50_000_000) {
            linkedQueue.addLast(i)
            arrayDeque.addLast(i)
        }


        val arrayDequeTime = measureTimeMillis {
            while(arrayDeque.isNotEmpty()) {
                arrayDeque.removeFirst()
            }
        }

        val linkedJobTime = measureTimeMillis {
            while(linkedQueue.isNotEmpty()) {
                linkedQueue.removeFirst()
            }
        }


        println("LinkedList based time")
        println("$linkedJobTime ms elapsed.")

        println("ArrayDeque based time")
        println("$arrayDequeTime ms elapsed.")
    }

 

테스트 결과

The number of data set: 50 millions

Unit: milliseconds (ms)

	LinkedList	ArrayDeque
addLast	6649	1918
addFirst	6798	1889
removeLast	1350	353
removeFirst	1483	422

항상 `ArrayDeque` 가 `LinkedList` 보다 빠르다.
Deque 는 ArrayDeque 를 사용해 구현하자.

 

 

 

 

왜 ArrayDeque 가 더 빠른가? 

내 오해중 하나는 ArrayDeque 가 일반 배열이라 생각했던 것이다.

ArrayDeque 는 head, tail 의 포인터를 가진  Circular Array 로 구현되어있다. 

 

• 삽입/삭제의 앞/뒤 상관없이 현재의 Capacity 가 꽉차기 전까지는일반 배열처럼 밀기/당기기 시간이 소모되지 않으므로 O(1) 에 삽입/삭제가 가능하다.
• 배열의 특성상 'Cache locality' 의 이점을 볼 수 있다. (cache hit 확률 높음)
  반면에 LinkedList 는 보유하고 있는 값들의 메모리상 로드된 위치가 산발적일 수 있기 때문에 (cache hit 확률 낮음)

 

물론, ArrayDeque 라 하더라도 head(first), tail(last) 가 아니라 중간에 위치한 원소를 삽입/삭제할 경우 size 조정과 함께 밀기/당기기 연산이 일어나므로 O(N) 이 소요된다.

 

🔗 Reference

Diagram ArrayDeque is faster than LinkedList - Moment For Technology