[Data Structure] 단순 연결 원형 리스트

단순 연결 원형 리스트 (Singly Linked Circular List)

기존 연결 리스트에서 마지막 노드의 포인터가 첫 번째 노드를 가리키게 하면 된다.

https://www.geeksforgeeks.org/circular-linked-list/

원형 리스트의 마지막 노드 검사

기존 단순 연결 리스트에서는 마지막 노드를 검사하기 위해 포인터가 nullptr인지 검사하면 됐지만, 원형 리스트에서는 포인터가 head인지 검사하면 된다.

원형 리스트의 삽입

기본적인 작동 방식은 단순 연결 리스트와 같으나, 다음 경우에는 따로 처리를 해줘야 한다.

• 리스트의 맨 앞에 삽입하는 경우, 마지막 노드의 포인터가 새로 삽입한 노드를 가리키게 한 후 head로 설정
  • 만약 맨 마지막 노드를 가리키는 rear가 있는 경우, rear의 포인터가 새 노드를 가리키게 설정해주면 O(1)으로 삽입 가능
• 리스트의 맨 뒤에 삽입하는 경우, 새로 삽입한 노드의 포인터가 맨 앞 노드를 가리키게 해야함
  • 만약 맨 마지막 노드를 가리키는 rear가 있는 경우, rear의 포인터가 새 노드를 가리키게 설정하고, rear의 포인터가 새로 삽입한 노드를 가리키게 한 후 rear로 설정하면 O(1)으로 삽입 가능

원형 리스트의 삭제

기존의 단순 연결 리스트와 같으나, 다음 경우에 따로 처리를 해줘야 한다.

• head를 삭제하는 경우 rear의 포인터가 새로운 head를 가리키게 한다.

코드

#include <iostream>

// 노드 클래스
template <typename T>
class Node 
{
public:
    Node(T data)
    {
        this->data = data;
    }

    T data;
    Node<T>* next = nullptr;
};

template <typename T>
class CircularList
{
public:
    // 생성자
    CircularList()
    {
        head = nullptr;
        rear = head;
    }

    // 소멸자
    ~CircularList()
    {
        Node<T>* currNode = head;
        Node<T>* prevNode = nullptr;

        if (currNode == nullptr) return; // 빈 노드인 경우 종료

        // 모든 노드 삭제  
        while (currNode->next != head) // currNode 한 칸 앞까지만 삭제
        {
            prevNode = currNode;
            currNode = currNode->next;
            delete prevNode;
        }

        delete currNode; // currNode 삭제
    }

    // 앞쪽 노드 삽입
    // rear에서 삽입하고 링크 이어주면
    // head에서 추가하고 링크 이어주려고 마지막까지 이동하지 않아도 됨 => O(1)
    void InsertFront(Node<T>* node)
    {
        if (rear)
        {
            node->next = rear->next;
        }
        else // 빈 리스트인 경우
        {
            rear = node;
            rear->next = node; // 자기 자신을 가리키게 
        }

        head = node; // head 설정
    }

    // 뒷쪽 노드 삽입
    void InsertRear(Node<T>* node)
    {
        if (rear)
        {
            node->next = rear->next;
            rear->next = node;
        }
        else // 빈 리스트인 경우
        {
            head = node;
            node->next = node; // 자기 자신 가리키게
        }

        rear = node;
    }

    // value 값을 가지는 노드 삭제
    void Delete(T value)
    {
        if (head == nullptr) // 빈 리스트인 경우
        {
            std::cout << "List is empty\n";
        }
        else if (head->next == nullptr) // head만 있는 경우
        {
            if (head->data == value)
            {
                delete head;
                head = nullptr;
            }
            else
            {
                std::cout << "Cannot find node\n";
                return;
            }

        }
        else // 2개 이상 있는 경우
        {
            if (head->data == value) // head를 지우는 경우
            {
                Node<T>* temp = head;
                head = head->next; // head의 다음 노드를 새로운 head로 설정
                head->next = head; // 자기 자신 가리키게
                delete temp;
                rear->next = head; // rear의 포인터가 새로운 head를 가리키게 함
            }
            else
            {
                Node<T>* findNode = head;
                Node<T>* prevNode = nullptr;

                while (findNode->next != head) // 마지막 노드 한 칸 앞까지 이동
                {
                    if (findNode->data == value) break; // 찾은 경우 break
                    prevNode = findNode;
                    findNode = findNode->next;
                }

                // 마지막 노드에 대해 검사
                if (findNode->data != value) // 찾지 못한 경우
                {
                    std::cout << "Cannot find node\n"; 
                    return;
                }

                if (findNode == rear) // 만약 지우려는 노드가 마지막 노드면
                {
                    rear = prevNode; // 마지막 노드를 prevNode로 설정
                }

                prevNode->next = findNode->next;
                delete findNode; // 노드 삭제
            }
        }
    }

    // Linked List 연결
    void Concatenate(CircularList<T>* list)
    {
        if (head)
        {
            rear->next = list->head;
            rear = list->rear;
        }
        else
        {
            head = list->head;
            rear = list->rear;
        }

        rear->next = head; // 붙인 리스트의 맨 뒤와 앞을 연결

        // 합쳐져 사라진 리스트의 head와 rear를 nullptr로 설정
        list->head = nullptr;
        list->rear = nullptr;
    }

    // Linked List 뒤집기
    void Reverse()
    {
        Node<T>* currNode = head;
        Node<T>* prevNode = nullptr;
        Node<T>* nextNode = nullptr;

        rear = head; // 현재 head -> 뒤집힌 리스트의 rear

        while (currNode->next != head) // rear에 도달할 때까지 반복
        {
            nextNode = currNode->next;
            currNode->next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }
        currNode->next = prevNode; // 마지막 노드 링크 설정

        head = currNode; // 뒤집힌 리스트의 head를 설정
        rear->next = head; // 앞뒤 연결
    }

    // Linked List 출력
    void Print()
    {
        Node<T>* currNode = head;

        while (currNode->next != head)
        {
            std::cout << currNode->data << " ";
            currNode = currNode->next;
        }

        std::cout << currNode->data; // 마지막 노드 출력

        std::cout << "\n";
    }

private:
    Node<T>* head = nullptr;
    Node<T>* rear = head;
};