12. 단일 원형 연결리스트

단일 연결리스트는 다음 노드로 이동하게 되면 이전 노드의 포인터값을 저장하지 않는 이상 이전 노드를 참조할 수 없다.

이전 노드를 참조 할 수 있도록 하기 위해 연결리스트의 마지막 노드의 다음 노드는 NULL이 아니라 연결리스트의 첫 노드를 가리키게 된다. 이러면 원형의 모습을 하게 되어 지나친 노드도 다시 방문할 수 있게 된다.

---

단일 원형 연결리스트 구현

노드의 구성은 단일 원형 연결리스트와 다르지 않다.

// 노드에 대한 구조체 정의
typedef struct Node *NodePointer;
typedef struct Node{
    int data;
    NodePointer next;
}Node;

 

 

연결리스트의 노드 삽입, 삭제 함수는 단일 연결리스트와 조금 다르다.

단일 연결리스트에서 마지막 노드가 첫 노드를 가리키는 부분이 추가되어야 한다.

// 새로운 노드를 연결리스트 가장 앞에 삽입
NodePointer Insert_Front(NodePointer head, int data){
    NodePointer temp = head;
    NodePointer New_Node = (NodePointer)malloc(sizeof(Node));
    New_Node -> data = data;
    
    if(!head) // 연결리스트가 비어있는 경우
        head = New_Node;
    else{ // 마지막 노드가 새로운 노드를 가리키게 한다.
        while(temp->next != head) temp = temp->next;
        temp -> next = New_Node;
    }
    New_Node -> next = head;
        
    return New_Node;
}
//새로운 노드를 연결리스트 가장 뒤에 삽입
NodePointer Insert_Back(NodePointer head, int data){
    NodePointer temp = head;
    NodePointer New_Node = (NodePointer)malloc(sizeof(Node));
    New_Node -> data = data;
    
    if(!head) // 연결리스트에 노드가 없다면(가장 첫 노드에 삽입)
        head = New_Node;
    else{ // 연결리스트에 노드가 있다면(가장 끝 노드에 삽입)
        while(temp->next != head) temp = temp -> next;
        temp -> next = New_Node;
    }
    New_Node -> next = head;
    
    return head;
}

단일 연결리스트 삽입 함수와 단일 원형 연결리스트의 삽입 함수를 비교해보자

조건식과 NULL값에 관한 내용이 바뀐 것을 확인할 수 있다.

 

연결리스트를 출력하는 함수 또한 아래와 같다.

// 연결리스트를 처음부터 끝까지 출력
void Print_Node(NodePointer head){
    NodePointer temp = head;
    do{
        printf("%d ", temp -> data);
        temp = temp -> next;
    }while(temp != head);
    
    printf("\n");
}

출력 함수를 보면 처음부터 시작하여 다시 처음으로 돌아왔을 때 출력을 멈춰야 하므로 do while 구문을 사용한다.

 

연결리스트의 노드 삭제 함수는 아래와 같다.

// 연결리스트의 가장 앞 노드를 삭제
NodePointer Delete_Front(NodePointer head){
    NodePointer temp = head;
    if(!head) return head; //삭제할 노드가 없다면 NULL 반환
    
    while(temp->next != head) temp = temp -> next;
    temp -> next = head -> next;
    
    temp = head;
    head = head -> next;
    free(temp);
    return head;
}
// 연결리스트의 가장 뒷 노드를 삭제
NodePointer Delete_Back(NodePointer head){
    NodePointer temp = head;
    if(!head) return head; //삭제할 노드가 없다면 NULL 반환
    
    if(!head->next) { // 삭제할 노드가 첫 노드일 경우
        free(head);
        head = NULL;
    }
    else{ // 삭제할 노드가 마지막 노드일 경우
        while(temp->next->next != head) temp = temp->next;
        free(temp->next);
        temp -> next = head;
    }
    return head;
}

마지막 노드의 포인터 값을 변경해야 하므로 단일 연결리스트에서 한 단계가 추가되었다고 생각하면 된다.

 

단일 원형 연결리스트 또한 단일 연결리스트처럼 직접 코드를 작성해면서 공부하며, 이해가 어려운 경우 그림으로 그려가며 이해하도록 하자. 또한 여러 사람의 다양한 코드를 보면서 자신만의 코드를 정립하는 것을 우선으로 공부하자.