1. 선형자료구조 - 연결리스트(Linked List)

연결리스트는 원소들이 메모리 여기저기 흩어져 있고 각 원소들이 이전과 다음 원소를 가리키는 포인터를 가지고 있는 방식으로 구현된다.

각 원소들이 이전과 다음 원소들에 대한 정보를 가지고 있으므로 

특정 위치에서의 원소 삽입과 삭제를 상수 시간 내에 수행 할 수 있다.

배열의 경우 특정 위치에 원소를 삽입하거나 삭제하기 위해서는 삽입/삭제 후 해당 위치 뒤의 원소들을 하나씩 앞 또는 뒤로 이동시켜야 하기 때문에 선형시간 O(N) 이 걸리는 것과 비교해 큰 차이가 난다.

연결리스트는 다음과 같은 노드 구조체를 사용해 구현할 수 있다.

여기서 노드는 원소와 포인터들의 집합이다.

struct ListNode{

int element;  // 담고 있는 원소

ListNode *prev, *next; // 이전 노드 , 다음 노드의 포인터

};

연결리스트는 메모리 여기저기에 노드들이 흩어져 있기 때문에 특정 위치의 값을 찾기가 쉽지 않다.

연결리스트에서 i번째 노드를 찾아내려면 하나씩 포인터를 따라가며 찾아야한다. 

즉, i번째 노드를 찾는 데 O(N) 의 시간이 걸리게 된다.

특정 노드 삭제와 복구

연결리스트의 경우 한번 삭제했던 원소를 쉽게 돌려놓을 수 있다는 것이 장점이다.

노드를 삭제할 때 이전/이후 노드의 포인터를 변경할 뿐, 해당 노드의 정보는 바뀌지 않기 때문이다.

삭제 되었던 노드는 원래 자기가 들어가 있던 위치를 알고 있기 때문에 원래 리스트에 쉽게 다시 삽입 할 수 있다.

다만 이 방법은 이전 노드나 이후 노드가 삭제된 상태에서 수행하면 리스트를 망가뜨릴수 있기 때문에 

항상 삭제한 순서의 반대로 복구 해야 한다.

// node 이전/이후 노드의 포인터를 바꿔서 node를 리스트에서 삭제한다.

void deleteNode(ListNode* node){

node->prev->next = node->next;

node->next->prev = node->prev;

}

// node 이전/이후 노드의 포인터를 바꿔서 자기 자신을 다시 리스트에 삽입한다.

void recoverNode(ListNode* node){

node->prev->next = node;

node->next->prev = node;

}

이 연산은 프로그램에서 되돌리기(undo) 연산을 지원하는데 유용하게 쓸 수 있다.

조합 탐색 알고리즘에서 답의 한 조각을 만들고, 현재의 상태를 갱신한 뒤 나머지를 재귀 호출로 해결하게 된다.

재귀 호출이 끝난 뒤 문제의 상태는 다시 복구되어야 하는데 

이때 연결리스트로 문제의 현재 상태를 표현하면 되돌리기 연산을 효율적으로 할 수 있다.

동적 배열과 연결 리스트의 비교

동적 배열과 연결리스트의 가장 큰 차이점은 삽입과 삭제, 임의의 원소에 접근하는데 걸리는 시간이다.

배열의 끝이 아닌 특정위치에 삽입과 삭제를 할 일이 없는 경우에는 동적배열이 거의 항상 좋은 선택이다.

임의의 원소에 빠르게 접근 할 수 있고, 원소들이 메모리에 연속해 배치되어 있기 때문에 CPU 캐시의 효율도 더 높여주기 때문이다.

연결리스트는 크기를 쉽게 알 수 없기 때문에 원소의 개수를 리스트 객체에서 유지하면서 새 원소를 삽입하거나 삭제할 때마다 갱신해준다.

그렇지 않는 경우는 전체 리스트를 다 탐색해야 하기 때문에 리스트의 크기를 구하려면 선형시간 O(N) 이 걸리게 된다.