선형 자료 구조 -> 자료를 순차적으로 나열한 형태 배열, 연결 리스트, 스택 / 큐 배열 - 사용할 개수를 고정해서 할당 (절대 개수 변경 불가) - 연속된 배열로 배정 받아 사용 장점 : 연속된 배열 단점 : 배열을 추가 / 축소 불가 동적 배열 - 사용할 배열 개수를 유동적으로 계약 - 연속된 배열을 배정 받아 사용 문제점 : 이사 비용은 어떻게? 동적 배열 할당 정책 - 실제로 사용할 배열보다 많이, 여유분을 두고 (대략 1.5 ~ 2배) 할당 - 이사 횟수를 최소화 장점 : 유동적인 계약 (배열 추가 시 이사 횟수 초기화) 단점 : 중간 삽입 / 삭제