[알고리즘] 원형 연결 리스트 기본 , 삽입 연산

원형 연결 리스트 개념

• 단순 연결 리스트와 비슷하지만 차이점은 마지막 노드의 링크가 첫번째 노드를 가리키고 있는 리스트
  • 마지막 노드의 링크 필드가 NULL이 아닌 첫번째 노드 주소가 되는 리스트 구조
  • 장점: 한 노드에서 다른 모든 노드로의 접근이 가능 (한바퀴 돌아서 뒤로 다시 가면 되기 때문에)
• 단순 연결 리스트에서 head 포인터가 맨 앞에 있으나 원형 연결 리스트에서는 head 포인터를 마지막 노드를 가리키게 하면 노드 삽입, 삭제 연산이 용이하기 때문에 대부분 head 포인터를 맨 뒤 노드에 둔다.

원형 연결 리스트 맨 앞에 삽입

• 새로운 노드의 링크가 첫번째 노드를 가리키게 하고, 마지막 노드의 링크가 새로운 노드를 가리키면 된다.

void insert_first(ListNode** phead, ListNode* node) {
	if (*phead == NULL) { //노드가 비어있을 때
		*phead = node;
		node->link = node;
	}
	else { //노드가 비어있지 않을 때
		node->link = (*phead)->link;
		(*phead)->link = node;
	}
}

 

원형 연결 리스트 마지막에 삽입

• 원형 연결 리스트는 어차피 원형으로 돌아가기 때문에 head노드가 불분명하다. 
• 그 뜻은 마지막에 삽입하고 삽입된 노드를 head로 지정해주면 된다.

 

void insert_last(ListNode** phead, ListNode* node) {
	if (*phead == NULL) { //노드가 비어있을 때
		*phead = node;
		node->link = node;
	}
	else {
		node->link = (*phead)->link;
		(*phead)->link = node;
		*head = node;
	}
}