원형 연결 리스트(Cricular Linked List)

 
#pragma once
#include <iostream>
 
using namespace std;
 
typedef int DATA;
 
class Node
{
    friend class List; 
private:
    DATA data; 
    Node *next; 
 
};
 
class List
{
    friend class Node;
private:
    Node *tail;
 
    int numOfData;
 
public:
    void ListInit(List *plist)
    {
        plist->tail = NULL;
        plist->numOfData = 0;
    }
 
    void LInsert(List *plist, DATA data)
    {
        Node *newNode = new Node;
        newNode->data = data;
 
        if (plist->tail == NULL)
        {
            plist->tail = newNode;
            newNode->next = newNode;
        }
 
        else
        {
            newNode->next = plist->tail->next; // 이 세 과정이 tail을 유지시키고, 원형 연결 리스트로 만든다.
            plist->tail->next = newNode;
            plist->tail = newNode;
        
            Node *tmp = plist->tail->next; // 처음을 의미
            Node *tmp_1 = plist->tail->next->next; // 그 다음을 의미
            
            int val = tmp->data; // 그것의 데이터
            int val_1 = tmp_1->data;
            for (int i = 0; i < plist->numOfData; i++)
            {
                for (int j = i; j < plist->numOfData; j++)
                {
                    if (val > val_1)
                    {
                        int temp = val;
                        tmp->data = val_1;
                        tmp_1->data = temp;
 
                        tmp_1 = tmp_1->next;
                        val_1 = tmp_1->data;
                    }
                    else
                    {
                        tmp_1 = tmp_1->next;
                        val_1 = tmp_1->data;
                    }
                }
                tmp = tmp->next;
                val = tmp->data;
                tmp_1 = tmp->next;
                val_1 = tmp_1->data;
            }
 
            
        }
 
 
        (plist->numOfData)++;
    }
 
    DATA LRemove(List *plist)
    {
        if (plist->numOfData == 0)
            return 0;
 
            Node *rpos = plist->tail->next;
            DATA result = plist->tail->data;
            Node *arr = plist->tail->next; // 처음을 보도록
 
            
            while(1)
            {
                if (plist->tail == arr->next) // 끝과 처음의 다음(즉, 끝)이 같을 경우
                {
                    break;
                }
 
                else
                    arr = arr->next;
            }
 
            delete plist->tail;
            plist->tail = arr;
            plist->tail->next = rpos;
 
            (plist->numOfData)--;
            
            return result;
    }
 
    int LCount(List *plist)
    {
        cout << "현재 개수 : " << plist->numOfData << endl;
 
        if (plist->numOfData == 0) return 0;
 
        cout << "처음 ::  " << plist->tail->next->data << endl;
        cout << "끝 :: " << plist->tail->data << endl;
 
        Node *arr = plist->tail->next;
        for (; plist->tail != arr;)
        {
            cout << arr->data <<" ";
            arr = arr->next;
        }
 
        // for문에서 출력 되지 못하는 마지막 값 출력
        cout << arr->data << endl; 
        return 1;
    }
};

앞의 연결 리스트를 이해했다면 원형 연결 리스트 또한 tail->next == NULL이 아니라는 점만 제외하면 대부분이 같다는 것을 느낄 수 있다.

구조체로 변형 시키는 것은 클래스 함수를 다 밖으로 빼고, 변수를 struct로 변형 시킨 후 약간의 부분만 수정하면 된다.

[ 주의 할 코드 구간 ]

이 코드는 삽입을 하는 순간 오름차순 순으로 정렬을 하는 코드이므로 오름차순을 원치 않는다면

위 코드에서 아래 코드 부분을 제거하면 된다.

하지만 이 코드를 분석해보고 포인터의 선택정렬은 일반 변수 선택정렬과 다르다는 것을

 한번 짚고 넘어갈 수 있으면 아주 좋은 경험이 될 것이다.

 

int val = tmp->data; // 그것의 데이터
int val_1 = tmp_1->data;
for (int i = 0; i < plist->numOfData; i++)
{
    for (int j = i; j < plist->numOfData; j++)
    {
        if (val > val_1)
        {
            int temp = val;
            tmp->data = val_1;
            tmp_1->data = temp;
 
            tmp_1 = tmp_1->next;
            val_1 = tmp_1->data;
        }
        
        else
        {
            tmp_1 = tmp_1->next;
            val_1 = tmp_1->data;
        }
    }
 
    tmp = tmp->next;
    val = tmp->data;
    tmp_1 = tmp->next;
    val_1 = tmp_1->data;
}

이 코드에 대한 알고리즘

Node 클래스와 List 클래스를 형성 후 List list;를 선언하여 하나의 list 클래스를 생성한다. 

그리고 list의 tail 포인터와 numOfData를 이용하여 리스트의 위치를 파악하고, 리스트의 개수를 조사한다.

생성자를 이용하지 않고, ListInit를 이용하여 처음 list 클래스를 초기화 시켜주고, 

LInsert를 통해 Node 클래스를 new를 통해 공간을 할당 해주고 그 노드끼리 연결한다.

 tail은 list의 끝을 가리키도록 한다.

그리고 원형으로 만들어주는데 이때 원형이라 함은 plist->tail = newNode; newNode->next = newNode;를 통해 형성한다.

첫 원형의 시작은 아래의 코드에서부터 시작된다.

if (plist->tail == NULL)
{
    plist->tail = newNode;
    newNode->next = newNode;
}

이 코드를 보면 tail이 NULL일때 tail은 newNode를 가리키게 되는데, 

그다음 newNode의 next도 newNode를 가리키게 된다.

그 뒤로 계속 노드를 형성하면 꼬리부분에 newnode를 만들어주면서 tail을 계속 newnode를 가리키게 하고, 원형 연결 리스트를 만들어준다.

// 이 세 과정이 tail을 유지시키고, 원형 연결 리스트로 만든다.

newNode->next = plist->tail->next; 

 plist->tail->next = newNode; 

plist->tail = newNode;

그리고 insert를 할 때마다 포인터를 통해 data를 비교하여 서로의 포인터를 바꾸는 것이 아닌 포인터 속 값만 바꾸는 행위를 취한다.

제거 코드는 rpos, arr 포인터 및 result int형 변수를 이용하여 포인터를 이동시키며 연결리스트에서 빠지는 노드는 메모리 해제를 시킨다.

출력 코드는 numOfData를 이용하여 for(int i = 0 ; i < numOfData; i++)를 이용하여도 되지만

리스트인 만큼 포인터를 이용하여 리스트를 출력하는 알고리즘이다.