배열(Array)

배열은 메모리 상에 원소를 연속하게 배치한 구조입니다.

1. 장점

다른 자료구조와 달리 원소를 저장하는 것 이외에 추가적으로 소모되는 메모리 양이 거의 없다는 점

2. 단점

반드시 메모리상에 연속한 구간을 잡아야하기 때문에 할당에 다시 제약이 걸린다는 점이 단점.

1. 인덱스에 해당하는 원소를 빠르게 접근해야 할 때

2. 아카이브처럼 데이터를 자주 바꾸거나 확인하는 일 없이 쌓아두고 싶을 때

(만약 데이터의 삽입/삭제가 빈번한 상황이라면 배열은 비효율적)

1. 임의의 위치에 있는 원소를 확인/변경

: 원소가 연속하게 배치되어 있으므로, 임의의 위치의 원소를 O(1)에 확인/변경 가능

2. 임의의 위치에 원소를 추가

: 임의의 위치에 원소를 추가하고 나면, 그 뒤의 원소들을 전부 한 칸씩 밀어야 하므로 O(N)에 추가 가능

3. 임의의 위치에 원소를 제거

: 임의의 위치에 원소를 제거하고 나면, 그 뒤의 원소들을 전부 한 칸씩 당겨야 하므로 O(N)에 제거 가능

4. 원소를 마지막에 추가

: 배열의 길이를 알고 있으니 마지막 위치에 원소를 두기만 하면 되므로 O(1)에 추가 가능

5. 마지막 원소를 제거

: 배열의 길이를 알고 있으니 마지막 원소를 O(1)에 제거 가능

굳이 한 칸씩 당기는 작업이 필요하냐고 묻는다면, 배열의 칸을 빈 채로 두게 되면,

더 이상 메모리 상에 원소가 연속해서 존재하지 않기 때문에 i번째 원소를 O(1)에 찾을 수 없습니다.

공장콧차뇽