데이터가 변경될 때 구조를 변경하는 동적 자료 구조

• 필요에 따라 자료 구조의 크기를 확장
• 서로 다른 값 사이에 동적이고 가변적인 연결을 만드는 것
• etc.

Section 1. 배열의 한계

배열의 한 가지 중요한 한계는 크기와 메모리 레이아웃이 생성 시 고정된다는 점이다.

• 고정된 자료 구조는 데이터에 따라 자료 구조의 크기가 늘어날 수 없다.
• 배열 크기는 배열을 생성할 때 고정되므로 배열을 확장해 더 많은 데이터를 저장하려면 새로운 더 큰 메모리 블록을 만들어야 한다.
  • 분할 상환(amortizing)
  • 두 배로 늘리기(array doubling) : 배열 크기가 확장될 때마다 그 크기를 두 배로 키우는 방식

이미 가득 찬 배열의 중간에 새 값을 삽입하는 경우

• 이전 값을 복사하고 새 블록을 할당.
• 새 값이 들어갈 위치부터 모든 값을 한 칸씩 움직여서 새 값을 위한 공간 비우기
• 새 값 삽입.

ArrayDouble(Array: old_array):
	Integer: length = old_array의 길이
	Array: new_array = 크기가 length * 2인 빈 새로운 배열
	
	Integer: j = 0
	WHILE j < length:
		new_array[j] = old_array[j]
		j = j + 1
	return new_array

Section 2. 포인터와 참조

포인터(어떤 대상이나 장소를 가리키는 존재)

: 컴퓨터 메모리의 주소만 저장하는 변수.

포인터 작업 수행 시, 사용되는 메커니즘은 프로그래밍 언어마다 다르다.