Array는 연관된 Data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조이다.

Array의 특징

• 고정된 저장 공간(fixed-size)
• 순차적인 데이터 저장(order)

Array의 operation들의 time complexity

• 조회(lookup): O(1) - random access
• 마지막 인덱스에 추가(append): O(1)
• 마지막 인덱스에 삭제: O(1)
• 삽입(insert): O(n)
• 삭제(delete): O(n)
• 탐색(search): O(n)

Array의 장점은 lookup과 append가 빠르다는 것이다. 따라서 조회를 자주 해야되는 작업에서는 Array 자료구조를 많이 쓴다.

Array의 단점은 fixed-size 특성상 선언시에 Array의 크기를 미리 정해야 된다는 것이다. 이는 메모리 낭비나 추가적인 overhead가 발생할 수 있다.

Q1) 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐다. 이 때, 어떻게 해결할 수 있을까?

• 기존의 size보다 더 큰 Array를 선언하여 데이터를 옮겨 할당한다. 모든 데이터를 옮겼다면 기존 Array는 메모리에서 삭제한다. 이런식으로 동적적으로 배열의 크리를 조절하는 자료구조를 Dynamic Array라고 한다.
• 또 다른 방법으로는, size를 예측하기 쉽지 않다면 Array 대신 Linked List를 사용함으로써 데이터가 추가될 때마다 메모리 공간을 할당받는 방식을 사용하면 된다.

Q2) Dynamic Array는 어떤 자료구조 인가?

• Array의 경우 size가 고정되어 있기 때문에 선언시에 설정한 size보다 많은 갯수의 data가 추가되면 저장할 수 없다. 이에 반해 Dynamic Array는 저장공간이 가득 차게 되면 resize를 하여 유동적으로 size를 조절하여 데이터를 저장하는 자료구조이다.

대제목

소제목

Reference

1. Semantic Versioning 2.0.0
2. 다양한 소프트웨어 버전 명명 (Software versioning)
3. 버전 표기법 (SemVer) 기초개념 알려드림. 5분 순삭.
4. Semantic Versioning 소개