원형 연결 리스트

앞의 단순 연결리스트와 다르게 원형 연결 리스트는 말 그대로 원형의 모습으로 리스트가 연결되어 있는 것이다.

이는 즉 단순 연결 리스트는 마지막 Node가 가르키는 주소는 NULL값이었지만, 원형 연결리스트는 다시 맨 처음 노드를 가르키게 된다.

헤더파일

#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE 1
#define FALSE 0

typedef int LData;

typedef struct _node
{
   LData data;
   struct _node *next;
} Node;

typedef struct _CLL
{
   Node *tail;
   Node *cur;
   Node *before;
   int numOfData;
} CList;

typedef CList List;

void ListInit(List *plist);
void LInsert(List *plist, LData data);
void LInsertFront(List *plist, LData data);

int LFirst(List *plist, LData *pdata);
int LNext(List *plist, LData *pdata);
LData LRemove(List *plist);
int LCount(List *plist);

#endif

소스파일

#include <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"

void ListInit(List *plist)
{
   plist->tail = NULL;
   plist->before = NULL;
   plist->cur = NULL;
   plist->numOfData = 0;
}

void LInsert(List *plist, LData data)
{
   Node *newNode = (Node *)malloc(sizeof(Node));
   newNode->data = data;

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

   (plist->numOfData)++;
}

void LInsertFront(List *plist, LData data)
{
   Node *newNode = (Node *)malloc(sizeof(Node));
   newNode->data = data;

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

   (plist->numOfData)++;
}

int LFirst(List *plist, LData *pdata)
{
   if (plist->tail == NULL)
   {
      return FALSE;
   }

   plist->before = plist->tail;
   plist->cur = plist->tail->next;

   *pdata = plist->cur->data;

   return TRUE;
}

int LNext(List *plist, LData *pdata)
{
   if (plist->tail->next == NULL)
   {
      return FALSE;
   }

   plist->before = plist->cur;
   plist->cur = plist->cur->next;

   *pdata = plist->cur->data;

   return TRUE;
}

LData LRemove(List *plist)
{
   Node *rpos = plist->cur;
   LData rdata = rpos->data;

   // 삭제할 노드가 tail일 경우
   if (rpos == plist->tail)
   {
      // tail 혼자만 남았을 경우
      if (plist->tail == plist->tail->next)
      {
         plist->tail = NULL;
      }
      else
      {
         plist->tail = plist->before;
      }
   }

   plist->before->next = plist->cur->next;
   plist->cur = plist->before;

   free(rpos);
   (plist->numOfData)--;

   return rdata;
}

int LCount(List *plist)
{
   return plist->numOfData;
}

메인파일

#include <stdio.h>
#include "CLinkedList.h"

int main()
{
   List list;
   int data, i, nodeNum;
   ListInit(&list);

   LInsert(&list, 3);
   LInsert(&list, 4);
   LInsert(&list, 5);
   LInsertFront(&list, 2);
   LInsertFront(&list, 1);

   printf("전체 데이터 수 : %d \n", LCount(&list));

   if (LFirst(&list, &data))
   {
      printf("%d ", data);

      for (i = 0; i < LCount(&list) - 1; i++)
      {
         if (LNext(&list, &data))
         {
            printf("%d ", data);
         }
      }
   }
   printf("\n");

   // 2의 배수 삭제
   nodeNum = LCount(&list);

   if (nodeNum != 0)
   {
      LFirst(&list, &data);
      if (data % 2 == 0)
      {
         LRemove(&list);
      }

      for (i = 0; i < nodeNum - 1; i++)
      {
         LNext(&list, &data);
         if (data % 2 == 0)
         {
            LRemove(&list);
         }
      }
   }

   printf("전체 데이터 수 : %d \n", LCount(&list));

   if (LFirst(&list, &data))
   {
      printf("%d ", data);

      for (i = 0; i < LCount(&list) - 1; i++)
      {
         if (LNext(&list, &data))
         {
            printf("%d ", data);
         }
      }
   }

   return 0;
}

결과

전체 데이터 수 : 5 
1 2 3 4 5
전체 데이터 수 : 3 
1 3 5