Chap 05. 원형 연결 리스트

원형 연결 리스트란 기존의 연결 리스트에서 NULL을 가르키던 마지막 노드가 첫 번째 노드를 가르키도록 한 연결 리스트다.

원형 연결 리스트의 장점은 기존의 연결 리스트는 head, tail 두 포인터가 필요했지만 원형 연결 리스트는 하나의 포인터만 있어도 head 또는 tail에 노드를 추가할수 있다. (tail이 마지막 노드를 가르키도록 하면) 

 

원형 리스트에서는 최초에 리스트에 아무것도 없을때 tail은 NULL을 가르킨다. 

tail은 항상 마지막 노드를 가르키도록 한다. 

이 상황에서 첫 번째 노드가 추가된다면 tail은 새 노드를 가르키고, 새 노드는 자기자신을 가르켜야 한다. (첫 노드는 자기 자신이 머리이자 꼬리) 

---

 

원형 리스트는 tail과 head의 구분이 의미 없다. (하나만 있으면 된다.)

tail이 가르키는 노드의 다음 노드가 리스트의 첫 부분이므로.

tail에 노드 추가하는 LInsertFront()

// tail에 노드 추가
void LInsertFront(List *plist, Data data)
{
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;

    // tail이 NULL을 가르키고 있다면 리스트 empty
    if(plist->tail == NULL)
    {
        plist->tail = newNode;
        newNode->next = newNode;
    }
    else
    {
        // 새 노드가 기존의 첫 노드 가르키도록
        newNode->next = plist->tail->next;
        // tail이 가르키던 노드 즉 마지막 노드가 새 노드 즉 첫 노드 가르키도록
        plist->tail->next = newNode;
    }
    (plist->numOfData)++;
}

head에 노드 추가하는 LInsert()

void LInsert(List *plist, Data 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; // LInsertFront와의 유일한 차이점
    }
    (plist->numOfData)++;
}

두 함수의 유일한 차이점은 LInsert() 함수의 tail이 새노드를 가르키도록 하는 부분 뿐이다. 

---

원형 연결 리스트의 노드 삽입

노드의 삽입은 head에 노드를 추가한다고 하면

새 노드가 기존의 첫 노드를 가르키도록 하고, tail이 가르키던 노드 즉 마지막 노드가 새 노드인 첫 노드를 가르키도록 한다. 

// 새 노드가 기존의 첫 노드 가르키도록
newNode->next = plist->tail->next;
// tail이 가르키던 노드 즉 마지막 노드가 새 노드 즉 첫 노드 가르키도록
plist->tail->next = newNode;

 

---

원형 연결 리스트의 LFirst와 LNext (데이터 조회)

데이터의 조회는 포인터 before은 cur보다 하나 앞선 노드를 가르키고, cur은 현재 노드를 가르키도록 한다.

즉 LFirst 함수는 before 포인터는 꼬리를 가르키도록, cur 포인터는 머리를 가르키도록 하고, cur이 가르키는 노드를 반환하도록 하면되고,

LNext는  cur은 다음 노드를 가르키도록 하고 before는 cur을 따라 한칸 이동, 그리고 cur이 가르키는 데이터를 반환하면 된다.

 

---

원형 연결 리스트의 삭제

원형 연결 리스트의 삭제는 기존의 동적할당 기반 연결 리스트와 거의 동일하다. 

동적할당 기반 연결 리스트의 삭제 과정은 

1. 삭제할 노드의 이전 노드가, 삭제할 노드의 다음 노드를 가르키도록 한다 

2. 포인터 cur을 한 칸 뒤로 이동시킨다. 

 

원형 연결 리스트는 꼬리와 머리 부분이 연결되어 있지만 위와 동일한 과정으로 원형 연결 리스트에서 노드 삭제를 진행하면 정상적으로 지워진다.

하지만 예외적인 상황이 두가지 있는데 이는 동적할당 기반 연결 리스트와 달리 원형 연결리스트는 dummy 노드가 존재하지 않기 때문이다.

 

예외적인 상황 1. 삭제할 노드를 tail이 가르키는 경우

이 상황에서는 tail이 가르키는 노드가 삭제되므로 tail이 삭제될 노드의 이전 노드를 가르키도록 해야한다.

 

예외적인 상황 1. 삭제할 노드가 리스트에 홀로 남은 경우 

이 경우에는 삭제가 진행되고 나면 tail이 가르킬 노드가 없어진다. 따라서 tail이 NULL을 가르키도록 해야한다.

 

-> 그렇다면 원형 리스트에도 더미 노드를 추가한다면?

원형 리스트에도 더미 노드를 추가하면 위의 예외 상황을 처리하지 않아도 되지만, 데이터를 순환 참조하는 LNext 함수에서 예외상황이 생기기 때문에 장단점이 있다.

 

 

---

문제 05-1 [원형 연결 리스트의 활용]

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

Employee* WhoIsShift(List *plist, char name[], int next)
{
    Employee *ret;

    // 인자로 전달받은 name 찾음
    if(LFirst(plist, &ret))
    {
        // 이름 다른 경우
        if(strcmp(ret->name, name) != 0)
        {
            for(int i = 0; i < LCount(plist)-1; i++)
            {
                LNext(plist, &ret);
                // 이름 같으면 탈출
                if(strcmp(ret->name, name) == 0) break;
            }
        }
    }

    // next 번째 인원 찾음
    for(int i = 0; i < next; i++)
    {
        LNext(plist, &ret);
    }

    return ret;
}

int main()
{
    List list;
    ListInit(&list);

    Employee *emp;

    // 4명의 직원 리스트에 추가
    emp = (Employee*)malloc(sizeof(Employee));
    strcpy(emp->name, "LEE");
    emp->employeeNumber = 100;
    LInsert(&list, emp);

    emp = (Employee*)malloc(sizeof(Employee));
    strcpy(emp->name, "PARK");
    emp->employeeNumber = 200;
    LInsert(&list, emp);

    emp = (Employee*)malloc(sizeof(Employee));
    strcpy(emp->name, "KIM");
    emp->employeeNumber = 300;
    LInsert(&list, emp);

    emp = (Employee*)malloc(sizeof(Employee));
    strcpy(emp->name, "YOON");
    emp->employeeNumber = 400;
    LInsert(&list, emp);


    // KIM 3일 후 당직
    emp = WhoIsShift(&list, "KIM", 3);
    printf("%s ", emp->name);
}