원형 연결 리스트

☑️ 개념

• 마지막 노드의 링크가 다시 첫 번째 노드를 가리키는 리스트
• 한 노드에서 다른 어떤 노드로도 접근 가능
• 리스트 전체를 자유공간리스트에 반환할 때 리스트의 길이에 관계없이 일정시간에 반환 가능

☑️ 노드 삽입

• C 포인터가 첫 노드를 가리키는 경우

  • 마지막 노드의 link를 맨 앞 p로 연결해야 하는 문제 발생
  • 탐색 비용 O(n) 발생

• C 포인터가 마지막 노드를 가리키는 경우

  • 리스트 길이 상관없이 일정 시간 O(1) 노드 삽입 가능

    

    inserFornt(C,p) {
    //C는 원형 리스트 마지막 노드, p는 삽입할 노드 지시
    	if (C==NULL) {
    		C = p;
    		p->link = C;
    	}
    	else {
    		p->link = C->link;    //(1)번
    		C->link = p;         //(2)번
    		// **C = p**;           //마지막 노드에 삽입하는 경우
    	}
    }

☑️ 길이 계산

lengthC(C){
	if (C==NULL) return 0;

	length = 1;
	p = C->link; // p=순회포인터
	
	while( **p!=C** ) { // p가 처음 출발한 위치인 C로 돌아왔는지 확인
		length = length + 1
		p = p->link
	}
	return length
}

☑️ 자유공간 리스트에 반환

returnCList(C){
	if (C==NULL) return;
	
	p = C->link;
	C->link = Free;
	Free = p;
}