[자료구조] 배열 Array

선형 자료구조

요소가 일렬로 나열되어 있는 자료구조

---

배열 Array

입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조

구성요소

• 요소(데이터)
• 인덱스(번호) - 배열의 인덱스는 0부터 시작한다

 

특징

• 메모리 상에서 연속적으로 저장되어 있다 ➡️ index를 통한 접근이 용이하다
• 배열의 크기는 처음 생성할 때 정하며 이후에 변경할 수 없다

-

배열 연산

• push()  배열 마지막 인덱스에 요소 삽입
• pop()  배열 마지막 인덱스 요소 제거

-

시간 복잡도

• 삽입/삭제
  • 마지막에 삽입/삭제 O(1)
  • O(n) 새로운 데이터를 추가하기 위해서 기존 데이터들을 재배치해야 함
• 검색 O(n) : 요소 검색을 위해서 해당 인덱스까지 차례로 하나씩 탐색해야 함
• 접근 O(1) : 인덱스를 이용해 바로 접근

 

사용 예시

• 데이터 개수가 고정적이고 삽입/삭제가 빈번하지 않은 경우
• 데이터 접근이 빈번한 경우