얌생

배열 - 메모리상에 원소를 연속하게 배치한 자료구조다.

배열의 성질

• O(1)에 k번째 원소를 확인 및 변경이 가능
• 추가적으로 소모되는 메모리의양( =overhead )가 거의 없다.
• 메모리 상에 데이터들이 붙어있으므로 캐시 적중률이 높다
• 메모리 상에 연속한 구간을 잡아야 하므로 할당에 제약이 걸린다.

기능과 구현

• 임의의 위치에 있는 원소를 확인 하거나 변경할때 O(1)이 걸린다.
• 원소를 끝에 추가 = O(1)
• 마지막 원소를 제거 = O(1)
• 임의의 위치에 원소를 추가 / 임의 위치의 원소 제거 = O(N)