3.1. 동적배열

힙 영역에 저장된 배열

3.1.1. 스택 vs 힙

1. 스택

• 실제 스택프레임에 쌓이는 메모리 공간
• 따라서 실제 스택 프레임의 크기를 알아야 함
• 반드시 고정된 크기의 배열 생성해야 함

2. 힙

• 변수 생성, 소멸시기를 프로그래머가 결정 가능 : 동적 할당
• ex) 파이썬의 리스트

3.1.2. Dynamic Array ADT

1. Array.is_empty() : Boolean

li = []
bool(li) # false : python 에서는 빈 리스트는 거짓을 의미함

2. Array.add_last(element) : 마지막에 원소 추가

• append() : 리스트의 마지막에 원소 추가하는 메서드

li = [1,2,3,4,5]
li.append(6)

3. Array.insert(index, element) : index 위치에 원소 삽입
   -insert(index, element) : 리스트 중간에 원소 추가

li = [1,2,3]
li.insert(1,4) # [1,4,2,3]

4. Array[index] : indexing(해당 인덱스에 위치한 원소 반환)
5. Array.remove_last() : 리스트의 마지막 원소 삭제 후 반환

• pop() : 리스트의 마지막 원소 삭제

li = [1,2,3,4]
li.pop() # 4 반환

6. Array.remove(index) : 인덱스에 위치한 원소 삭제 후 반환

• pop(매개변수) : 매개변수로 인덱스를 받아 해당 위치의 원소 삭제

li = [1,2,3,4]
li.pop(2) # 3 반환

3.2. 인덱싱

• 배열은 메모리상에서 물리적, 선형적으로 이어져 있음

  인덱싱(Indexing) : 배열에서 데이터 접근할 때
  데이터 주소 값 = 배열의 첫 주소값 + (데이터 크기 * 인덱스)

ex) start : arr의 첫 주소값, 데이터 크기 : 4 byte
arr[3] = start + (4*3)
-> 성능 : O(1)

3.3. 동적 배열에서의 삽입, 삭제

3.3.1. 데이터를 배열의 마지막에 삽입, 삭제

• capacity : 배열이 확보한 메모리 공간
• size : 배열의 사이즈(데이터 크기)

1) capacity > size

• 삽입, 삭제 시 성능 : O(1)

2) capacity = size

• 분할 상환 분석
• 충분한 공간 다시 확보 후, 기존 배열 요소를 모두 복사한 뒤 새로운 요소 추가
• 배열이 가득 찬 경우에만 O(n), 그 이전의 모든 연산은 O(1)

3.3.2. 데이터를 배열의 중간에 삽입, 삭제

1) 데이터를 배열 맨 처음에 삽입, 삭제

• 성능 : O(n)
• 이미 있는 모든 요소를 한 칸 씩 뒤(앞)로 미루는 연산 수행 : 데이터 n개에 대하여 n번의 복사 수행