이 튜토리얼에서는 C++를 사용하여 배열을 순환 이중 연결 리스트(Circular Doubly Linked List)로 변환하는 방법을 알아보겠습니다.
순환 이중 연결 리스트는 각 노드가 next와 prev 포인터를 모두 가지며, 마지막 노드의 다음 포인터가 다시 첫 번째 노드를 가리키고, 첫 번째 노드의 이전 포인터가 마지막 노드를 가리키는 자료구조입니다. 즉, 리스트 전체가 하나의 원을 이루는 형태입니다.
변환 접근 방식
주어진 배열의 각 요소를 순서대로 순회하면서 다음 과정을 수행합니다.
- 새로운 노드를 생성하고 배열의 요소 값을 저장합니다.
- 첫 번째 요소라면 해당 노드가 시작 노드가 되며, 자기 자신을
next와prev로 가리킵니다. - 그 외의 경우에는 시작 노드의
prev(마지막 노드) 뒤에 새 노드를 삽입한 후, 원형 연결을 유지하도록 포인터를 갱신합니다.
예제 코드
#include<iostream>
using namespace std;
// 이중 연결 리스트의 노드 구조체
struct node{
int data;
struct node *next;
struct node *prev;
};
// 노드 생성
struct node* getNode(){
return ((struct node *)malloc(sizeof(struct node)));
}
// 리스트 출력
int print_list(struct node *temp){
struct node *t = temp;
if(temp == NULL)
return 0;
else {
cout<<"List: ";
while(temp->next != t) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<temp->data;
return 1;
}
}
// 배열을 순환 이중 연결 리스트로 변환
void convert_array(int arr[], int n, struct node **start) {
// 새로운 포인터 선언
struct node *newNode,*temp;
int i;
// 모든 요소를 순회
for(i=0;i<n;i++){
newNode = getNode();
newNode->data = arr[i];
if(i==0) {
*start = newNode;
newNode->prev = *start;
newNode->next = *start;
} else {
// 마지막 노드 찾기
temp = (*start)->prev;
temp->next = newNode;
newNode->next = *start;
newNode->prev = temp;
temp = *start;
temp->prev = newNode;
}
}
}
int main(){
int arr[] = {1,2,3,4,5};
int n = sizeof(arr) / sizeof(arr[0]);
struct node *start = NULL;
convert_array(arr, n, &start);
print_list(start);
return 0;
}실행 결과
List: 1 2 3 4 5
코드 설명
convert_array 함수는 배열과 배열 크기, 그리고 시작 노드의 이중 포인터를 매개변수로 받습니다. 이중 포인터를 사용하는 이유는 함수 내부에서 시작 노드 자체를 변경해야 하기 때문입니다.
- 첫 번째 요소 처리: 새 노드가 시작 노드가 되며, 리스트에 노드가 하나뿐인 상태이므로
next와prev가 모두 자기 자신을 가리켜 순환 구조를 완성합니다. - 이후 요소 처리:
(*start)->prev가 항상 마지막 노드를 가리키므로, 별도의 순회 없이 O(1) 시간에 새 노드를 리스트 끝에 삽입할 수 있습니다. 새 노드의next는 시작 노드를 가리키고, 시작 노드의prev는 새 노드를 가리키도록 갱신하여 원형 구조를 유지합니다.
print_list 함수는 시작 노드부터 순회하며 각 노드의 데이터를 출력합니다. 시작 노드의 next가 다시 시작 노드와 같아지면 모든 노드를 출력한 것이므로 반복을 종료합니다.
이 방식의 시간 복잡도는 배열의 길이를 n이라 할 때 O(n)이며, 공간 복잡도 역시 노드 개수에 비례하여 O(n)입니다.