[자료구조] 배열(Array) 정리

배열의 개념

배열은 데이터를 저장하고 관리하는 방법 중 하나로 동일한 타입의 데이터를 연속적인 메모리 공간에 저장하는 방법을 사용합니다. 쉽게 이야기하여 배열은 같은 종류의 물건이 담긴 상자가 순서대로 나열되어있는 형태라고 생각할 수 있습니다.

예를 들어, 과일가게 주인은 수박 여러 개 를 상자에 하나씩 담아 번호를 붙여 순서대로 나열해두었습니다.여기서 가게 주인은 상자에 번호를 매길때 첫 번째 상자를 기준으로 첫 번째 상자로 부터 떨어진 거리를 붙여 두었습니다 즉, 첫 번째 상자의 번호는 0, 두 번째 상자의 번호는 1 로 이 같은 방식을 사용하여 여러개의 상자를 나열하였습니다. 

위 같은 번호 방식을 사용하면 두 번째 상자의 번호 '1'은 첫 번째 상자로 부터 1만큼 떨어진 위치에 존재한다는 것을 유추 할 수 있습니다. 만약 손님이 서른 번째 상자에 담겨 있는 수박을 주세요 라고 말을 한다면 가게 주인은 첫 번째 상자로 부터 떨어진 거리인 29가 적혀있는 상자를 찾아야 할 것입니다. 이런 방식으로 가게 주인은 손님이 원하는 상자에 매우 빠르게 접근할 수 있습니다.

이처럼 배열도 위와 같은 방식으로 동작하게 됩니다. 배열에서 수박은 데이터가 되고, 수박이 담긴 각각의 상자는 배열의 요소라고 표현합니다. 마지막으로 상자에 적힌 번호는 배열에서 인덱스라고 표현하고 있습니다. 마찬가지로 배열의 인덱스는 0부터 시작하며 인덱스는 배열의 시작주소로 부터 떨어진 거리를 의미합니다. 배열의 시작주소와 데이터타입의 크기만 알 수 있다면 원하는 위치에 있는 요소를 매우 빠르게 접근할 수 있습니다.

배열의 특징

이전에 배열은 같은 종류의 물건을 담은 상자를 순서대로 나열하는 형태라고 표현하였습니다. 여기서 같은 종류의 물건은 배열에서 동일한 타입의 데이터라고 이해 할 수 있고, 상자를 순서대로 나열한다는 표현은 메모리 공간에 연속적으로 저장된다는 의미로 이해할 수 있습니다. 즉, 동일한 타입의 데이터를 담을 수 있다는 특징과, 연속적인 공간에 저장된다 라는 특징을 가지고 있습니다. 또한 배열은 선언 시에 크기를 지정해주어야 하며 선언 이후에는 크기를 수정할 수 없다는 특징이 있습니다. 

위 와 같은 특징으로 배열의 장단점을 알 수 있습니다. 먼저 고정된 크기로 인해 메모리의 사용량을 예측할 수 있고 관리가 쉬워진다는 장점이 있습니다. 또한 동일한 타입과 연속적인 공간에 저장한다는 특징으로 특정한 요소에 매우 빠르게 접근할 수 있다는 장점이 있습니다. 특정한 요소에 빠르게 접근할 수 있는 이유는 자바에서 기본타입의 데이터를 메모리에 저장할때 데이터 타입의 크기만큼 데이터 블록을 차지하기 때문입니다. 예를 들어 배열의 시작주소가 '1000' 이고 int타입의 데이터를 저장한다고 하였을때 배열의 시작주소 [0]은 '1000'이 되고 두 번째 주소 [1]은 '1004'가 됩니다. int타입이 4byte이기 때문입니다. 즉, 인덱스와 메모리 주소 간의 연산만 수행하면 되므로 매우 빠르게 접근할 수 있게 됩니다.

반대로 단점도 여럿 존재하게 되는데 고정된 크기로 인해 메모리의 낭비 또는 데이터 부족이 발생할 수 있습니다. 
배열에 크기를 너무 크게 설정하게 되면 메모리 낭비가 발생하게 되고 작게 설정하게 되면 데이터가 들어갈 자리가 없어 새로운 배열을 생성해야합니다. 또한 크기가 고정되어있어 배열의 중간에서 추가와 삭제의 동작이 비효율적으로 동작합니다.  이러한 작업을 수행할 때 배열의 모든 요소를 앞 뒤로 한 칸씩 이동해야 하며 이로 인해 시간이 소요되고 성능이 저하 될 수 있습니다.

배열의 시간 복잡도

접근 : 접근이란 특정한 요소에 직접적으로 접근하는데 걸리는 시간을 의미합니다.배열 에서는 배열의 시작주소와 데이터타입의 크기를 이용하여  특정한 요소에 접근할 수 있으며 $O(1)$ 의 시간복잡도를 갖습니다. 

 

검색 : 검색이란 특정한 요소를 검색하기 위해 걸리는 시간을 의미합니다.배열에서 특정한 요소를 검색하기 위해 배열의 길이만큼 요소를 찾아야하므로 $O(n)$의 시간 복잡도를 갖습니다.

 

추가 : 추가란 요소를 자료구조에 추가하는데 걸리는 시간을 의미합니다. 배열의 끝에 요소를 추가할 때는 $O(1)$ 만큼 시간이 소요되며 배열의 중간에 요소를 추가할 때는 O(n) 만큼 시간이 소요됩니다.

 

삭제 : 요소를 자료구조에 삭제하는 걸리는 시간을 의미합니다. 배열에서는 요소를 삭제하는 경우 요소들을 이동시켜야하기 때문에 o(n)의 시간 복잡도를 갖습니다.