아래 함수를 구현

void Append_Node(Node** head, Node* newNode)

void Append_Node_T(Node** tail, Node* newNode)

원형 연결 리스트는 일반적인 연결 리스트와 유사하지만, 마지막 노드가 첫 번째 노드를 가리키는 형태의 연결 리스트이다. 따라서 , 마지막 노드가 다음에 첫 번 째 노드가 오고, 첫 번째 노드 이전에 마지막 노드가 있다.

즉 첫 번째 노드만 있어도 자기 자신을 가르켜야 한다.

void Append_Node(Node** head, Node* newNode) {
    if (*head == NULL) { /*현재 헤드가 비어있다면*/
        *head = newNode;
        newNode->link = newNode; /*새로만든 링크를 자기자신을 저장*/
    }
    else {
        Node* tail = *head;
        do
        {
            tail = tail->link;
        } while (tail->link != *head); /*tail다음이 head가 아닐때 까지 */
        tail->link = newNode;
        newNode->link = *head; /*새로운 노드의 링크를 head로 */
    }
}

이렇게 만들면 빅오가 n이 나오게 된다.

빅오가 n도 충분하지만 이것 보다 더 낮은 시간복잡도로 만들 수 있다.

head가 아닌 tail을 사용하는 것이다.

이렇게 하면 while을 사용하지 않고 꼬리에 바로 새로운 노드를 삽입할 수 있다.

void Append_Node_T(Node** tail, Node* newNode) {
    if ((*tail) == NULL) { /*꼬리가 NULL이면 */
        *tail = newNode;
        newNode->link = newNode;
    }
    else {
        newNode->link = (*tail)->link; /*새 노드에 첫 번째 노드 연결 */
        (*tail)->link = newNode; /*꼬리 다음에 새로운 노드를 연결*/
        (*tail) = newNode; /*새 노드를 꼬리로*/
    }
}

이렇게 하면 수행시간을 빅오 1로 줄일 수 있다.

결과

과제에 대한 고찰

저렇게 헤드가 아닌 꼬리를 이용하면 시간 복잡도를 줄 일 수 있는 것을 보고 헤드랑 꼬리를 동시에 사용하면 새로운 노드를 어디 넣는 냐에 따라 두 개를 적절히 사용하면 시간 복잡도를 조금 줄 일 수 있을까하고 고민하게 되었고 이번 과제 또한 일반 연결리스트에 대해 알면 금방 구현 할 수 있었다.