연결 리스트란?
연결 리스트(Linked List)는 각 노드가 두 개의 블록으로 구성된 선형 자료구조입니다. 하나의 블록에는 노드의 값(데이터)이 저장되고, 다른 블록에는 다음 노드의 주소가 저장됩니다.
이번 글에서는 각 노드가 리스트 내의 다른 노드를 가리키는 랜덤(random) 포인터를 추가로 포함하고 있는 연결 리스트를 다뤄보겠습니다. 이러한 원본 리스트와 완전히 동일한 새로운 리스트를 만드는 것이 바로 우리의 과제입니다. 랜덤 포인터까지 그대로 복제하여 원본 리스트로부터 새로운 리스트를 만드는 작업을 연결 리스트의 '깊은 복사(Deep Copy)'라고 부릅니다.
예시
입력(Input)
출력(Output):
5-> 2 -> 3 -> 7 ->4 ->
설명: 주어진 연결 리스트의 각 노드 값을 기반으로 새로운 리스트를 구성하고, 원본 리스트의 랜덤 포인터 관계를 새 리스트에도 동일하게 적용하면 위와 같은 결과를 얻을 수 있습니다.
문제 해결 접근 방식
우리에게 주어진 것은 데이터와 랜덤 포인터를 함께 가지고 있는 연결 리스트입니다. 데이터와 랜덤 포인터를 모두 포함하는 복사본을 만들기 위해, 먼저 원본 리스트의 각 노드 바로 뒤에 동일한 값을 가진 새 노드를 삽입합니다. 이렇게 하면 각 노드 뒤에 복제 노드가 하나씩 생기게 됩니다.
노드 삽입이 끝나면, 원본 리스트에서 랜덤 포인터가 가리키는 경로를 확인하고 이를 새로 생성된 노드에도 알맞게 설정해 줍니다.
마지막으로 원본 리스트에서 새로 생성된 노드들을 분리하면, 랜덤 포인터까지 완벽하게 복제된 연결 리스트의 깊은 복사본이 완성됩니다.
알고리즘 단계
- 데이터 필드와 랜덤 노드의 주소를 가리키는 포인터를 가진 연결 리스트를 준비합니다.
- 함수 copyRandomList(listnode* head)는 원본 리스트의 헤드(head) 노드를 입력으로 받아, 리스트의 깊은 복사본을 반환합니다.
- 헤드가 비어 있다면 리스트가 비어 있는 것이므로 헤드를 그대로 반환합니다.
- 원본 리스트의 각 노드 뒤에 동일한 값을 가진 새 노드를 삽입합니다.
- 원본 리스트의 랜덤 포인터를 참조하여 새 노드들의 랜덤 포인터를 설정합니다. 즉, newnode->next = curr->randomPointer 형태로 연결합니다.
- 포인터와 데이터를 모두 갖춘 새 노드들이 준비되면, 리스트를 분리하여 최종 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
struct listnode {
int data;
listnode * next, * random;
listnode(int d) {
data = d;
next = NULL;
random = NULL;
}
};
void print(listnode * head) {
listnode * curr = head;
while (curr) {
cout << curr -> data << " " << curr -> random -> data << endl;
curr = curr -> next;
}
}
listnode * copyRandomList(listnode * head) {
if (!head) {
return head;
}
//원본 리스트의 각 노드 뒤에 같은 값을 가진 새 노드를 삽입합니다.
listnode * curr = head;
while (curr) {
listnode * newHead = new listnode(curr -> data);
newHead -> next = curr -> next;
curr -> next = newHead;
curr = curr -> next -> next;
}
//새로 생성된 노드에 랜덤 포인터를 설정합니다.
curr = head;
while (curr) {
if (curr -> random)
(curr -> next) -> random = (curr -> random) -> next;
curr = curr -> next -> next;
}
//이제 새로 생성된 리스트를 분리합니다.
curr = head;
listnode * result = curr -> next;
listnode * dummyHead = new listnode(-1);
dummyHead -> next = result;
while (curr) {
curr -> next = result -> next;
curr = curr -> next;
if (curr) {
result -> next = curr -> next;
}
result = result -> next;
}
result = dummyHead -> next;
delete dummyHead;
return result;
}
int main() {
listnode * head = new listnode(5);
head -> next = new listnode(6);
head -> next -> next = new listnode(3);
head -> next -> next -> next = new listnode(4);
head -> next -> next -> next -> next = new listnode(2);
head -> random = head -> next -> next;
head -> next -> random = head;
head -> next -> next -> random =
head -> next -> next -> next -> next;
head -> next -> next -> next -> random =
head -> next -> next -> next -> next;
head -> next -> next -> next -> next -> random =
head -> next;
cout << "Original list :" << endl;
print(head);
cout << "Deep Copy of the List:" << endl;
listnode * deep_copyList = copyRandomList(head);
print(deep_copyList);
return 0;
}위 코드를 실행하면 아래와 같은 결과가 출력됩니다.
실행 결과
Original List: 5 3 6 5 3 2 4 2 2 6 Deep Copy of the List: 5 3 6 5 3 2 4 2 2 6
출력 결과에서 확인할 수 있듯이, 깊은 복사된 리스트는 원본 리스트와 노드 값은 물론 랜덤 포인터가 가리키는 대상까지 완전히 동일합니다. 이 방식은 추가 해시 맵 없이 O(1)의 공간만 사용하면서 O(n) 시간 안에 깊은 복사를 수행할 수 있다는 장점이 있습니다.