학습 일자 : 2023.04.18
동일한 타입의 요소를 메모리상에 연속적으로 저장하는 자료구조
→ 동일한 타입의 데이터를 연속적으로 저장하기 때문에 인덱스를 통해 직접 접근이 가능함
int 배열이 100번지에 만들어졌다고 가정하면, 1번째 자료는 104번에, 2번째는 108번에, 3번째는 112번에… n번째는 (데이터 크기 x N)번에 있음 → 특정 위치를 추측할 수 있음. (특정 위치를 찾는 방법이 바로 인덱스임)
[ 시작위치 + 데이터크기 x n ]으로 위치를 계산하는 방법이기 때문에 배열 선언에서 지정한 크기 이상 넘어가서 작성하는 것도 “문법적으로는 가능”함 (but, 실행 시점에 오류 남)
초기화때 정한 크기가 소멸까지 유지됨
⇒ 정해진 크기가 중요한 데이터의 집합을 경우 배열이라는 자료구조를 사용함
접근 : O(1) → 인덱스를 사용하기 때문
탐색 : O(N) → 데이터가 n개 있을 때, 특정 수를 찾기 위해 최악의 경우 N번을 반복해야 찾을 수 있음
보통은 n/2만큼 시간이 걸리겠지만 bingO에서 보통 상수는 관심 없음. > 버림
why? 시간 복잡도는 ✌대략적인✌ 상승폭을 나타내는 표기 법임
컴퓨터는 생각보다 더 많은 데이터를 처리하기 때문에 성장률에 초점을 맞춤.
지수에 따라서는 큰 폭으로 변동되지만, 상수에 따라서는 그렇게까지 큰 폭의 변화는 없음.
따라서 O(n/2) = O(n)
삽입 : O(n)
삭제 : O(n)
⇒ 메모리 상에서 연결된 구조를 가지고 있기 때문에 중간에 삽입 또는 삭제를 할 경우, 순회하면서 삽입 시 이후 데이터를 미뤄주고, 삭제 시 이후 데이터를 앞으로 당겨와야 함.
→ 최소 1회 이상 순회가 필요함
런타임 중 크기를 확장할 수 있는 배열기반의 자료구조
배열요소의 갯수를 특정할 수 없는 경우 사용
<aside> 💡 리스트 선언 List<자료형> 리스트_이름 = new List<자료형>( );
</aside>
| 접근 | O(1) |
|---|---|
| 탐색 | O(n) |
| 삽입 | O(n) |
| 삭제 | O(n) |
리스트는 힙영역에 저장 됨. → Add할 때마다 연속적으로 방을 만들 수 없음. → 애초에 크게 잡아 놓고, Add할 때마다 추가하는 방식을 통해 연속적으로 데이터를 저장 함
list.Count() : 현재 사용하고 있는 방의 개수