원형 연결 리스트(CircleLinkedList)

원형 연결 리스트(CircleLinkedList)

: 단일 연결리스트와 거의 동일해 보이지만, 마지막 노드가 NULL이 아닌 첫 번째 노드(head가 가리키는 노드)를 가리킨다

 

단순 연결리스트와 원형 연결리스트 비교

단순 연결 리스트

 

원형 연결 리스트

원형연결리스트의 장점

단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수(head포인터와 tail포인터)를 각각 두지 않아도,

하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드 추가 가능

 

지금까지의 (더미노드 포함)단일 연결리스트에서는

head 포인터를 통하여 새로운 노드를 추가하는 방식이었음

이번에는 tail포인터만으로 머리와 꼬리 둘다에 노드를 추가해볼 것

 

 

꼬리를 가리키는 포인터 변수는 tail

머리를 가리키는 포인터 변수는 tail -> next

 

tail포인터만을 사용하여 머리와 꼬리를 동시에 가리키는 원형 연결 리스트 구현하기

 

원형 연결리스트의 헤더파일

#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE    1
#define FALSE    0

typedef int Data;

typedef struct _node
{
    Data 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, Data data); //꼬리에 노드 추가
void LInsertFront(List * plist, Data data); //머리에 노드 추가

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

#endif

 

 

꼬리를 가리키는 포인터 변수는 tail

머리를 가리키는 포인터 변수는 tail -> next

원형 연결리스트의 구현부

 

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

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

void LInsertFront(List * plist, Data data){
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode -> data = data;
    newNode -> next = NULL;
    
    //처음 추가된 노드라면 그 자체로
    if(plist -> tail == NULL)
    {
        plist -> tail = newNode; //꼬리이자
        plist -> tail -> next = newNode; //머리임. tail -> next는 머리(head)를 가리키는 포인터 변수다
    }
   
    else //2번째 이후의 노드라면 머리로 연결한다.
    {
        newNode -> next = plist -> tail -> next; //새로운 데이터에 기존에 맨앞 데이터(머리 포인터가 가리키는 값)를 next로 연결
        plist -> tail -> next = newNode; //머리 포인터(tail -> next) 변경
    }
    
    (plist -> numOfData)++;
}

void LInsertRear(List * plist, Data data){
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode -> data = data;
    newNode -> next = NULL;
    
    //처음 추가된 노드라면 그 자체로
    if(plist -> tail == NULL)
    {
        plist -> tail = newNode; //꼬리이자
        plist -> tail -> next = newNode; //머리임. tail -> next는 머리(head)를 가리키는 포인터 변수다
    }
    
    //2번째 이후의 노드라면 -> 머리(tail -> next)가 아닌 꼬리(tail)로 연결할때
    else{
        newNode -> next = plist -> tail -> next; //새노드가 이제 마지막 데이터이므로 head 데이터로 next 연결
        plist ->tail -> next = newNode;
        plist -> tail = newNode; //⭐️tail 위치 변경!!(새로운 마지막 데이터이기 때문)
    }
  
    (plist -> numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
    if(plist -> tail == NULL)
    {
        printf("저장된 노드가 없습니다.\n");
        return FALSE;
    }
    plist -> before = plist -> tail; //before은 꼬리
    plist -> cur = plist -> tail -> next; //cur이 머리(1번째 데이터)

    *pdata = plist -> cur -> data;

    return TRUE;
}

int LNext(List * plist, Data * pdata)
{
    if(plist -> cur -> next == NULL)
    {
        printf("더이상 저장된 노드가 없습니다.\n");
        return FALSE;
    }
    plist -> before = plist -> cur; //before포인터는 cur의 한칸 이전이기에 cur포인터의 주소값을 따라받음
    plist -> cur = plist -> cur -> next;

    *pdata = plist -> cur -> data;
    
    return TRUE;
}

Data LRemove(List * plist)
{
    Node * delNode = plist -> cur;
    Data removeData = delNode -> data;

    if(delNode == plist -> tail) //⭐️삭제 대상이 tail이라면?
    {
        if(plist -> tail == plist -> tail -> next) //⭐️그게 마지막 남은 노드라면?
            plist -> tail = NULL;
        else
            plist -> tail = plist -> before; //⭐️tail포인터를 tail이전 데이터로 변경
    }

    //삭제 대상이 tail이 아니라면
    else {
        //⭐️삭제할 데이터의 이전데이터와 삭제할데이터의 다음데이터 연결
        plist -> before -> next = plist -> cur -> next;
        //⭐️cur노드 위치 변경(why? 삭제데이터의 다음 데이터는 참조하지 않았음을 표시하기 위함)
        plist -> cur = plist -> before; 
    }

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

    return removeData;
}

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

 

원형 연결리스트를 활용하는 main 함수

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

int main()
{

    // 원형 연결리스트 생성 및 초기화
    List list;
    int data, i, nodeNum;
    ListInit(&list);

    //리스트에 5개의 데이터 저장
    LInsertRear(&list, 3);
    LInsertRear(&list, 4);
    LInsertRear(&list, 5);
    LInsertFront(&list, 2);
    LInsertFront(&list, 1);
    

    //리스트에 저장된 데이터 연속 3회 출력
    if(LFirst(&list, &data))
    {
        printf("%d ", data);
        
        for(i=0; i<LCount(&list)*3-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);
        }
    }

    //전체 데이터 1회 출력
    if(LFirst(&list, &data))
    {
        printf("%d ", data);
        
        for(i=0; i<LCount(&list)-1; i++)
        {
            if(LNext(&list, &data))
                printf("%d ", data);
        }
    }
    return 0;
}