CircularList 구현

오늘은 원형리스트(circularList)에 대해서 정리해보겠습니다.

일반적으로 단일리스트와 다르게 원형 리스트는 맨마지막 노드의 링크가 NULL이 아니라 맨 처음 노드와 연결되어 있습니다.

원형리스트의 첫 번째 노드의 위치 값(position)은 0이며, 마지막 노드의 위치의 인덱스는 CurrentElementCount -1 입니다. 

그러면 어떻게 원형리스트를 순환하면서 이게 첫번째인지, 마지막 노드인지 알수 있을까요?

이런 문제를 해결하기 위해서 HeaderNode가 하나 존재합니다.

즉, pPreNode == HeaderNode->link 

현재 찾고 있는 노드와 헤더노드와 가르키는 곳이 동일하다면  pPreNode는 현재 마지막 노드에 있다는 것을 알 수 있습니다. 

이번 원형 리스트 또한 분할 컴파일을 실시하였습니다.

circularlist.h

1 #ifndef _CIRCULARLIST_ 2 #define _CIRCULARLIST_ 3 4 typedef struct CircularListNodeType 5 { 6 int data; 7 CircularListNodeType* pLink; 8 }CircularListNode; 9 10 typedef struct CircularListType 11 { 12 int currentElementCount; 13 CircularListNode* pLink; 14 }CircularList; 15 16 CircularList* createCircularList(); 17 void deleteCircularList(CircularList* pList); 18 int addCLElement(CircularList* pList, int position, CircularListNode element); 19 int removeCLElement(CircularList* pList, int position); 20 void clearCircularList(CircularList* pList); 21 int getCircularListLength(CircularList* pList); 22 CircularListNode* getCLElement(CircularList* pList, int position); 23 void displayCircularList(CircularList* pList); 24 25 26 #endif 27 28 #ifndef _COMMON_LIST_DEF_ 29 #define _COMMON_LIST_DEF_ 30 31 #define TRUE 1 32 #define FALSE 0 33  

34 #endif

헤더파일 선언 입니다. 기본적인것들로만 구성되어 있습니다. 다만 분할컴파일때문에 #ifndef로 한번만 컴파일 되게 했습니다.

circularlist.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Circularlist.h"

CircularList* createCircularList()
{
    CircularList* pReturn = NULL;

    pReturn = (CircularList*)malloc(sizeof(CircularList));

    if(pReturn != NULL)
    {
        memset(pReturn , 0, sizeof(CircularList));
    }
    else
    {
        printf("?޸??? ?Ҵ? ?�?, createCircularList()\n");
        return NULL;
    }
    return pReturn;
}

