[자료구조] Array

Array

동일한 자료형의 데이터을 일렬로 저장하는 선형 데이터 구조

특징

인덱스를 활용하여 접근이 가능하다.
즉 ramdom access(비순차접근)가 가능하다.

ramdom access란 집합 내의 요소의 주소를 알고 있다면 요소의 개수와 무관하게
모든 요소에 대하여 쉽고 효율적으로 동일한 시간에 접근할 수 있는 방식이다.

반대의 개념으로, Sequential access가 있다.
접근하려면 순차적으로 탐색해야 한다는 개념이다.

인덱스는 0부터 시작하여 순차적으로 증가한다.

논리적 저장 순서와 물리적 저장 순서 가 일치한다.
2차원 배열의 경우 1번행과 2번행의 물리적 주소는 연속적이다.

고정된 크기의 데이터를 연속적으로 저장하기 때문에 메모리를 효율적으로 사용할 수 있다.

삽입/삭제가 O(n)으로 비효율적이다.
이는 배열의 연속적인 물리적 저장방식 때문이다.

삽입을 위해 삽입 대상 뒤의 데이터를 한칸씩 뒤로 밀어야하기 때문이다.
삭제의 경우, 삭제 후 한칸씩 앞으로 밀어야하기 때문이다.