1. Array

• Array는 연속적으로 데이터를 저장하는 자료구조로, 거의 모든 데이터를 호환한다. 다만, Array는 데이터를 저장하기 전에도 최초 선언한 크기대로 메모리를 점유(statically allocated)하고 있으며, 이를 임의로 늘릴 수는 없다. 더 큰 Array를 선언 후, 저장하고 있는 데이터를 복사해야한다.

• 이때, 추상적인 데이터의 위치와 메모리에 할당된 위치는 반드시 동일하다. 곧, 첫번째 자료는 메모리에도 첫번째 위치에 할당되어있고, 마지막 자료는 최후미에 할당되어 있다. 그래서 물리적인 할당 위치를 보장하기 위해 최초에 자료형과 배열의 크기를 정해서 선언해주어야 한다.

• 자료형은 최소, 최대 메모리 할당량이 정해져 있다. Java로 예를 들면, int 자료형은 최대 자리수가 설정되어 있는 것을 생각하면 된다. 그래서 배열을 선언하면, 선언한 자료형이 메모리를 최대로 사용할 경우에도 넣을 수 있는 할당량 * 선언한 배열의 크기 만큼 메모리를 처음부터 할당한다.

• 이렇게되면, 첫번째 인덱스는 배열 최초부터 첫번째 값이 할당되어있는 메모리를 쭉 읽고, 두번째 인덱스는 그 다음부터 할당되어 있는 메모리를 쭉 읽어 반환하는 것으로 동작한다.

2. 구성

• 기본적으로 Array는 다음의 기능을 기본적으로 탑재하고 있다.

• 첫번째는 index 접근이다. Array는 데이터를 연속적으로 저장하기 때문에, 기본 index를 0으로 하고, 필요에 따라 index를 입력하면 그로부터 입력한 만큼 떨어진 메모리 자리의 데이터를 직접 접근하여 불러올 수 있다.

• 두번째는 search 기능이다. 특정 데이터가 Array 내부에 존재하는지를 비교를 통해 찾아내는 것으로, 0번 index부터 마지막 index까지 하나 하나 데이터에 접근하여 비교하여 데이터를 찾는다.

• index 접근의 big-o 값은 O(1)이며, search의 값은 O(n)이다.

3. 쓰임새

• Array 그 자체로도 많이 쓰이지만, Array를 기반으로 여러 기능을 덧붙이고 제한하는 것을 통해 다른 자료구조를 구현하는 일에 주로 쓰인다.

부록: 희소행렬

• 기본적으로 행렬의 표현은 2차원 배열로 하는 경우가 많다.

• 이때, 배열 내부의 원소 중 상당한 수의 값이 0인 행렬을 희소행렬이라고 한다.

• 이때, 0은 실제로 메모리에 할당할 값은 없지만, 메모리를 점유하고 있다. 즉, 실질적으로 무의미한 메모리 할당이 많이 일어난다는 의미이다.

• 이 경우, 메모리의 효율적인 활용을 위해 이런 경우 실제로 값을 가지고 있는 부분만을 따로 표현하는 경우가 있다.

• 2차원 배열을 이용하되, 행의 수는 값은 행렬 내부 값을 가진 부분 + 1, 열의 수는 3으로 X * 3의 2차원 배열을 생성한다.

• 이때, 3열에는 실제 값, 1열과 2열에는 각각 값이 위치한 행과 열의 위치를 저장한다. 최초 1행에는 전체 행의 크기, 열의 크기, 값을 가진 위치의 개수로 한다. 이렇게 하면, 메모리를 더 적개 사용하면서 2차원 배열의 계산을 할 수 있다.