[자료구조] 배열(Array)

정의

메모리에 데이터들을 연속적으로 배치한 자료구조

 

특징

• 임의의 위치에 있는 데이터를 확인/변경하는 데 O(1)의 시간이 걸린다
• 배열 끝에 데이터를 추가 / 배열 끝의 데이터를 삭제하는 데 O(1)의 시간이 걸린다
• 임의의 위치에 데이터를 추가 / 삭제하는 데 O(N)의 시간이 걸린다
  • 해당 위치 이후의 데이터들을 전부 한 칸씩 밀어내거나, 당겨와야 한다
• 추가로 소모되는 메모리가 거의 없다
• 캐시 적중률이 높다
  • 데이터들이 연속적으로 배치되어 있어 참조 지역성(공간적 지역성)을 잘 활용할 수 있다
• 메모리에 연속적으로 배치해야 하기 때문에 할당에 제약이 있다