[Data Structure] Array

배열(Array)

동일한 데이터 타입을 가진 요소들의 모음으로, 인덱스를 이용하여 각 요소에 접근할 수 있는 데이터 구조입니다.

배열의 장단점

1. 장점

• 인덱스를 통한 빠른 접근: 배열은 인덱스를 사용하여 각 요소에 O(1)의 시간 복잡도로 빠르게 접근할 수 있습니다.
• 메모리 관리: 연속된 메모리 공간에 요소를 저장하기 때문에 메모리 관리가 효율적입니다. (연속된 메모리 공간은 캐시 효율성이 높습니다.)
• 간단한 구조: 배열은 고정된 크기와 연속적인 메모리 공간을 사용하므로 구조가 매우 단순하고 구현이 간단합니다.

2. 단점

• 고정된 크기: 최초 선언시 크기를 정해줘야 합니다. (고정된 크기를 가지기 때문) 크기를 변경해야 할 경우, 새 배열을 할당하고 기존 요소들을 복사해야 합니다.
• 메모리 낭비: 선언한 배열의 크기 보다 적게 사용하면 실제로 사용하지 않는 공간이 낭비됩니다. (내부 단편화)
• 삽입 및 제거의 어려움: 중간에 요소를 삽입하거나 제거하는 작업은 많은 시간과 리소스가 발생합니다.(연속된 메모리 공간에 요소를 저장하는 것을 유지하기 위해)
  

시간 복잡도

• 탐색: O(1)
  • arr[i]처럼 직접 접근할 경우
• 수정: O(1)
  • 인덱스를 모른다면 처음부터 탐색을 해야하니까 O(n)
• 삽입, 삭제: O(n)
  • 삽입, 삭제 후에도 배열이 연속되게 만들어야 하기 때문
  • 인덱스의 맨 끝에 삽입, 삭제를 한다면 상수 시간

Reference
https://velog.io/@mic050r/자료구조-배열-Array이란