List vs Array

이번 게시물에서는 리스트(List)와 배열(Array)에 대하여 알아보려고 한다.

List

• 리스트는 빈틈없는 데이터 적재에 초점을 맞춘 자료구조이다.
• 리스트는 원소들 간의 순서가 있는 데이터의 모임이라고 할 수 있다.
• 리스트의 인덱스는 각 원소들의 순서를 나타내는 지표로 사용된다.
• 순차성을 보장하지 않기 때문에 special locality가 보장되지 않게 되고, 이는 cache hit에 어려움을 준다.

Array

• 배열은 여러 데이터를 하나의 이름으로 그룹핑하여 관리하기 위한 자료구조이다.
• 배열에서의 인덱스는 원소들에 대한 위치만을 알리는 지표로 사용된다.
• 배열의 크기를 처음에 지정하면, 크기를 변경할 수 없다.
• 원소의 인덱스는 변경되지 않는다.
• 관련 있는 데이터를 메모리에 순차적으로 나열할 수 있다. (인덱스)
• 인덱스를 활용하여 빠르게 조회할 수 있다.
• cache hit의 가능성이 크기 때문에 성능이 좋다.
• 삭제된 원소의 자리는 빈자리로 그대로 남게되고, 다른 원소들의 인덱스는 그대로 유지된다.
  - 원소들이 삭제되면 빈자리로 남기 때문에 메모리의 낭비가 발생한다.

List vs Array

• List의 인덱스는 원소들의 순서를 나타내고, 중간의 원소가 삭제될 경우 빈공간을 없애고 인덱스를 변경시키기 때문에 메모리의 낭비가 없다. Array의 인덱스는 중간의 원소가 삭제되어도 변경되지 않고 빈자리로 두기 때문에 메모리 낭비가 발생한다.
• List는 cache hit가 좋지 않지만, Array는 cache hit가 좋은 편이다.
• List는 크기가 가변적이지만, Array는 크기가 불변적이다.
  - 크기가 가변적인 Array도 존재하지만, 이 경우 크기를 변경하고자 할 때에는 새로운 빈 Array를 생성하고 값을 복사하는 방식을 사용하기 때문에 성능이 좋지 않다.

정리

원소의 순서가 중요한 경우와 크기를 정확히 모르는 경우에는 List를 사용하는 것이 좋고, 크기가 고정적이고 자주 사용하는 경우라면 Array를 사용하는 것이 좋다.