선형 자료 구조

기존 배열

- 처음 배열 선언시, 배열 크기 지정 해야함

- 지정 된 크기 이상으로 할당X

 

==>

동적배열!!(Dynamic Array)

: 자료의 개수가 변함에 따라 크기 변경

- 배열을 이요해 만들어 낸 별도의 자료 구조

 

기존 배열의 특성을 이어 받은 동적 배열

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

2. 주어진 위치의 원소 반환 및 변경 동작 -> O(1)

 

+ 동적배열은

1. 배열 크기 변경 가능 -> 시간은 배열 크기에 비례

2. 배열의 맨 끝에 원소 추가 -> 상수시간

 

동적 배열 구현하기

step1. 새 배열 동적으로 할당받기

step2. 기존 원소들 복사

step3. 새 배열 참조하도록 바꿔치기

 

 

// 용량 꽉 차면 재할당 받기

if(size == capacity)

{

   // 용량 M만큼 늘리고 새 배열 할당받기

   int newCapacity = capacity + M;

   int* newArray = new int[newCapacity];

   

   // 기존 자료 복사

   for(int i = 0; i < size; i++)

      newArray[i] = array[i];

 

   // 기존 배열 삭제 & 새 배열로 바꾸기

   if(array) delete [] array;

   array = newArray;

   capacity = newCapacity;

}

// 배열 끝에 새 원소 삽입

array[size++] = newValue;

 

 

문제점: 배열 원소들의 순서를 유지하면서 임의의 위치에 원소 삽입하거나, 삭제하는 것은 시간이 오래 걸린다.

연결 리스트!!!!!

: 원소들이 메모리 여기저기 흩어져 있고, 각 원소들이 prev,next 원소를 가리키는 포인터 가지고 있다

node(element, *prev, *next)

 

-> 삽입 or 삭제할 노드의 prev, next 포인터만 바꾸면 가능!