February 10, 2021 February 12, 2021 February 16, 2021 March 2, 2021

18.1 도입

배열과 같이 일렬로 늘어선 자료들을 저장하기 위한 자료 구조(선형 자료 구조)인 동적배열과 연결 리스트에 대해 다룹니다.

두 자료구조는 배열에서 비효율적이거나 할 수 없는 작업들을 효율적으로 할 수 있도록 도와줍니다.

<aside> 📌 선형 자료 구조는 배열에서 비효율적인 작업을 효율적으로 할 수 있게 한다.

</aside>

18.2 동적 배열

동적 배열은 일반 배열처럼 언어 차원에서 지원되는 기능이 아니라 배열을 이용해 만들어 낸 별도의 자료구조입니다.

따라서 언어의 표준 라이브러리에 포함되어 있습니다.

배열으로 만들었기 때문에 배열의 특징을 이어받습니다.

• 원소들은 메모리의 연속된 위치에 저장됩니다.
• 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있습니다.

동적 배열은 배열과 다른 특성을 추가로 지닙니다.

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

동적 배열은 동적으로 할당받은 배열을 사용합니다. 둘이 같은 의미는 아닙니다.

동적으로 할당받은 배열 독자적으로는 resize(), append()를 하지 않습니다. 단순하게 동적으로 할당을 받은 배열입니다.

반면에 동적 배열은 append() , resize() 연산을 수행합니다.

동적 배열의 크기가 바뀌어야 할 때는 단순하게 새 배열을 동적으로 할당받은 뒤 기존 원소들을 복사하고, 새 배열을 참조하도록 바꿔치기합니다.

따라서 동적 배열 클래스는 배열의 크기와 실제 배열을 가리키는 포인터를 저장하고 있겠죠.

int size;
ElementType* array;

<aside> 📌 동적 배열은 배열을 이용해서 만들었다. 따라서 배열의 특징을 지니고 있다. 배열과 다른 특성을 추가로 지닌다.

</aside>

resize() 연산

배열의 크기를 변경하는 연산입니다.