개요
배열(Array)이란 프로그래밍 하는 사람이면 모르는 사람이 없을 자료구조이다.
동일한 타입의 요소들을 연속된 메모리 공간에 순서대로 저장한 것을 배열이라고 한다. 칸이 여러 개 달린 서랍장을 생각하면 좋다.
특징
크기가 고정되어 있다.
항상 처음에 선언했던 크기를 가진다. 중간에 늘리거나 줄일 수 없는데, 그 이유는 배열이 만들어질 때 [입력한 타입의 크기*배열 길이] 만큼의 용량을 통짜로 확보하기 때문이다.
4byte짜리 int가 10개 들어가는 배열을 생성하면 그 배열은 총 40byte의 길이를 가지게 된다. 여기서 크기를 늘려버리면 다른 변수가 차지하고 있는 공간을 침범하게 될 수 있다는 문제가 생긴다. 그렇기에 배열의 크기를 조정하려면 새로 만드는 수밖에 없다.
원하는 위치의 요소로 쉽게 접근할 수 있다.
arr[3], arr[x] 처럼, 숫자만 넣으면 간편하게 배열의 특정 위치에 접근할 수 있다. 이게 가능한 이유는 위에도 설명했듯 배열이 고정된 크기를 가지고 있기 때문이다. 프로그램은 배열의 처음에서 시작해, 숫자값만큼 건너뛴 값을 읽기만 하면 된다.
예를 들어 int형 배열의 5번째 값을 읽도록 시킨다면, 배열의 시작에서 4byte만큼 4번 건너뛴 다음 4byte의 길이를 읽게되는 것이다(그렇기에 arr[4]라고 쓰게 된다). 여기서 'n번째'를 배열의 인덱스라고 부른다.
클래스 배열의 경우 더 복잡한데, 여기저기에 흩어져 있는 객체의 주소만 배열에 저장해서 사용한다. 이걸 알려면 포인터를 공부하면 좋다...
동일한 데이터 타입을 사용한다.
설명은 생략한다!
성능
배열을 사용한 연산으로는 접근, 삽입/삭제, 탐색, 정렬 정도가 있다.
접근: 배열에서 접근하는 방법은 arr[n] 밖에 없다. 즉, 거칠 것이 없으므로 매우 빠르다. 따라서 O(1)의 시간 복잡도를 가진다.
삽입/삭제: 배열 내 요소의 삽입이나 삭제는 말 그대로 그 자리를 데이터로 채우거나 비우는 것만 수행하게 된다. 배열의 크기가 변화하거나 하지 않기 때문이다.
다만 배열 사이에다가 값을 삽입/삭제하고 뒤의 요소들을 한 칸씩 밀거나 당기고 싶을 때가 있다. 이렇게 반복 연산을 수행하게 되면 시간 복잡도가 O(n)까지 늘어나게 된다.
탐색: 배열에서 특정 요소를 찾는 방법은 반복문을 돌려 하나하나 찾아나가는 수밖에 없다. 나쁜 경우 배열의 마지막에서 원하는 요소를 찾을 수도 있게 되므로 시간 복잡도는 O(n)에 수렴한다.
정렬: 배열을 정렬하는 알고리즘이 많다. 다만 아무리 효율적인 알고리즘을 사용하더라도 O(n log n)보다 빠를 수 없다. 버블 정렬이나 삽입 정렬을 사용하면 O(n^2)까지 시간 복잡도가 늘어난다. 두 정렬 알고리즘은 이중 반복문을 쓰기 때문.
어떤 때에 쓰이나
데이터를 순차적으로 접근해야 할 때 배열을 사용할 수 있다.
행렬이나 다차원 배열을 구현하고자 할 때에도 사용할 수 있다.
여러 자료구조의 기반으로써 사용할 수 있다. 당장 스택이나 큐도 배열로 구현한다.(연결 리스트를 쓰는 경우도 많지만...)
