[자료구조] 누구나 아는 배열에 대해서

(00) :: Introduciton

대학교 학부 시절때 공부했던 이론 내용들을 리마인드 하기 위해서 작성된 게시글입니다.

정확하지 않은 내용이 포함되어 있는 경우, 댓글로 남겨주시면 수정할 수 있도록 하겠습니다.

이 게시글은 한 번에 완성되는 게시글이 아니며 내용을 지속적으로 추가할 예정입니다.

 

(01) :: Define a Concept

배열 자료구조는 메모리 상에 원소를 연속하게 배치한 자료구조를 뜻합니다.

---------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | - INDEX
| 2 | 3 | 4 | 1 | 6 | 8 | 4 | 2 | - VALUE
---------------------------------

 

(02) :: Property

배열 구조는 '메모리'상에 원소를 연속하게 배치하고 있는 구조 덕분에 다양한 특성을 갖게됩니다.

#1. O(1)에 K번째 원소를 확인하고 변경할 수 있다.
#2. 추가적으로 소모되는 메모리의 양이 거의 없다. 즉, 오버헤드가 거의 없다고 볼 수 있다.
#3. 캐시 적중률(Cache Hit Rate)이 높다.
#4. 메모리의 연속한 구간을 확보해야 돼서 할당에 제약이 걸린다.

 

 

(03) :: Array, How it works?

배열의 동작은 크게 4가지로 구분할 수 있습니다.

#1. 임의의 위치에 있는 원소를 확인하거나 변경하는 경우 = O(1)
#2. 원소를 끝에 추가하는 경우 = O(1)
#3. 마지막 원소를 제거하는 경우 = O(1)
#4. 임의 위치의 원소를 추가하거나 임의 위치의 원소를 제거하는 경우 = O(N)

#1의 경우 인덱스를 통해 배열의 요소에 접근할 수 있기 때문에 O(1) 가 소요됩니다.

#2의 경우 배열의 맨 끝에 추가하는 것은 길이를 1 증가 시키고 끝에 값을 넣으면 되기 때문에 O(1) 입니다.

#3의 경우 배열의 길이 1 감소 시키면 되기 때문에 O(1) 입니다.

 

#4의 경우 임의의 위치에 원소를 추가해야 하기 때문에 O(N) 입니다.

#1. 배열의 길이 증가
-------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | - INDEX
| 2 | 3 | 4 | 1 | 6 | 8 | 4 | 2 |   | - VALUE
-------------------------------------

#2. 공간 확보를 위해 데이터 밀기
-------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | - INDEX
| 2 | 3 | 4 | X | 1 | 6 | 8 | 4 | 2 | - VALUE
-------------------------------------

#3. 데이터 추가
-------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | - INDEX
| 2 | 3 | 4 | 3 | 1 | 6 | 8 | 4 | 2 | - VALUE
-------------------------------------

위 구조에서 3번 인덱스의 3을 추가하고 싶다면 배열의 길이를 1 증가 시키고, 현재 3번 인덱스의 값인 1부터 7번 인덱스의 값인 2까지 전부 뒤로 밀어야 하기 때문입니다.

이때, 추가하는 위치가 마지막 인덱스에 가까울 수록 밀어야될 요소의 개수가 적기 때문에 소요 시간은 줄어듭니다.

반대로 처음 인덱스와 가까울 수록 소요 시간이 늘어날테지만 평균적으로는 N/2개를 밀어야하므로 O(N) 입니다.

 

(04) :: Array, How to use in Java?

- 자바 API 활용한 사용 방법

- 실제 구현

 

(FF) :: Reference

참고자료는 다음과 같습니다.

# -- Thanks to --
#1 blog.encrypted.gg