1. 배열

자료구조는 연속방식과 연결 방식으로 나뉜다. 배열은 이 중에서 연속방식의 가장 기본이 되는 자료형이다. 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말하다. 한번 생성한 배열은 크기를 변경하지 못하는 것이 일반적이다. 자바에서는 ArrayList가 그 기능을 수행한다.

2. 메모리

int 형태의 배열을 하나 선언하면, 공간 하나를 4바이트로 사용한다. 1바이트가 증가할 때마다 주소가 1씩 증가한다. 이 주소 덕분에 모든 배열에 대한 탐색은 O(1) 안에 가능하다. 배열의 4번째 값에 접근하고 싶다면 (4-1) X 4 = 12로 0 X 00에서 12만큼 증가한 16진수 값은 0 X 0C가 되어 한번의 계산만으로 무조건 배열을 탐색할 수 있다.

32비트 운영체제에서는 최대 메모리가 4GB여서 부족한 면이 있었다. 하지만 64비트 운영체제가 개발되면서 그 최대치가 기하급수적으로 증가하여 1,677,721,600GB가 되었다. 지금 보통 16GB 램을 사용하며 최대로 쓰이고 있는 메모리 크기가 몇 안되는 컴퓨터들이 쓰는 2TB정도라는 것을 생각하면, 적어도 당분간은 메모리 최대치를 걱정할 일이 없게 되었다.

현재 메모리가 640KB면 컴퓨터를 키는 것을 걱정해야 하지만, 빌 게이츠가 과거에 램 용량은 640KB면 충분하다고 말 했던 것이 지금 웃음거리가 된 것 처럼, 머지 않아 수만, 수십만 기가도 상상할 수 없을 정도로 적다고 느끼게 될 것이다.

3. 동적 배열

파이썬을 비롯한 많은 프로그래밍 언어들은 정적 배열이 아닌 동적 배열을 지원한다. 미리 초기 값을 적게 잡은 뒤, 크기가 늘어남에 따라 늘려주고 복사하는 형태이다. 보통 2배씩 늘리는 경우가 있는데 이를 더블링이라고 부르기도 한다.

파이썬에서는 0, 4, 8, 16 순으로 배열의 크기가 늘어난다. 하지만, 2배로 늘어났던 것이 일정 크기를 넘어가면 약 1.13배로 그 폭이 줄어드는 형태가 된다. 이를 재할당 비율: 그로스팩터라고 한다.