선형 자료 구조 (동적 배열, 연결 리스트)

1. 동적 배열

● 배열의 문제점

1. 처음 배열을 선언할 때 크기를 지정해주어야 한다.

2. 그 크기 이상의 자료를 집어넣을 수 없다.

=> 이 문제를 해결하기 위한 것이 동적배열이다.

● 동적배열의 특징

동적배열의 내부는 배열로 이루어져있기 때문에 배열의 특징을 이어받는다.

배열의 특징 이어받은 것

- 원소들은 메모리의 연속된 위치에 저장

=> 캐시의 효율성과 직결되기 때문에 아주 중요하다.

- 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있음

동적배열이 가지는 다른 추가 특성

- 배열의 크기를 변경하는 resize() 연산이 가능

=> 배열의 크기 N에 비례하는 시간이 걸림

- 배열의 맨 끝에 원소를 추가할 수 있는 append() 연산을 지원

=> 상수 시간이 걸림

C++ 에서의 동적배열은 vector

2. 연결 리스트

● 배열의 문제점

배열 원소들의 순서를 유지하면서 어떤 위치에 원소 삽입, 또는 원소 삭제는 시간이 오래걸린다.

=> 해당 위치 뒤에 있는 원소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야하기 때문

=> 원소의 개수에 선형 비례하는 시간이 걸림

● 연결리스트의 특징

- 어떤 위치에 삽입과 삭제를 상수 시간에 할 수 있게 하는 것이 연결 리스트(Linked List)이다.

=> 배열은 메모리의 연속된 위치에 각 원소들이 저장하는 구조

=> 연결 리스트는 원소들이 메모리에 흩어져 있고 이들이 포인터로 연결되어 있는 구조

- i번째 노드를 찾으려면 리스트의 머리에서부터 하나씩 포인터를 따라가며 다음 노드를 찾아야 한다.

=> i번째 노드를 찾는데 드는 시간은 리스트의 길이에 선형 비례하게 된다.

- 노드들의 순서를 유지하며 새 노드를 삽입하거나 기존 노드를 삭제하는 작업은 포인터만 변경하면 된다.

=> 삽입과 삭제는 각각 상수 시간에 이루어짐

C++ 에서의 연결 리스트는 list

3. 동적 배열 vs 연결 리스트

가장 큰 차이점은 삽입과 삭제 그리고 임의의 원소에 접근하는데 드는 시간

● 동적 배열을 선택해야 할 때

삽입과 삭제를 할 일이 없거나, 배열의 끝에서만 하면 될 경우

● 연결 리스트를 선택해야 할 때

모든 원소들을 순회하며 삽입과 삭제를 할 경우

● 수행 시간 비교