[데이터구조] 원형연결리스트

 

 

 

데이터구조 조교로써 채점을 하려는데, 채점에 앞서 내가 사전적으로 다시 공부를 해야했다.

알아야 하는 개념은 연결할당시스템 and 원형연결리스트 and 가용공간 리스트

 

 

원형연결리스트

# 원형 연결리스트란

선형리스트가 아닌 원형리스트.

사진에서는 단순연결리스트처럼 맨 앞 노드를 가리키게 한 예다.

리스트의 마지막 노드가 링크의 첫번째 노드를 가리키게 되어 순환적인 형태를 띤다.

다음과 같은 특징이 있다.

• 한 노드에서 다른 모든 노드로의 접근이 가능
• 노듭의 삽입/삭제 진행시 선행 노드의 포인터가 필요

그리고, 위의 사진을 기준으로 보면 삽입/삭제시 다음과 같은 문제가 일어난다

1. head가 맨 앞 노드를 가리키고 있다.
2. 삽입시 맨 앞 노드 앞에 삽입해야한다.
3. 맨 뒤 노드까지 탐색해야 한다 => 비효율적이다.

 

 

# 개선된 원형 연결리스트 

기존 원형 연결리스트에서 head의 위치가 마지막 노드를 가리키도록 바꼈다. 이것이 일반적인 원형 연결리스트 형태이며, 다음과 같은 연결구조를 가진다.

• 마지막 노드는 헤드 포인터의 head가 가리킴
• 첫번째 노드는 head의 link가 가리킴

이를 통해, 기존의 노드 삽입/삭제 방법을 보다 편이하게 할 수 있게된다.

 

## 예시를 통한  노드 삽입/삭제 이해

얘를 봐보자.

기억하자, 이곳은 순환되는 공간이며 표시된 맨 앞의 '10' 이라는 공간은 head의 link로 가리키고 있다.

 

• 앞부분 삽입을 한다면

1. [node의 link]를 [head의 link]로 가리키게 함
   

   

2. [head의 link]를 [node]로 가리키게 함
   

   

 

• 뒷부분 삽입을 한다면

1. [node의 link]를 [head의 link]로 가리키게 함 (앞부분 삽입과 동일)
2. [head의 link]를 [node]로 가리키게 함 (앞부분 삽입과 동일)
3. [head]를 [node]가 되게 함
   

   

   코드상으로 보아도, head= node; 라는 코드만 추가가 된다.

// 앞에서 할당시키기
ListNode* first(ListNode* head, element data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head =  node;
		node->link = head;
	}
	else {
		node->link =  head->link;
		head->link =  node;	
	}
	return head;
}


// 뒤에서 할당시키기
ListNode* last(ListNode* head, element data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
	node->data = data;
	if (head == NULL) {
		head =  node ;
		node->link = head;
	}
	else {
		node->link =  head->link;	
		head->link =  node;		
		head =  node;		
	}
	return head;	
}

 

다음은 가용공간리스트에 대해서 포스팅하기

 

 

참고사이트

 

 

정보컴퓨터 임용고시 티스토리 블로그

2.2.4 원형 연결 리스트 (Circular Linked List)

yig 티스토리 블로그

[자료구조] 원형 연결리스트 Circular Linked List