[Algorithm] 18. 선형 자료 구조

18.3 연결리스트

연결 리스트 다루기

연결 리스트는 메모리에 연속되어 저장되지 않기 때문에 특정 위치를 값을 찾기 어렵다.

연결 리스트의 i번째 노드를 찾아내려면 어떻게 해야할까?

리스트의 머리에서부터 시작하여 포인터를 따라가며 i번째 노드를 찾아야한다.

i번째 노드를 찾는데 드는 시간은?

리스트의 길이에 선형 비례한다.

새 노드를 삽입하거나 기존 노드를 삭제하는 작업은 어떨까?

노드의 순서가 포인터로 지정되어 있어서, 삽입/삭제 대상이 되는 노드의 이전 노드와 이후 노드의 포인터만을 바꾸면 된다.

연결 리스트의 삽입/삭제 연산에 드는 시간은? 상수시간

표준 라이브러리의 연결 리스트 구현

• C++ STL list
• Java와 C#의 LinkedList

연결 리스트 응용 연산들

• 표준 라이브러리에서는 연결 리스트를 응용할 수 있는 연산들을 잘 지원하지 않는다.

잘라 붙이기 연산

연결리스트에서 다른 리스트를 통째로 삽입하는 것은 원소의 삭제와 삽입을 상수 시간에 하는 것과 동일하다.

// a
lotte [8 -> 8 -> 8 -> 8 -> 5]
lg    [6 -> 6 -> 6 -> 8 -> 5]

// b
lotte [8 -> 8 -> 6 -> 8 -> 8 -> 8 -> 5]
lg    [6 -> 6 -> 5]

연결리스트는 원소의 개수를 리스트 객체에서 유지를 하면서 새 원소를 삽입하거나 삭제할 때 원소의 개수를 갱신한다.

하지만, 잘라 붙이기 연산을 하면 몇개의 원소가 추가되었는지 알 수 없어서 원소의 개수를 갱신할 수가 없다.

자바와 C#의 LinkedList 는 잘라 붙이기 연산을 지원하지 않는 대신, 원소의 개수를 상수 시간에 지원한다.

C++ STL의 list 는 splice() 메서드를 통해 잘라 붙이기 연산을 지원하지만, 리스트의 크기를 선형 시간에 지원한다.

삭제했던 원소 돌려놓기

// node 이전/이후 노드의 포인터를 바꿔서 node를 리스트에서 삭제한다.
// prev -> node -> next
// prev(next)   -> next
// prev         <- next(prev)
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;
}

위 코드에서 deleteNode() 메서드는 연결리스트 노드를 x를 삭제한다.

이 때, node의 이전/이후 노드의 포인터만 변경되고 node에 들어 있는 정보는 변하지 않는다.

따라서, node의 포인터들은 원래 자기가 들어 있던 위치를 알고 있으므로, recoverNode() 처럼 node 파라미터만 알고 있어도 원래 리스트로 돌아갈 수 있다.

이 연산은 언제 유용할까?

조합 탐색에서 연결 리스트의 되돌리기 연산이 유용하게 사용된다.

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

그리고, 재귀 호출이 끝난 후 문제의 상태가 다시 복구된다.