[자료 구조] 배열

배열은 자료 구조의 하나로, 데이터를 1열로 나열한 것입니다. 앞 절의 리스트와는 대조적으로 데이터에 접근하기는 쉽지만 추가나 삭제에 시간이 걸립니다. 이것은 '[자료 구조] 자료 구조란?'에서 설정한 가나다순의 전화번호부와 비슷한 구조입니다. - 책 알고리즘 도감

 

배열의 개념도

 

배열에서 데이터는 연속된 메모리 영역에 순서대로 저장됩니다.

연속된 영역에 저장돼 있기 때문에 인덱스를 사용해서 메모리의 주소를 계산할 수 있습니다. 따라서 각 데이터에 바로 접근할 수 있습니다. 이것을 '임의 접근(random access)'이라고 합니다. 예를 들어, 'Red'에 접근하고 싶다고 합시다. 이 때 리스트의 경우는 앞에서부터 포인터를 따라 가야 합니다. 하지만 배열의 경우는 a[2]라고 지정하기만 하면 직접 'Red'에 접근할 수 있습니다.

 

 

배열에서 데이터는 연속된 메모리 영역에 순서대로 저장된다.

 

 

 

 

하지만 배열은 임의의 위치에 데이터를 추가, 삭제해야하는 경우에 리스트에 비해 많은 시간이 걸리는 단점이 있습니다. 예를 들어, 'Green'을 두 번째 요소(a[1])에 추가하는 경우를 생각해 봅시다.

배열에서의 데이터 추가

 

 

 

먼저, 배열의 마지막에 데이터를 추가하기 위한 공간을 확보해야 합니다. 그리고 하나씩 데이터를 옆으로 이동합니다. 먼저 'Red'를 이동시킵니다. 그 다음 'Yellow'를 이동시키고 빈 공간에 'Green'을 추가합니다.

Blue와 Yellow사이에 Green추가

 

추가완료

 

 

 

 

 

반대로, 'Green'을 삭제할 때는 요소(여기서는 'Green')를 삭제하고 하나씩 왼쪽으로 옮겨서 빈 자리를 메꿉니다.

배열에서의 데이터 삭제

 

 

 

그리고 마지막으로, 남은 공간을 삭제합니다.

 

 

 

보충

리스트와 배열 모두 데이터를 1열로 나열하는 데이터 구조이지만, 리스트는 접근에 시간이 걸리는 반면에 추가나 삭제가 간단합니다. 반대로, 배열은 접근은 간단하지만 추가나 삭제에 많은 시간이 걸립니다. 무엇을 사용할지는 어떤 작업을 자주하는지를 고려해서 정하면 됩니다.

 

 

참고 - 책 알고리즘 도감