[자료구조] Array와 LinkedList의 삽입/삭제 (feat. ArrayList vs LinkedList)

1. Array vs LinkedList

정의

  Array와 LinkedList는 모두 연속된 데이터 집합을 위한 기본 자료구조입니다.

 

차이

  Array와 LinkedList의 가장 큰 차이는 메모리 할당 방식입니다.

 

Array

  Array는 연속적인 주소 할당으로, 주소를 이용하면 모든 데이터의 접근 시간이 동일한 Random Access가 가능하여 데이터 탐색이 빠를 수 있습니다(O(1)).

  그러나 데이터 삽입/삭제에서 이 연속성을 지키기 위해 데이터를 움직이는 비용(O(n))이 발생하고, 크기가 고정되야하기 때문에 Dynamic Array의 경우 데이터 삽입 중 크기가 큰 Array로 copy하는 비용(Amortized O(1))이 발생할 수 있습니다.

 

LinkedList

  LinkedList는 원소마다 인접한 원소의 주소만 기억하므로, 탐색이 비교적 느릴 수 있습니다(O(n)).

  그러나, 데이터 삽입/삭제시 동적으로 주소를 할당하고, 원소의 포인터를 연결하는 비용만 발생하여 비교적 빠를 수 있습니다(O(1)).

 

정리

	탐색	삽입/삭제
Array	O(1)	O(n) + Amortized O(1)
LinkedList	O(n)	O(1)

 

2. 의문점

  위에서 정리한 내용에 따르면, Array와 LinkedList에서 데이터를 삽입/삭제 할 때 소요되는 시간은 O(1) + O(n)으로 비슷해보입니다. 그런데 Java의 정석에서 Array를 사용하는 Collection.ArrayList와 LinkedList를 사용하는 Collection.LinkedList를 비교할 때, (1)삽입/삭제가 빈번한 경우 LinkedList가 더 빠르다라는 내용을 확인했습니다. 게다가, 이를 확인하기 위한 (2)아래 테스트에서 Array가 LinkedList보다 삽입/삭제 속도가 더 빠른 것을 확인하였습니다.

https://github.com/pythaac/Performance_Test/tree/main/Dynamic_Array_vs_LinkedList_for_List

GitHub - pythaac/Performance_Test: These tests are for optimization and verifying out what I'm confused.

 

3. 테스트

  이를 자세하게 확인하기 위해서 아래 테스트를 진행하였습니다.

https://github.com/pythaac/Performance_Test/tree/main/Dynamic_Array_vs_LinkedList_for_List_2

GitHub - pythaac/Performance_Test: These tests are for optimization and verifying out what I'm confused.

결론은, Java의 정석에서 테스트한 코드는 "데이터의 앞쪽 인덱스"를 대상으로 삽입/삭제하여 LinkedList의 속도가 빠른 결과를 나타냈습니다. "데이터의 중간 인덱스"를 대상으로 같은 테스트를 진행할 경우, ArrayList가 더 빠른 것을 확인하였습니다. 테스트의 결과를 정리하면 다음과 같습니다.

1. 삽입/삭제 인덱스가 앞쪽일수록 LinkedList가 빠르다.
- Array는 삽입/삭제 대상이 앞쪽일수록 shift할 데이터 양이 많아진다.
- LinkedList는 삽입/삭제 대상이 중앙에서 멀어질수록 대상을 빠르게 탐색한다.
2. 삽입/삭제 인덱스가 중앙일수록 Array가 빠르다.
- Array에서 shift할 데이터 양은 N/2이다.
- LinkedList가 삽입/삭제 대상을 찾기위해 N/2만큼 탐색한다.
3. 삽입/삭제 인덱스가 뒤쪽일수록 비슷하다.
- Array는 삽입/삭제 대상이 뒤쪽일수록 shift할 데이터 양이 적어진다.
- LinkedList는 삽입/삭제 대상이 중앙에서 멀어질수록 대상을 빠르게 탐색한다.

	앞쪽 인덱스	중간 인덱스	뒤쪽 인덱스
Array	느림	빠름	빠름
LinkedList	빠름	느림	빠름

 

4. 결론

  먼저 Array vs LinkedList의 "삽입/삭제"만 고려한 속도는 O(n) vs O(1)이므로 LinkedList가 빠르다고 볼 수 있습니다. 그리고 "탐색"을 포함한 삽입/삭제 속도는 대상 인덱스에 따라 다르지만, 임의의 인덱스에 대해 빈번히 일어날 경우 Array가 더 빠른 것으로 보입니다.

  그러나 삽입/삭제가 빈번한 경우 LinkedList를 사용해야하는 이유는 메모리인 것 같습니다. LinkedList는 가변적인 크기 조절이 가능하지만, Array의 경우 크기가 고정되어야하며, Dynamic Array면 주소 크기가 exponential하게 증가합니다.