원형 링크드리스트 (Circular Linked List)

원형 연결 리스트(Circular Linked list)

• 맨 뒤의 노드가 맨 앞의 노드를 가리켜서, 연결의 형태가 원을 이루는 구조

원형 연결 리스트의 새 노드 추가

단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 2개를 두지 않아도,
1개의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다.

---

head 노드가 없고, tail 포인터 노드만 존재

위 그림을 보면 포인터 변수인 tail 이 리스트의 끝을 가리키는 상황이니, 새로운 노드를
리스트의 끝에 추가하는 것이 가능하고, tail -> next 가 가리키는 것이 첫번째 노드이니,
이를 이용해 리스트의 머리에도 노드를 쉽게 추가할 수 있다.

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

---

원형 링크드 리스트 구현

원형 링크드 리스트의 메소드

조회 관련 LFirst / 조회 관련 LNext / 삭제 관련 remove
삽입 관련 / 정렬 관련 / 기타 부분

class LinkedList
{
public:
  Node *tail;
  Node *cur;
  Node *before;
  int numofData;
  
 LinkedList(); //생성자

  void Insert(LData data); //삽입 호출 시 정렬 기준이 있는지 판단하는 함수
  void FInsert(LData data); //정렬 없을 때, 꼬리에 노드 추가하는 경우
  void FInsertFront(LData data); //정렬 없을 때, 머리에 노드 추가하는 경우
  void SInsert(LData data); //정렬 있을 때 머리에 노드 추가하는 경우
  int LFirst(LData* pdata);
  int LNext(LData* pdata); //순환하는 형태 
  LData LRemove();
  int LCount();
};

1. 생성자

CLinkedList::CLinkedList()
{
  tail = NULL;
  cur = NULL;
  before = NULL;
  numofData = 0;
}

2. 삽입(1) : 머리에 새로운 노드를 추가
   

void LinkedList::FInsertFront(LData data) //정렬 없을 때, 머리에 노드 추가하는 경우
{
	Node* newNode = new Node(); //새 노드 생성
	newNode->data = data;
	if (tail == NULL) // 빈 링크드 리스트에 삽입하는 경우. 삽입 노드는 머리이자 꼬리가된다.
	{
     // tail 이 newnode를 가리키고, newnode는 자기자신을 가리키는 형태
		tail = newNode;
		newNode->next = newNode;
	}
    else // 비어있지 않은 그냥 링크드 리스트의 맨 앞에 노드를 추가하는 경우
    {
      newnode -> next = tail -> next; // tail->next  = 기존 리스트의 맨 앞 노드
      tail -> next = newnode;
      tail = newnode;
    }

3. 삽입(2)

• 위의 FInsertFront 메소드를 약간 변형시킨다.

else
{
  newnode -> next = tail -> next;
  tail -> next = newnode; // tail->next 속성값. 즉, 맨 앞 노드를 newnode로 지정
  tail = newnode;
}

---

3. LFirst - 참조 : 맨 앞 노드(머리)의 데이터 값을 참조

int LinkedList::LFirst(LData* pdata)
{
  if(tail == NULL)
    return false;
  
  // 맨 앞 노드를 tail 노드를 통해 접근해서 그 노드의 data 값을 추출함
  before = tail;
  cur = tail -> next; // cur 은 첫번째 노드(머리) 를 가리키게 함
  *pdata = cur -> data; //  pdata 가 가리키는 공간에 데이터 저장
  return true;
}

4. LNext - 참조

• 원형 연결 리스트의 경우 끝이 없으므로, 리스트의 끝을 검사하는 코드가 존재하지 않는다.
  리스트의 마지막까지 조회가 이뤄졌다면, 다시 첫번째 노드에서부터 조회가 시작된다.
  

int LinkedList::LNext(LData* pdata)
{
  if(tail == NULL)
    return false;
  
  before = cur; // cur이 가리키던 것을 before 가 가리킴 
  cur = cur -> next; // cur은 그 다음 노드를 가리킴
  *pdata = cur -> data; // pdata 가 가리키는 공간에 데이터 저장
  return true;
}

5. LRemove - 삭제

LData LinkedList::LRemove()
{
  Node* rpos = cur; // 소멸 대상의 주소값을 rpos 에 저장
  
  LData rdata = rpos -> data; // 삭제할 데이터 임시저장
  
  if(rpos == tail)
  {
    if(tail == tail => next)
      tail = NULL;
    else
      tail = before;
  }
  
  before -> next = cur -> next; // 소멸 대상을 리스트에서 제거
  cur = before; // cur이 가리키는 위치 재조정
  
  delete(rpos);
  numofData--;
  
  return rdata; // 삭제된 데이터를 리턴
}

---