[선형 자료구조] 배열(선형 리스트)

배열이란?

선형 자료구조 중 선형 리스트에 해당하며,

Swift에서는 표준 라이브러리가 제공하는 가장 기본적인 선형 자료구조이다.

 

주요 특징

연속된 메모리 주소

 

배열은 모든 요소가 연속된 메모리 주소를 가지게 된다.

같은 선형 자료구조이지만, 랜덤한 메모리 주소를 가지는 링크드 리스트와는 차이가 있다.

 

이러한 특징으로 인하여, 인덱스를 통한 임의 접근이 가능하며, 시간 복잡도는 O(1)를 가진다.

 

 

시간 복잡도

임의 접근: O(1)

임의 접근한 요소의 메모리 주소 = 시작 메모리 주소 + (인덱스 넘버 * 타입의 메모리 크기)

 

삽입/삭제 (배열 끝): O(1)

마지막 배열에 추가/삭제

 

삽입/삭제 (배열 중간): O(n)

중간에 삽입/삭제를 통해 그 뒤에 있는 요소들의 메모리 위치가 모두 변경