Array vs List

Array

• 메모리 상에 데이터가 연속적으로 저장
• 순차적으로 저장된 데이터를 참조할 때는 인덱스가 활용된다.
• 고정된 크기를 갖는다. (데이터 개수가 정해져있다.)
• 논리적 저장 순서와 물리적 저장 순서가 동일하다.
• cache hit rate( cpu가 참조하고자 하는 메모리가 캐시에 존재하는 비율) 이 높다.
• 추가적으로 소모되는 메모리 양이 거의 없다. (데이터 크기를 미리 정해두고 사용하기때문에)
• 삽입/삭제에 o(n) - 데이터의 연속적 형태를 유지하기 위해
• 데이터 접근에 o(1)

List

• 배열이 갖는 인덱스라는 장점을 버리고, 빈틈없는 데이터의 적재라는 장점을 취한 인터페이스
• Linked List, Array List등의 선형 자료 구조를 구현할 때 사용되는 추상 자료형
• 배열은 크기가 정해져있고, 메모리 상에 데이터가 연속적으로 있어야 하기 때문에 메모리의 낭비가 발생. 그러나 리스트는 빈 공간을 허용하지 않기에 메모리 낭비가 없다.
• Data들이 순차적으로 구성된 집합, 그러나 일반적으로 Data가 메모리 상에 연속적으로 저장되지 않음 ( 실제 메모리 주소 랜덤 ). 그렇기에 Cache Hit Rate가 낮다.
• 크기가 가변적이다.
• 삽입, 삭제, 접근에 O(N) 소요
• 삽입, 삭제, 크기 등 해당 리스트를 사용하기 위한 메서드를 따로 구현할 필요가 없다.