int addCLElement(CircularList* pList, int position, CircularListNode element)
{
    int ret = FALSE;
    CircularListNode* pNewNode = NULL;
    CircularListNode* pPreNode = NULL;
    CircularListNode* pLastNode = NULL;
    int i = 0;

    if(pList != NULL)
    {
        if(position >= 0 && position <= pList->currentElementCount)
        {
            pNewNode = (CircularListNode*) malloc(sizeof(CircularListNode));
            if(pNewNode == NULL)
            {
                printf("pNewNode ?޸??? ?Ҵ? ?�? , addCLElement()\n");
                return ret;
            }
            *pNewNode = element;
            pNewNode ->pLink = NULL;

            if(position == 0)
            {
                //headNode?? NULL?? ????(??, ?? ó�?? ?ִ? ????)
                if(pList->currentElementCount == 0)
                {
                    pList->pLink = pNewNode;
                    pNewNode->pLink = pNewNode;
                }
                else
                {
                    pLastNode = pList->pLink;

                    while(pLastNode->pLink != pList->pLink)
                    {
                        pLastNode = pLastNode->pLink;
                    }
                    pList->pLink = pNewNode;
                    pNewNode ->pLink = pLastNode->pLink;
                    pLastNode ->pLink = pNewNode;
                }
            }
            else
            {
                pPreNode = pList->pLink;
                for(i = 0; i<position-1; i++)
                {
                    pPreNode = pPreNode->pLink;
                }
                pNewNode ->pLink = pPreNode->pLink;
                pPreNode ->pLink = pNewNode;

            }
            pList->currentElementCount++;
            ret = TRUE;

        }
        else
        {
            printf("position error addCLElement()\n");
        }

    }

    return ret;
}
int removeCLElement(CircularList* pList, int position)
{
    int ret = FALSE;
    int arraycount = 0;
    int i = 0;
    CircularListNode* pPreNode = NULL;
    CircularListNode* pDelNode = NULL;
    CircularListNode* pLastNode = NULL;

    if(pList != NULL)
    {
        arraycount = getCircularListLength(pList);
        if(position >= 0 && position < arraycount) 
        {
            if(position == 0)
            {
                pDelNode = pList->pLink;
                if(arraycount == 1)
                {
                    free(pDelNode);
                    pList->pLink = NULL;
                }
                else
                {
                    pLastNode = pList->pLink;
                    while(pLastNode->pLink != pList->pLink)
                    {
                        pLastNode = pLastNode->pLink;
                    }
                    pLastNode->pLink = pDelNode->pLink;
                    pList->pLink = pDelNode->pLink;
                    free(pDelNode);
                }
            }
            else
            {
                pPreNode = pList->pLink;
                for(i=0; i<position-1; i++)
                {
                    pPreNode = pPreNode->pLink;
                }
                pDelNode = pPreNode->pLink;
                pPreNode->pLink = pDelNode->pLink;
                free(pDelNode);
            }
            pList->currentElementCount--;
            ret = TRUE;
        }
        else
        {
            printf("index error ,  removeCLElement()\n");
        }
    }
    return ret;
}
void deleteCircularList(CircularList* pList)
{
    int i =0;
    if(pList != NULL)
    {
        clearCircularList(pList);
        free(pList);
    }
}
void clearCircularList(CircularList* pList)
{
    if(pList!=NULL)
    {
        while(pList->currentElementCount > 0)
        {
            removeCLElement(pList, 0);
        }
    }
}
int getCircularListLength(CircularList* pList)
{
    int ret;
    if(pList!=NULL)
    {
        ret  = pList->currentElementCount;
    }
    return ret;

}
CircularListNode* getCLElement(CircularList* pList, int position)
{
    int i =0;
    CircularListNode* pNode = NULL;

    if(pList!=NULL)
    {
        if(position >= 0 && position < pList->currentElementCount)
        {
            pNode = pList->pLink;
            for(i = 0; i<position; i++){
                pNode = pNode->pLink;
            }
        }
    }
    return pNode;
}
void displayCircularList(CircularList* pList)
{
    int i =0; 
    if(pList!=NULL)
    {
        printf("current element count : %d\n", pList->currentElementCount);
        for(i = 0; i<pList->currentElementCount; i++)
        {
            printf("[%d], %d\n", i, getCLElement(pList, i)->data);
        }
    }
    else
    {
        printf("not element \n");
    } 

}

모르시면 댓글로 질문을~

main.cpp

#include <stdio.h>

#include <stdlib.h>
#include "Circularlist.h"

int main()
{
    int i =0; 
    int arraycount = 0;
    CircularList *pList = NULL;
    CircularListNode * pValue = NULL;
    CircularListNode node;

    pList = createCircularList();

    if(pList != NULL)
    {
        node.data = 1;
        addCLElement(pList , 0, node);

        node.data = 3;
        addCLElement(pList , 1, node);

        node.data = 5;
        addCLElement(pList , 2, node);

        arraycount = getCircularListLength(pList);

        for(i = 0; i<arraycount; i++)
        {
            pValue = getCLElement(pList, i);

            printf("position[%d]- %d\n", i, pValue->data);
        }
    }
    return 0;
}