동적 배열

배열의 문제 : 처음에 배열을 선언할 때 배열의 크기를 지정해야 하며, 그 이상의 자료를 집어넣을 수 없다는 점이다. -> 그래서 동적 배열이 고안됨 동적 배열은 대게 언어의 표준 라이브러리에 포함되어 있으므로, 배열의 특성을 그대로 이어받음

배열 특성

1. 원소들은 메모리의 연속된 위치에 저장됨
2. 주어진 위치의 원소를 반환 혹은 변경을 O(1)로 함

동적 배열 특성

1. 배열의 크기를 변경하는 resize 연산이 가능, 배열의 크기 N에 비례하는 시간이 걸림
2. 배열의 맨 끝에 원소 추가하는 append 연산 가능, 상수 시간이 걸림

• 동적 배열의 크기를 바꿔야 할 때는 새 배열을 동적으로 할당받은 뒤, 기존의 원소복사하고 새 배열을 참조
• append는 처음부터 여유분의 메모리를 할당받기 때문에 상수시간에 구현 가능
• 그러나 용량이 다차서 재할당 받을 때는 O(N+M)이 됨
• 재할당 받을 때마다 늘어나는 용량을 현재 원소의 개수에 비례해서 확보
• 결국 o(1)임

연결 리스트

배열 원소들의 순서를 유지하면서 임의의 위치에 원소 삽입, 삭제는 시간이 오래 걸림 - O(N) 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있는 “연결리스트” 고안 연결 리스트에서 i번재 노드를 찾아내려면 리스트의 길이에 선형 비례