[Data Structure] 배열 (Array)

✔ 배열

배열(Array)이란?

• 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조
• 선언한 자료형의 값만 저장하여 연속적으로 이루어져 있음
• 불변하므로 기존 배열이나 값을 변경시키지 않고 주어진 배열이나 요소들을 기존 배열에 합쳐 새 배열을 반환

배열의 특징

1. 인덱스를 사용하여 값에 바로 접근할 수 있음
   • 논리적 저장 순서와 물리적 저장 순서가 일치
   • O(1)의 시간 복잡도로 해당 원소에 접근 가능
   • 랜덤 접근이 가능
2. 새로운 값을 삽입하거나 삭제할 때는 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하므로 어려움
   • 배열은 연속적인 특징을 가져야 하므로 이를 위한 shift 비용인 O(N)의 시간 복잡도가 발생
3. 배열의 크기는 선언할 때 지정하며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음
   • 메모리에는 배열이 선언되자마자 컴파일 타임에 할당됨
   • 정적 메모리 할당
   • 메모리 공간 활용에 제약
4. 구조가 간단하므로 코딩 테스트에서 많이 사용함

배열을 언제 사용할까?

• 데이터의 크기가 고정되어 있으며, 데이터의 접근이 많을 때 유리

배열 리스트(ArrayList)란?

1. 내부적으로 배열을 사용하여 데이터를 관리
2. 배열과 동일한 특징을 가지지만, 길이가 가변 길이를 가지므로 Dynamic Array이라고도 불림
   • 기본값으로 10개의 공간을 가진 배열로 시작
   • 대신 Array보다 속도가 약간 느리므로 Array로 충분히 처리가 가능할 경우 Array를 활용