조회
arr[i] = O(1)
인덱스가 있으면 바로 주소를 계산해 접근한다.
ARRAY MODEL
배열은 연속 메모리라 조회가 빠르고 이동이 비싸다
인덱스 접근은 주소 계산으로 끝나지만, 중간 삽입과 삭제는 뒤 원소를 밀거나 당겨야 한다.
0
1
2
3
4
5
붙어 있는 칸이므로 순회와 임의 접근은 안정적이다.
순회
cache-friendly
연속된 칸을 차례로 읽으므로 반복 조회에 강하다.
삽입
중간은 O(N)
새 칸을 만들려면 뒤 원소를 한 칸씩 밀어야 한다.
삭제
빈칸 메우기
중간 삭제 후에는 뒤 원소를 당겨 순서를 보존한다.