[Algorithm] 자료구조 - 배열(Array)

 

배열

---

같은 자료형의 다중 원소 집합

순서대로 번호(인덱스, index)가 붙은 원소들이 연속적인 형태로 구성되어 있다

 

 

배열의 API과 시간복잡도

API (Application Programming Interface)

---

- k번째 위치에 원소 삽입 : 상수 시간 O(1)에 k번째 위치에 값 저장

- k번째 위치에서 값 읽기 : 상수 시간 O(1)에 k번째 위치에 저장된 값에 접근

- k번째 위치에 저장된 값 대체하기 : 상수 시간 O(1)에 k번째 위치에 저장된 값을 새 값으로 대체

 

 

배열의 단점

---

- 고정된 크기를 가지기 때문에 저장할 수 있는 값이 한정되어 있다

- 더 많은 값을 고정하기 위한 방법

    - 크기가 충분한 새 배열을 재할당 / 복사 -> 연산이 느리다

    - 처음부터 더 큰 배열을 할당 -> 메모리 낭비

> 이러한 배열의 문제를 해결하기 위한 방법이 연결 리스트!

💡 연결 리스트 : codesyun.tistory.com/108

[Algorithm] 연결 리스트 (Linked list)

 

 

 

💡 자료 구조 : codesyun.tistory.com/106

[Algorithm] 자료 구조(Data Structure) 란?