Array
배열은 모든 프로그래밍 언어에서 사용되는 핵심 기능이며 다음과 같은 특징을 가지고 있다.
- 배열은 어떤 타입의 값이든 저장할 수 있다.
- 배열은 크기가 정해져있다.(swift에서는 배열을 초기화할때 따로 크기를 지정해주지 않는다.)
- 배열은 어느 인덱스에 있는 값이든 무작위로 상수 시간 O(1)으로 접근할 수 있다.
Operations
Get / Set
배열에 얼마나 많은 값이 저장되어 있던지에 상관없이 상수 시간 O(1)으로 값을 설정하거나 얻을 수 있다. 배열의 가장 강력한 기능 중 하나이다!
Insert
값을 배열에 삽입할때 다음과 같은 일이 일어난다.
- 값을 복사해서 옮긴다.
- 값을 삽입한다.
- 배열의 크기를 재정의한다.
예를 들어 [a, c, d]라는 배열에 b라는 값을 인덱스 1에 삽입하려고 한다고 해보자. 그럼 삽입하려는 인덱스를 포함한 그 위의 모든 인덱스의 값들을 복사해서 다음 인덱스로 옮긴다. 그러니까 이 경우 c,d를 인덱스 1,2 에서 2,3으로 옮긴다. 그리고 b를 인덱스 1에 삽입하고 배열의 사이즈를 3에서 4로 변경한다. 값을 삽입할 때의 동작 시간은 선형시간 O(n)인데 그 이유는 값을 복사해서 옮기는 과정에서 배열 속의 값들을 하나하나 확인하기 때문이다.
Delete
배열에서 값을 삭제할때 다음과 같은 일이 일어난다.
- 값을 복사한다.
- 삭제할 값을 복사한 값으로 덮어씌운다.(값을 삭제할 필요가 없다.)
[a, b, c, d]에서 b의 값을 삭제하려고 한다면 인덱스 2 이상의 모든 값들을 복사해서 이전 인덱스의 값에 덮어씌운다. 삽입과 마찬가지로 동작시간은 선형시간 O(n)이다.
Resize
배열에 값을 추가하려고 할때 배열이 가지고 있는 정해진 크기를 벗어나게되면 배열은 크기를 조정한다. 보통 배열에 값을 추가할때는 상수 시간이지만 배열의 크기를 조정해야 될때는 선형시간이다. 배열이 크기를 조정하는 방법은 다음과 같다.
- 기존의 크기보다 2배가 큰 새로운 배열을 만든다.
- 기존 배열의 값들을 복사한다.
- 복사한 값들을 새로운 배열에 넣는다.
- 새로운 값을 추가한다.
Arrays In Swift
스위프트는 배열을 생성할 때 크기를 지정할 필요가 없이 알아서 다 해준다.(직접 지정할 수도 있다.) 또한 삽입, 삭제, 추가 같은 동작들이 내장되어있다.
