배열(array)

배열의 정의

고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 형태로 구성된 선형자료구조

→크기를 변경하려면 새로 배열을 선언하는 수밖에 없다.

배열 특징

cache hit 가능성이 커져서 성능에 큰 도움이 된다?

→ 연속된 메모리 공간에 저장되기 때문에 캐시 지역성(locality)이 증가하여 캐시 적중률이 증가하는 것

overhead가 적다

→ 장점이자 단점인 고정된 크기를 갖는다는 특성은 추가적인 메모리가 필요하지 않다는 것을 의미하고, 이는 overhead가 적다는 것으로 이어진다

메모리 낭비가 발생할 수 있다

→ 크기가 고정되어 있어서, 사용하지 않는 부분이 많을 경우에는 저장 공간의 낭비가 발생할 수 있다

시간복잡도

접근/수정: O(1)

삽입/삭제: O(n)

java에서의 array

arrayList가 array가 아니다!

→ 선형 데이터구조를 정리하다가 arrayList와 array가 헷갈려서 확실히정하고 간다!

int[] array = new int[5];

이런식으로 대괄호로 선언하는 것이 array이다.