선형 자료구조

<동적 배열>

c++의 vector를 떠올리면 된다. 내부적으론 모두 정적 배열로 구현돼 있다.

 

append()를 할 때 이미 배열이 꽉 차있으면 동적 배열의 크기를 다시 할당해야 한다. 이는 현재 들어있는 원소수에 비례하는 시간이 필요하다.

 

이 부분을 최적화하지 않는다면 동적배열의 자료의 추가/제거 시간은 선형시간이다.

 

하지만 크기를 다시 할당할때 현재 있는 원소수*2로 할당한다면 평균 O(1)에 가능하다.

 

<연결리스트>

일반적인 양방향리스트의 구현

struct listNode{
	int element;
    listNode * next, prev;
}    

 

삭제와 undo - knuth의 dancing link, 조합탐색, UI의 되돌리기에서 쓰임

void deleteNode(listNode* node){
	node->prev->next = node->next;
    node->next->prev = node->prev;
}
void recoverNode(listNode* node){
	node->prev->next = node;
    node->next->prev = node;
}