Array
- 여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조
- 논리적 저장 순서와 물리적 저장 순서 일치
- 해당 인덱스로 해당 원소에 접근
- 인덱스는 value에 대한 유일무이한 식별자
장점
- 원소의 인덱스를 알면 접근시 O(1)
- 데이터가 모여있기 때문에 cache hit rate가 높음
단점
- 원소를 중간에 삽입이나 삭제시 한칸씩 땡기거나 밀어줘야하기 때문에 O(N)
- 크기가 고정되어 사용하지 않는 공간 낭비
List
- 논리적 저장 순서와 물리적 저장 순서가 일치하지 않음
- 원소들 간의 순서가 있는 데이터의 모임
- 원소들은 자기 다음이 어떤 원소인지 기억하고 있음
- 인덱스는 몇번째 데이터인가 정도의 의미
장점
- 원소의 삽입이나 삭제시 원소의 다음 원소만 바꿔주면 되기 때문에 O(1)
- 크기가 정해져 있지 않음
단점
- 배열과 다르게 검색시 처음부터 찾아가야하기 때문에 O(N)
- 각 원소는 다음 원소를 알고 있어야하기 때문에 추가적인 메모리 사용
- 데이터의 순차성이 보장되지 않기 때문에 cache hit가 어려움