도입

일렬로 늘어선 같은 종류의 자료 여러 개를 저장하기 위한 가장 기초적인 자료구조는 배열입니다. 동적 배열과 연결 리스트는 배열과 비슷하지만, 배열에서 비효율적이거나 할 수 없는 작업들을 효율적으로 할 수 있도록 도와줍니다.

동적 배열

배열의 큰 문제 중 하나는 처음에 배열을 선언할 때 배열의 크기를 지정해야 하며, 그 이상의 자료를 집어넣을 수 없다는 점입니다. 이와 같은 문제를 해결하기 위애 고안된 것이 자료의 개수가 변함에 따라 크기가 변경되는 동적 배열입니다. 동적 배열은 일반 배열처럼 언어 차원에서 지원되는 기능이 아니라 배열을 이용해 만들어 낸 별도의 자료 구조입니다. 때문에 동적 배열은 대개 언어 문법이 아니라 언어의 표준 라이브러리에 포함되어 있습니다. 내부적으로 배열을 이용하기 때문에 동적 배열은 배열이 갖는 다음과 같은 특성을 그대로 이어받습니다.

• 원소들은 메모리의 연속된 위치에 저장됩니다.(이 특성은 캐시의 효율성과 직결되기 때문에 중요합니다.)
• 주어진 위치의 원소를 반환하거나 변경하는 동작을 $O(1)$에 할 수 있습니다.

반면 동적 배열은 배열에 비해 다음과 같은 특성을 추가로 지닙니다.

• 배열의 크기를 변경하는 $grow()$ 연산이 가능합니다. 이 동작을 수행하는 데는 배열의 크기 $N$에 비례하는 시간이 걸립니다.
• 주어진 원소를 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 $add()$ 연산을 지원합니다. 이 동작을 수행하는 데는 상수 시간이 걸립니다.

이와 같은 연산들을 구현하기 위해 동적 배열은 동적으로 할당받은 배열을 사용합니다. 동적 배열의 크기가 바뀌어야 할 때는 단순하게 새 배열을 동적으로 할당받은 뒤 기존 원소들을 복사하고, 새 배열을 참조하도록 바꿔치기합니다. 따라서 동적 배열 클래스는 현재 배열의 크기와 동적으로 할당받은 배열을 가리키는 포인터를 다음과 같이 저장하고 있을 겁니다.

위 사진은 자바의 ArrayList 내부의 일부입니다.
새 배열을 할당 받고 기존 자료를 복사하는 데는 배열의 크기에 비례하는 시간이 걸리므로, 이와 같은 방법을 사용하면 $grow()$ 연산을 $O(N)$에 구현한다는 요구 조건을 쉽게 만족시킬 수 있습니다.

자바에서는 $grow()$ 함수로 동적으로 배열을 할당합니다.
$add()$ 함수가 호출될 때마다 $grow()$를 호출하면 $add()$의 수행시간도 선형 시간이 됩니다. 하지만 여유분의 메모리를 미리 할당받아 두는 것으로 상수 시간 안에 수행할 수 있습니다.

$elementData$배열의 공간이 남아있으면 그냥 데이터를 추가하고 가득 차있다면 $grow()$ 함수로 길이가 더 긴 배열을 새로 할당합니다.

동적 배열의 재할당 전략

$add()$ 함수를 호출할 때 가끔 재할당을 위해 선형 시간이 걸립니다. 재할당할 때 새로운 용량을 선택해야 하는데 용량을 작게 설정하면 재할당 연산을 자주 호출하게 되고, 용량을 크게 설정하면 메모리를 낭비하게 됩니다. 자바에서는 이를 해결하기 위해 아래와 같은 함수를 호출합니다.

기본적으로 새로운 용량은 원래 용량의 절반만큼 더한 값으로 설정합니다. 만약 인자가 새로운 용량보다 더 크다면 새로운 용량을 인자만큼 늘려줍니다. 원래 용량에 비례해서 여유분을 확보하는 전략을 사용함으로써 효율적으로 재할당을 합니다.

연결 리스트

배열 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제하는 것은 시간이 오래 걸리는 작업입니다. 이 문제를 해결하기 위해 고안된 자료 구조가 연결 리스트 입니다.
연결 리스트는 배열과 아주 다른 형태를 가지고 있습니다. 배열에서는 메모리의 연속된 위치에 각 원소들이 저장되어 있다면, 연결 리스트는 원소들이 메모리 여기저기 흩어져 있고 각 원소들이 이전과 다음 원소를 가리키는 포인터를 가지고 있는 방식으로 구현됩니다.
연결 리스트의 각 항목은 노드라는 내부클래스로 구현됩니다.

노드만 봐도 삽입, 삭제, 검색을 어떤 식으로 하는지 직관적으로 알 수 있기 때문에 더 설명하지 않겠습니다.

동적 배열과 연결 리스트의 비교

동적 배열과 연결 리스트의 가장 큰 차이점은 삽입과 삭제 그리고 임의의 원소에 접근하는 데 드는 시간입니다. 삽입과 삭제를 할 일이 없거나, 배열의 끝에서만 하면 될 경우에는 동적 배열이 거의 항상 더 좋은 선택입니다. 임의의 원소에 빠르게 접근할 수 있을 뿐더러, 원소들이 메모리에 연속해 배치되어 있다면 점이 CPU 캐시의 효율도 더 높여 주기 때문입니다. 만약 모든 원소들을 순회하며 삽입과 삭제를 한다면 연결 리스트가 좋은 선택입니다.

작업	동적 배열	연결 리스트
이전 원소/다음 원소 찾기	$O(1)$	$O(1)$
맨 뒤에 원소 추가/삭제하기	$O(1)$	$O(1)$
맨 뒤 이외의 위치에 원소 추가/삭제하기	$O(n)$	$O(1)$
임의의 위치의 원소 찾기	$O(1)$	$O(n)$
크기 구하기	$O(1)$	$O(1)$

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)