[자료구조] 배열(Array)

[배열이란?]

- 인덱스를 가지고있으며 순차적으로 데이터가 삽입 삭제될수있는 형태의 자료구조이다.

 

Array의 특징

- 삽입 순서대로 저장됨

- 인덱스로 특정요소를 빠르게 색인가능하며 각 요소에 접근하는 속도는 O(1) 이다.

- 인덱스로 특정요소에 삽입하는데 걸리는 속도는 O(1)이다.

- 중복 값 삽입 가능

- 다차원 배열이 가능, 백터, 행렬 표현 가능

- 요소의 추가 삭제가 빈번하면 resizing 이슈가 생김

- Resizing같은 리소스 낭비가 없으려면 데이터의 변경이 적을때 배열을 사용하는것이 좋음

 

Array의 메모리 구조

배열의 메모리구조는 차례대로 저장되는 구조이며 메모리 주소조차 순서대로저장된다

즉 실제메모리상에서 물리적으로 데이터가 순차적으로 저장한다

 

배열의 삭제는 중간을 삭제하게된다면 뒤에있는 요소들을 전부 앞으로 당기는 구조입니다

배열은 데이터를 추가할때 resizing의 문제를 가지게 됩니다

배열은 메모리를 어느정도 할당하게되는데 처음에 할당한 양보다 요소가 많아진다면 리사이징이 필요합니다.

((Array리스트)에는 눈에는 보이지않지만 내부에서 resizing함)

 

Resizing의 과정

10개의 배열에서 10개를 추가해 리사이징을 한다면

20개의 배열을 만들고 기존10개를 카피후  다음데이터를 순차적으로 넣습니다.