배열 (Array)

배열(Array)

---

모든 요소가 순차적으로 배열된 선형 데이터 구조

연속된 메모리 위치에 저장된 동일한 데이터 유형의 요소의 컬렉션

배열의 각 항목은 0부터 시작하여 인덱싱, 인덱스 값을 사용하여 배열 요소에 직접 액세스 가능

 

시간복잡도

---

인덱스를 알고 있다면, 인덱스에 접근하는 시간복잡도는 O(1)이다.

데이터를 배열에 삽입을 하려면 기존에 있는 데이터를 한 칸 shift 한 후 데이터를 넣어야 하기에 시간복잡도는 O(n)이 걸린다.

마찬가지로 배열에서 데이터를 삭제하는 작업 또한 삭제한 뒤, 나머지 데이터들을 한 칸 shift 해줘야 해서 삽입과 마찬가지로 시간복잡도가 O(n)이 걸리게 된다.

 

장점

---

• 구현이 쉽다
• 검색 기능이 좋다
• 인덱스(index)를 이용한 무작위 접근(random access)이 가능하므로 검색에서 빠른 성능

 

단점

---

• 선언할 때 크기가 고정되어 메모리가 모자라는 경우 모든 요소를 새로운 메모리로 이동해야한다
• 요소를 중간에 삽입하거나 삭제 시 해당 요소 뒤에 있는 요소들의 인덱스를 조정해야한다. -> 복잡하고 비효율적