Array와 Linked List는 포스팅한 적이 있다. 이번에는 몇 가지 관점에서 두 자료구조를 비교해본다.
자료구조를 공부하는 목적은 해결하고자 하는 문제에 맞춰 메모리를 효율적으로 사용하기 위해서다.
메모리 공간 효율
먼저 배열은 생성할 때부터 일정 공간을 만들어두다 보니 아무래도 안쓰는 공간이 생길 수 밖에 없다. 그에 비해 연결리스트의 경우 필요한 노드를 그때 그때 만들어서 사용하기 때문에 공간 효율이 좋다.
Cache Miss
배열은 cache miss 가 상대적으로 적기 때문에 효율적이다.
보통 배열을 사용할 때는 반복문 같이 연속적인 작업을 한다. 배열은 메모리상에 연속된 형태로 존재하기 때문에 이렇게 주변 데이터까지 가져가면 연속적인 작업을 할 때 필요한 데이터가 포함될 확률이 높아진다. 따라서 캐시 메모리에 필요한 데이터가 없어서 메모리를 오고가는 횟수가 줄어들기 때문에 효율적이다.
반대로 연결리스트는 노드마다 메모리에 각각 존재하기 때문에 연속적이지 않다. 그래서 반복적인 작업을 하기 위해서 캐시에 데이터를 가져가도 캐시에 다음 데이터가 있을 확률이 낮다. 따라서 필요한 데이터를 찾기위해 메모리를 오고가는 횟수가 많아져서 비효율적이다.
GC
배열은 처음 생성될 때 한 번에 공간을 차지하고 해지될 때도 한 번에 해지된다. 요소를 삭제해도 중간중간 GC되지 않는다. 반면, 연결리스트는 참조를 끊는 식으로 노드를 삭제할 때마다 GC가 돌게 된다. 따라서 연결리스트의 경우 배열에 비해 GC가 빈번하기 때문에 성능에 영향이 있을 수 있다.
결론
대부분의 경우 Array의 성능이 더 좋다. 삽입/삭제가 빈번한 경우라 해도 요소수가 많지 않다면 Array가 더 빠르다. cache되기 때문이다.
만약 요소수가 많은데 삽입/삭제가 빈번한 경우라면 연결리스트를 고려해볼 수 있다. 게임에서 사용되는 '대기열'을 예로 들 수 있다.
밴치마크를 통해서 성능 테스트를 해보고 결정하는 것이 좋다.
느낀점
이렇게 두 자료구조의 특징을 비교해보니까 자료구조의 특징을 잘 알고있는 것이 중요하다고 생각된다. 장점만 있는 것은 없다고 생각된다. 트레이드 오프를 항상 고려해야 한다. 그리고 정말로 효율적으로 자료구조를 사용하려면 수행하려는 작업의 특징을 아는 것 역시 매우 중요하다고 생각된다. 종합적인 요소를 고려해서 최적의 자료구조를 사용하려면 다양한 관점에서 문제를 살펴봐야 할 것 같다.
참고
